Channel Coding/Extension Field - Revision history

Hwang at 16:10, 23 November 2022

2022-11-23T16:10:48Z

Hwang at 16:08, 23 November 2022

2022-11-23T16:08:14Z

Hwang at 16:03, 23 November 2022

2022-11-23T16:03:27Z

Guenter at 10:45, 22 November 2022

2022-11-22T10:45:11Z

Guenter at 10:43, 22 November 2022

2022-11-22T10:43:22Z

Guenter at 10:33, 22 November 2022

2022-11-22T10:33:20Z

Guenter at 10:28, 22 November 2022

2022-11-22T10:28:20Z

Hwang at 14:46, 19 November 2022

2022-11-19T14:46:45Z

Hwang at 14:34, 19 November 2022

2022-11-19T14:34:52Z

Hwang at 14:32, 19 November 2022

2022-11-19T14:32:32Z

@@ Line 337: / Line 337: @@
 {{GraueBox|TEXT=
-$\text{Example 3:}$&nbsp; From the number set&nbsp; $Z_5 = \{0,\ 1,\ 2,\ 3,\ 4\}$,&nbsp; the numberss&nbsp; "$2$"&nbsp; and&nbsp; "$3$"&nbsp; are primitive elements because of
+$\text{Example 3:}$&nbsp; From the number set&nbsp; $Z_5 = \{0,\ 1,\ 2,\ 3,\ 4\}$,&nbsp; the numbers&nbsp; "$2$"&nbsp; and&nbsp; "$3$"&nbsp; are primitive elements because of
 ::<math>2^1 \hspace{-0.1cm}  =  \hspace{-0.1cm} 2\hspace{0.05cm},\hspace{0.2cm} 2^2 = 4\hspace{0.05cm},\hspace{0.2cm} 2^3 = 8 \hspace{0.1cm}{\rm mod} \hspace{0.1cm} 5 = 3\hspace{0.05cm},\hspace{0.2cm} 2^4 = 16 \hspace{0.1cm}{\rm mod} \hspace{0.1cm} 5 = 1\hspace{0.05cm},</math>

@@ Line 222: / Line 222: @@
 \hspace{0.05cm}.</math>
-With&nbsp; $a_0 =  a_1 = a_3 = b_0 =  b_1 =b_2 = 1$ &nbsp; und &nbsp;  $a_2 =  a_4 = a_5 = b_3 =  b_4 =b_5 = 0$  &nbsp;we obtain:
+With&nbsp; $a_0 =  a_1 = a_3 = b_0 =  b_1 =b_2 = 1$ &nbsp; and &nbsp;  $a_2 =  a_4 = a_5 = b_3 =  b_4 =b_5 = 0$  &nbsp;we obtain:
 ::<math>c_0 = a_0 \cdot b_0 = 1 \cdot 1 = 1 \hspace{0.05cm},</math>

@@ Line 108: / Line 108: @@
 *In the last row of the multiplication table and also in the last column there is now no "$1$" &nbsp; &#8658; &nbsp; Concerning the condition&nbsp; $p(\alpha)= \alpha^2 + 1= 0$&nbsp; consequently the multiplicative inverse to&nbsp; $1 +\alpha$&nbsp; does not exist.<br>
-*But thus the finite set&nbsp; $\{0, \ 1, \ \alpha, \ 1 + \alpha\}$ together with arithmetic operations modulo&nbsp; $p(\alpha)= \alpha^2 + 1$&nbsp; does not satisfy the conditions of an extension fields either&nbsp; $\rm GF(2^2) $.<br><br>
+*But thus the finite set&nbsp; $\{0, \ 1, \ \alpha, \ 1 + \alpha\}$ together with arithmetic operations modulo&nbsp; $p(\alpha)= \alpha^2 + 1$&nbsp; does not satisfy the conditions of an extension field either&nbsp; $\rm GF(2^2) $.<br><br>
 {{BlaueBox|TEXT=

@@ Line 308: / Line 308: @@
 Further it is to be noted:
 #The yellow highlighted positions&nbsp; $q=P$ &nbsp; &#8658; &nbsp; $m = 1$&nbsp; mark sets of numbers&nbsp; $\{0,\ 1,\hspace{0.05cm}\text{ ...} \hspace{0.05cm},\ q- 1\}$&nbsp; with Galois properties, see section&nbsp; [[Channel_Coding/Some_Basics_of_Algebra#Definition_of_a_Galois_field|"Definition of a Galois Field"]].<br>
-#The other background colors mark extension fields with&nbsp; $q=P^m$, &nbsp; $m &#8805; 2$.&nbsp; For&nbsp; $q &#8804; 64$&nbsp; these are based on the primes&nbsp; $2$,&nbsp; $3$,&nbsp; $5$&nbsp; and&nbsp; $7$.<br>
+#Other background colors mark extension fields with&nbsp; $q=P^m$, &nbsp; $m &#8805; 2$.&nbsp; For&nbsp; $q &#8804; 64$&nbsp; these are based on the primes&nbsp; $2$,&nbsp; $3$,&nbsp; $5$,&nbsp;  $7$.<br>
 #Highlighted in red are binary fields &nbsp; &#8658; &nbsp; $q=2^m$, &nbsp; $m &#8805; 1$, which will be considered in more detail in the next section.
 # All other extension fields are labeled in blue.<br>

@@ Line 117: / Line 117: @@
 ::<math>p(x) = x^2 + k_1 \cdot x + k_0 \hspace{0.05cm}, \hspace{0.45cm}k_0\hspace{0.05cm},\hspace{0.1cm}k_1 \in \{0, 1\}
 \hspace{0.05cm}.</math>
-&nbsp; <i>Note:</i> &nbsp; The renaming of the variable&nbsp; $\alpha$&nbsp; to&nbsp; $x$&nbsp; has only formal meaning with regard to later sections.<br>
+&nbsp; <u>Note:</u> &nbsp; The renaming of the variable&nbsp; $\alpha$&nbsp; to&nbsp; $x$&nbsp; has only formal meaning with regard to later sections.<br>
 *In the present case there is only one suitable polynomial&nbsp; $p_1(x)= x^2 + x + 1$. All other possible polynomials of degree&nbsp; $m = 2$, namely,
@@ Line 124: / Line 124: @@
 ::<math>p_4(x) = x^2 + x = (x+1) \cdot x\hspace{0.05cm}, </math>
 :can be factorized and do not yield extension fields.
 *The polynomials&nbsp; $p_2(x)$,&nbsp; $p_3(x)$&nbsp; and&nbsp; $p_4(x)$&nbsp; are called&nbsp; "reducible".
 *The conclusion is obvious that only&nbsp; "irreducible polynomials"&nbsp; such as&nbsp; $p_1(x)$&nbsp; are suitable for an extension fields}}.<br>

@@ Line 74: / Line 74: @@
 {{BlaueBox|TEXT=
 $\text{Intermediate result:}$&nbsp;
-*The set&nbsp; $\{0, \ 1, \ \alpha, \ 1 + \alpha\}$&nbsp; together with the two operations&nbsp;  "addition"&nbsp; and&nbsp; "multiplication"&nbsp; modulo&nbsp; $p(\alpha)= \alpha^2 + \alpha +  1$&nbsp; represents a <i>Galois field</i>. The order is&nbsp; $q = 4$.
+*The set&nbsp; $\{0, \ 1, \ \alpha, \ 1 + \alpha\}$&nbsp; together with operations&nbsp;  "addition"&nbsp; and&nbsp; "multiplication"&nbsp; modulo&nbsp; $p(\alpha)= \alpha^2 + \alpha +  1$&nbsp; represents a&nbsp; "Galois field"&nbsp; $($order&nbsp; $q = 4)$.
 *This Galois field, denoted by&nbsp; $\rm GF(2^2) = GF(4)$&nbsp; satisfies all the requirements mentioned in the&nbsp; [[Channel_Coding/Some_Basics_of_Algebra#Definition_of_a_Galois_field| "previous chapter"]]&nbsp;.<br>
 *In contrast to the Galois field&nbsp; $\rm GF(3) = \{0, \ 1, \ 2\}$&nbsp; with the property that&nbsp; $q = 3$&nbsp; is a prime number, $\rm GF(2^2)$&nbsp; is called an extension field.}}<br>

@@ Line 304: / Line 304: @@
 Further it is to be noted:
-#The yellow highlighted positions&nbsp; $q=P$ &nbsp; &#8658; &nbsp; $m = 1$&nbsp; mark sets of numbers&nbsp; $\{0,\ 1,\hspace{0.05cm}\text{ ...} \hspace{0.05cm},\ q- 1\}$&nbsp; with Galois properties, see section&nbsp; [[Channel_Coding/Some_Basics_of_Algebra#Definition_of_a_Galois_field| "Definition of a Galois Field"]].<br>
+#The yellow highlighted positions&nbsp; $q=P$ &nbsp; &#8658; &nbsp; $m = 1$&nbsp; mark sets of numbers&nbsp; $\{0,\ 1,\hspace{0.05cm}\text{ ...} \hspace{0.05cm},\ q- 1\}$&nbsp; with Galois properties, see section&nbsp; [[Channel_Coding/Some_Basics_of_Algebra#Definition_of_a_Galois_field|"Definition of a Galois Field"]].<br>
 #The other background colors mark extension fields with&nbsp; $q=P^m$, &nbsp; $m &#8805; 2$.&nbsp; For&nbsp; $q &#8804; 64$&nbsp; these are based on the primes&nbsp; $2$,&nbsp; $3$,&nbsp; $5$&nbsp; and&nbsp; $7$.<br>
 #Highlighted in red are binary fields &nbsp; &#8658; &nbsp; $q=2^m$, &nbsp; $m &#8805; 1$, which will be considered in more detail in the next section.
@@ Line 320: / Line 320: @@
 *The polynomials in columns 2 and 3 are not only irreducible,&nbsp; but additionally also primitive.<br>
-*Primitive polynomials also provide the basis for the&nbsp; [[Theory_of_Stochastic_Signals/Generation_of_Discrete_Random_Variables#Realization_of_PN_generators| "realization of pseudo&ndash;noise generators"]].<br>
+*Primitive polynomials also provide the basis for the&nbsp; [[Theory_of_Stochastic_Signals/Generation_of_Discrete_Random_Variables#Realization_of_PN_generators|"Realization of pseudo&ndash;noise generators"]].<br>

@@ Line 187: / Line 187: @@
 <br>
 {{BlaueBox|TEXT=
-$\text{Definition:}$&nbsp; A&nbsp; '''polynomial'''&nbsp; in a finite field&nbsp; ${\rm GF}(P)$,&nbsp; where&nbsp; $P$&nbsp; denotes a prime number,&nbsp; has the following form:
+$\text{Definition:}$&nbsp; A&nbsp; &raquo;'''polynomial'''&laquo;&nbsp; in a finite field&nbsp; ${\rm GF}(P)$,&nbsp; where&nbsp; $P$&nbsp; denotes a prime number,&nbsp; has the following form:
 ::<math>a(x) = \sum_{i = 0}^{m} a_i \cdot x^{i}  = a_0 + a_1 \cdot x + a_2 \cdot x^2 + \hspace{0.1cm}\text{...} \hspace{0.1cm} + a_m \cdot x^{m}
@@ Line 194: / Line 194: @@
 *All coefficients&nbsp; $a_i $&nbsp; are elements of the field: &nbsp; $a_i \in {\rm GF}(P)$.<br>
-*If the leading coefficient&nbsp; $a_m &ne; 0$, then&nbsp; $m$&nbsp; indicates the&nbsp; '''degree'''&nbsp; of the polynomial.}}<br>
+*If the leading coefficient&nbsp; $a_m &ne; 0$, then&nbsp; $m$&nbsp; indicates the&nbsp; &raquo;'''degree'''&laquo;&nbsp; of the polynomial.}}<br>
 Let us consider a second polynomial with degree $M$,
@@ Line 240: / Line 240: @@
 {{BlaueBox|TEXT=
-$\text{Definition:}$&nbsp; A polynomial&nbsp; $a(x)$&nbsp; is called&nbsp; '''reducible'''&nbsp; if it can be represented as the product of two polynomials&nbsp; $p(x)$&nbsp; and&nbsp; $q(x)$&nbsp; each of lower degree:
+$\text{Definition:}$&nbsp; A polynomial&nbsp; $a(x)$&nbsp; is called&nbsp; &raquo;'''reducible'''&laquo;&nbsp; if it can be represented as the product of two polynomials&nbsp; $p(x)$&nbsp; and&nbsp; $q(x)$&nbsp; each of lower degree:
 ::<math>a(x) = p(x) \cdot q(x)
@@ Line 249: / Line 249: @@
 ::<math>a(x) = p(x) \cdot q(x) + r(x)\hspace{0.05cm},\hspace{0.5cm} r(x) \ne 0</math>
-holds,&nbsp; then the polynomial is called an&nbsp; '''irreducible'''&nbsp; or&nbsp; '''prime'''.}}<br>
+holds,&nbsp; then the polynomial is called an&nbsp; &raquo;'''irreducible'''&laquo;&nbsp; or&nbsp; &raquo;'''prime'''&laquo;.}}<br>
 {{GraueBox|TEXT=
@@ Line 327: / Line 327: @@
 ::<math>{\rm GF}(q) = \{\hspace{0.05cm}z_0 = 0,\hspace{0.1cm} z_1 = 1,\hspace{0.05cm}  \text{...}\hspace{0.05cm} , \hspace{0.05cm}z_{q-1}\}.</math>
-The element&nbsp; $z_i = \beta$&nbsp; is then called&nbsp; '''primitive'''&nbsp;,
+The element&nbsp; $z_i = \beta$&nbsp; is then called&nbsp; &raquo;'''primitive'''&laquo;&nbsp;,
 *if the power&nbsp; $\beta^{\hspace{0.05cm}i}$&nbsp; modulo&nbsp; $q$&nbsp; for the first time for&nbsp; $i = q-1$&nbsp; leads to the result&nbsp; "$1$"&nbsp; so that  <br>
@@ Line 344: / Line 344: @@
 {{BlaueBox|TEXT=
-$\text{Definition:}$&nbsp;  An irreducible polynomial is called at the same time a&nbsp; "'''primitive polynomial'''"&nbsp; <br> &nbsp; &nbsp; if the root&nbsp; $\alpha$&nbsp; with respect to the polynomial&nbsp; $p(x)$&nbsp; is a primitive element of&nbsp; ${\rm GF}(q)$.&nbsp;  Then holds
+$\text{Definition:}$&nbsp;  An irreducible polynomial is called at the same time a&nbsp; &raquo;'''primitive polynomial'''&laquo;&nbsp; <br> &nbsp; &nbsp; if the root&nbsp; $\alpha$&nbsp; with respect to the polynomial&nbsp; $p(x)$&nbsp; is a primitive element of&nbsp; ${\rm GF}(q)$.&nbsp;  Then holds
 ::<math>{\rm GF}(q) = \{\hspace{0.1cm}\alpha^{-\infty} = 0\hspace{0.05cm},\hspace{0.1cm} \alpha^{0}  = 1,\hspace{0.05cm}\hspace{0.2cm}
@@ Line 382: / Line 382: @@
 $\text{Example 5:}$&nbsp; The elements&nbsp; $z_0$,&nbsp; $z_1$, ... ,&nbsp; $z_7$&nbsp; of the Galois field&nbsp; $\rm GF(2^3)$&nbsp; can be represented according to the adjacent table as follows:
 [[File:EN_KC_T_2_2_S4b_neu.png|right|frame|Elements of&nbsp; $\rm GF(2^3)$&nbsp; in three different representations]]
-*as powers of&nbsp; $\alpha$ &nbsp; &rArr; &nbsp; "'''exponent representation'''",<br>
+*as powers of&nbsp; $\alpha$ &nbsp; &rArr; &nbsp; &raquo;'''exponent representation'''&laquo;,<br>
-*as polynomials of the form&nbsp; $k_2 \cdot \alpha^2 + k_1 \cdot \alpha + k_0$&nbsp; with binary coefficients&nbsp; $k_2$,&nbsp; $k_1$,&nbsp; $k_0$ &nbsp; &rArr; &nbsp; "'''polynomial representation'''",<br>
+*as polynomials of the form&nbsp; $k_2 \cdot \alpha^2 + k_1 \cdot \alpha + k_0$&nbsp; with binary coefficients&nbsp; $k_2$,&nbsp; $k_1$,&nbsp; $k_0$ &nbsp; &rArr; &nbsp; &raquo;'''polynomial representation'''&laquo;,<br>
-*as vectors of coefficients&nbsp; $(k_2, \ k_1, \ k_0)$ &nbsp; &rArr; &nbsp; "'''coefficient representation'''".<br><br>
+*as vectors of coefficients&nbsp; $(k_2, \ k_1, \ k_0)$ &nbsp; &rArr; &nbsp; &raquo;'''coefficient representation'''&laquo;.<br><br>
 &rArr; &nbsp; For addition&nbsp; (or subtraction)&nbsp; of two elements polynomial and vector representation are equally suitable, <br>where the components are to be added&nbsp; $\text{modulo 2}$,&nbsp; for example: