Channel Coding/Some Basics of Algebra - Revision history

Maintenance script: Join 3 split formula blocks

2026-03-16T14:15:16Z

Join 3 split formula blocks

@@ Line 102: / Line 102: @@
 You can see the addition table and multiplication table below:
-:$$Z_2 = \{0, 1\}\hspace{0.25cm} \Rightarrow\hspace{0.25cm}\text{Addition:      }
+:$$Z_2 = \{0, 1\}\hspace{0.25cm} \Rightarrow\hspace{0.25cm}\text{Addition:      }\left[ \begin{array}{c|cccccc} + & 0 & 1  \\ \hline0 & 0 & 1  \\1 & 1 & 0\end{array} \right] \hspace{-0.1cm} ,\hspace{0.25cm}\text{Multiplication:      }\left[ \begin{array}{c|cccccc} \cdot & 0 & 1 \\ \hline0 & 0 & 0   \\1 & 0 & 1\end{array} \right]\hspace{0.25cm} \Rightarrow\hspace{0.25cm}{\rm GF}(2) .$$
 One can see from this representation:
@@ Line 125: / Line 116: @@
 $\text{Example 1:}$&nbsp;  The number set&nbsp; $Z_3 = \{0, 1, 2\}$ &nbsp; &#8658; &nbsp; $q = 3$&nbsp; satisfies all eight criteria and is thus a Galois field&nbsp; $\rm GF(3)$:
-:$$Z_3 = \{0, 1, 2\}\hspace{0.25cm} \Rightarrow\hspace{0.25cm}\text{Addition:      }
+:$$Z_3 = \{0, 1, 2\}\hspace{0.25cm} \Rightarrow\hspace{0.25cm}\text{Addition:      }\left[ \begin{array}{c {{!}} cccccc} + & 0 & 1  & 2\\ \hline0 & 0 & 1 & 2 \\1 & 1 & 2 & 0 \\2 & 2 & 0 & 1\end{array} \right] \hspace{-0.1cm} ,\hspace{0.25cm}\text{Multiplication:      }\left[ \begin{array}{c {{!}} cccccc} \cdot & 0 & 1  & 2\\ \hline0 & 0 & 0 & 0 \\1 & 0 & 1 & 2 \\2& 0 & 2 & 1\end{array} \right]\hspace{0.25cm} \Rightarrow\hspace{0.25cm}{\rm GF}(3) .$$}}
@@ Line 145: / Line 125: @@
 *But in the multiplication table there is no entry with&nbsp; "$1$"&nbsp; in the third row and third column&nbsp; $($each valid for the multiplicand&nbsp; $z_2 = 2)$.
-:$$Z_4 = \{0, 1, 2, 3\}\hspace{0.25cm} \Rightarrow\hspace{0.25cm}\text{Addition:      }
+:$$Z_4 = \{0, 1, 2, 3\}\hspace{0.25cm} \Rightarrow\hspace{0.25cm}\text{Addition:      }\left[ \begin{array}{c {{!}} cccccc} + & 0 & 1  & 2 & 3\\ \hline0 & 0 & 1 & 2 & 3\\1 & 1 & 2 & 3 & 0\\2 & 2 & 3 & 0 & 1\\3 & 3 & 0 & 1 & 2\end{array} \right] \hspace{-0.1cm} ,\hspace{0.25cm}\text{Multiplication:      }\left[ \begin{array}{c {{!}} cccccc} \cdot& 0 & 1  & 2 & 3\\ \hline0 & 0 & 0 & 0 & 0\\1 & 0 & 1 & 2 & 3\\2 & 0 & 2 & 0 & 2\\3 & 0 & 3 & 2 & 1\end{array} \right]\hspace{0.25cm} \Rightarrow\hspace{0.25cm}\text{no }{\rm GF}(4) .$$}}

Maintenance script: Add German interlanguage link

2026-03-16T12:27:35Z

Add German interlanguage link

← Older revision		Revision as of 14:27, 16 March 2026
Line 275:		Line 275:

	{{Display}}		{{Display}}
			[[de:Kanalcodierung/Einige_Grundlagen_der_Algebra]]

Hwang at 14:09, 19 November 2022

2022-11-19T14:09:40Z

← Older revision		Revision as of 16:09, 19 November 2022
Line 188:		Line 188:
	*For understanding the Reed–Solomon codes, however, this knowledge is not absolutely necessary.		*For understanding the Reed–Solomon codes, however, this knowledge is not absolutely necessary.

	*So you could jump directly to the chapter  [[Channel_Coding/Extension_Field#Verallgemeinerte_Definition_eines_Erweiterungsk.C3.B6rpers\| ~~$\text{~~Extension Field}$]] .<br>		*So you could jump directly to the chapter  [[Channel_Coding/Extension_Field#Verallgemeinerte_Definition_eines_Erweiterungsk.C3.B6rpers\| "Extension Field"]] .<br>

Hwang at 14:07, 19 November 2022

2022-11-19T14:07:22Z

← Older revision		Revision as of 16:07, 19 November 2022
Line 165:		Line 165:
	*A Galois field  ${\rm GF}(q)$  can be formed in the manner described here as  [[Channel_Coding/Some_Basics_of_Algebra#Definition_and_examples_of_an_algebraic_ring\| $\text{ring}$]]  of integer sizes modulo  $q$  only if  $q$  is a prime number:   <br>     $q = 2$,  $q = 3$,  $q = 5$,  $q = 7$,  $q = 11$, ...<br>		*A Galois field  ${\rm GF}(q)$  can be formed in the manner described here as  [[Channel_Coding/Some_Basics_of_Algebra#Definition_and_examples_of_an_algebraic_ring\| $\text{ring}$]]  of integer sizes modulo  $q$  only if  $q$  is a prime number:   <br>     $q = 2$,  $q = 3$,  $q = 5$,  $q = 7$,  $q = 11$, ...<br>

	*But if the order  $q$  can be expressed in the form  $q = P^m$  with a prime  $P$  and integer  $m$,  the Galois field  ${\rm GF}(q)$  can be found via an  [[Channel_Coding/Extension_Field#Generalized_definition_of_an_extension_field\|$\text{extension field}$]]  ~~find.~~}}<br>		*But if the order  $q$  can be expressed in the form  $q = P^m$  with a prime  $P$  and integer  $m$,  the Galois field  ${\rm GF}(q)$  can be found via an  [[Channel_Coding/Extension_Field#Generalized_definition_of_an_extension_field\|$\text{extension field}$]].  }}<br>

	== Group, ring, field - basic algebraic concepts ==		== Group, ring, field - basic algebraic concepts ==

Hwang at 14:06, 19 November 2022

2022-11-19T14:06:32Z

← Older revision		Revision as of 16:06, 19 November 2022
Line 165:		Line 165:
	*A Galois field  ${\rm GF}(q)$  can be formed in the manner described here as  [[Channel_Coding/Some_Basics_of_Algebra#Definition_and_examples_of_an_algebraic_ring\| $\text{ring}$]]  of integer sizes modulo  $q$  only if  $q$  is a prime number:   <br>     $q = 2$,  $q = 3$,  $q = 5$,  $q = 7$,  $q = 11$, ...<br>		*A Galois field  ${\rm GF}(q)$  can be formed in the manner described here as  [[Channel_Coding/Some_Basics_of_Algebra#Definition_and_examples_of_an_algebraic_ring\| $\text{ring}$]]  of integer sizes modulo  $q$  only if  $q$  is a prime number:   <br>     $q = 2$,  $q = 3$,  $q = 5$,  $q = 7$,  $q = 11$, ...<br>

	*But if the order  $q$  can be expressed in the form  $q = P^m$  with a prime  $P$  and integer  $m$,  the Galois field  ${\rm GF}(q)$  can be found via an  [[Channel_Coding/Extension_Field#~~Generalized_Definition_of_an_Extension. C3.B6rpers~~\|$\text{extension field}$]]  find.}}<br>		*But if the order  $q$  can be expressed in the form  $q = P^m$  with a prime  $P$  and integer  $m$,  the Galois field  ${\rm GF}(q)$  can be found via an  [[Channel_Coding/Extension_Field#Generalized_definition_of_an_extension_field\|$\text{extension field}$]]  find.}}<br>

	== Group, ring, field - basic algebraic concepts ==		== Group, ring, field - basic algebraic concepts ==

Hwang at 14:02, 19 November 2022

2022-11-19T14:02:22Z

← Older revision		Revision as of 16:02, 19 November 2022
Line 157:		Line 157:
	2 & 0 & 2 & 0 & 2\\		2 & 0 & 2 & 0 & 2\\
	3 & 0 & 3 & 2 & 1		3 & 0 & 3 & 2 & 1
	\end{array} \right]\hspace{0.25cm} \Rightarrow\hspace{0.25cm}\text{~~kein~~ }{\rm GF}(4) .		\end{array} \right]\hspace{0.25cm} \Rightarrow\hspace{0.25cm}\text{no }{\rm GF}(4) .
	$$}}		$$}}

Hwang at 13:55, 19 November 2022

2022-11-19T13:55:30Z

← Older revision		Revision as of 15:55, 19 November 2022
Line 64:		Line 64:

	::<math>\forall \hspace{0.15cm} z_i \in {\rm GF}(q),\hspace{0.15cm} \exists \hspace{0.15cm} {\rm Inv_A}(z_i) \in {\rm GF}(q)\text{:}		::<math>\forall \hspace{0.15cm} z_i \in {\rm GF}(q),\hspace{0.15cm} \exists \hspace{0.15cm} {\rm Inv_A}(z_i) \in {\rm GF}(q)\text{:}
	\hspace{0.25cm}z_i + {\rm Inv_A}(z_i) = N_{\rm A} = {0} \hspace{0.3cm}\Rightarrow \hspace{0.3cm}\text{~~kurz~~:}\hspace{0.3cm}		\hspace{0.25cm}z_i + {\rm Inv_A}(z_i) = N_{\rm A} = {0} \hspace{0.3cm}\Rightarrow \hspace{0.3cm}\text{short:}\hspace{0.3cm}
	{\rm Inv_A}(z_i) = - z_i \hspace{0.05cm}. </math>		{\rm Inv_A}(z_i) = - z_i \hspace{0.05cm}. </math>

Line 70:		Line 70:

	::<math>\forall \hspace{0.15cm} z_i \in {\rm GF}(q),\hspace{0.15cm} z_i \ne N_{\rm A}, \hspace{0.15cm} \exists \hspace{0.15cm} {\rm Inv_M}(z_i) \in {\rm GF}(q)\text{:}		::<math>\forall \hspace{0.15cm} z_i \in {\rm GF}(q),\hspace{0.15cm} z_i \ne N_{\rm A}, \hspace{0.15cm} \exists \hspace{0.15cm} {\rm Inv_M}(z_i) \in {\rm GF}(q)\text{:}
	\hspace{0.25cm}z_i \cdot {\rm Inv_M}(z_i) = N_{\rm M} = {1}\hspace{0.3cm}\Rightarrow \hspace{0.3cm}\text{~~kurz~~:}\hspace{0.3cm}		\hspace{0.25cm}z_i \cdot {\rm Inv_M}(z_i) = N_{\rm M} = {1}\hspace{0.3cm}\Rightarrow \hspace{0.3cm}\text{short:}\hspace{0.3cm}
	{\rm Inv_M}(z_i) = z_i^{-1}		{\rm Inv_M}(z_i) = z_i^{-1}
	\hspace{0.05cm}. </math>		\hspace{0.05cm}. </math>

Hwang at 13:50, 19 November 2022

2022-11-19T13:50:50Z

← Older revision		Revision as of 15:50, 19 November 2022
Line 8:		Line 8:
	== # OVERVIEW OF THE SECOND MAIN CHAPTER # ==		== # OVERVIEW OF THE SECOND MAIN CHAPTER # ==
	<br>		<br>
	This chapter discusses the  »Reed-Solomon codes«,  invented in the early 1960s by  [https://en.wikipedia.org/wiki/Irving_S._Reed $\text{Irving Stoy Reed}$]  and  [https://en.wikipedia.org/wiki/Gustave_Solomon $\text{Gustave Solomon}$].  Unlike binary block codes,  these codes are based on a Galois field   ${\rm GF}(2^m)$   with  $m > 1$.  So they work with ~~multilevel~~ symbols instead of binary characters  ("bits").		This chapter discusses the  »Reed-Solomon codes«,  invented in the early 1960s by  [https://en.wikipedia.org/wiki/Irving_S._Reed $\text{Irving Stoy Reed}$]  and  [https://en.wikipedia.org/wiki/Gustave_Solomon $\text{Gustave Solomon}$].  Unlike binary block codes,  these codes are based on a Galois field   ${\rm GF}(2^m)$   with  $m > 1$.  So they work with multi-level symbols instead of binary characters  ("bits").

	Specifically,  this chapter covers:		Specifically,  this chapter covers:

Hwang at 13:27, 19 November 2022

2022-11-19T13:27:16Z

Show changes

Hwang at 23:59, 12 November 2022

2022-11-12T23:59:37Z

← Older revision		Revision as of 01:59, 13 November 2022
Line 95:		Line 95:
	<br>		<br>
	We first check that for the binary number set  $Z_2 = \{0, 1\}$   ⇒   $q=2$   $($valid for the simple binary code$)$		We first check that for the binary number set  $Z_2 = \{0, 1\}$   ⇒   $q=2$   $($valid for the simple binary code$)$
	*the eight criteria mentioned on the last ~~page~~ are met,		*the eight criteria mentioned in the last section are met,

	*so that we can indeed speak of  "${\rm GF}(2)$".		*so that we can indeed speak of  "${\rm GF}(2)$".
Line 169:		Line 169:
	== Group, ring, field - basic algebraic concepts ==		== Group, ring, field - basic algebraic concepts ==
	<br>		<br>
	On the first ~~pages~~,  some basic algebraic terms have already been mentioned,  without their meanings having been explained in more detail.  This is to be made up now in all shortness from view of a communication engineer, whereby we mainly refer to the representation in  [Fri96]<ref name='Fri96'>Friedrichs, B.:  Kanalcodierung – Grundlagen und Anwendungen in modernen Kommunikationssystemen.  Berlin – Heidelberg: Springer, 1996.</ref>  and  [KM+08]<ref name='KM+08'>Kötter, R.; Mayer, T.; Tüchler, M.; Schreckenbach, F.; Brauchle, J.:  Channel Coding.  Lecture manuscript, Chair of Communications Engineering, TU Munich, 2008.</ref>.  To summarize:<br>		In the first sections,  some basic algebraic terms have already been mentioned,  without their meanings having been explained in more detail.  This is to be made up now in all shortness from view of a communication engineer, whereby we mainly refer to the representation in  [Fri96]<ref name='Fri96'>Friedrichs, B.:  Kanalcodierung – Grundlagen und Anwendungen in modernen Kommunikationssystemen.  Berlin – Heidelberg: Springer, 1996.</ref>  and  [KM+08]<ref name='KM+08'>Kötter, R.; Mayer, T.; Tüchler, M.; Schreckenbach, F.; Brauchle, J.:  Channel Coding.  Lecture manuscript, Chair of Communications Engineering, TU Munich, 2008.</ref>.  To summarize:<br>

	{{BlaueBox\|TEXT=		{{BlaueBox\|TEXT=
Line 185:		Line 185:


	On the next two ~~pages~~, the algebraic terms mentioned here will be discussed in more detail.		In the next two sections, the algebraic terms mentioned here will be discussed in more detail.
	*For understanding the Reed–Solomon codes, however, this knowledge is not absolutely necessary.		*For understanding the Reed–Solomon codes, however, this knowledge is not absolutely necessary.