Aufgaben:Exercise 2.5: Three Variants of GF(2 power 4) - Revision history

Guenter at 17:10, 3 October 2022

2022-10-03T17:10:39Z

Guenter at 16:42, 3 October 2022

2022-10-03T16:42:23Z

Guenter at 15:13, 30 September 2022

2022-09-30T15:13:43Z

Noah at 21:07, 31 August 2022

2022-08-31T21:07:08Z

Noah at 20:50, 31 August 2022

2022-08-31T20:50:16Z

Noah at 20:49, 31 August 2022

2022-08-31T20:49:52Z

Show changes

Guenter at 16:58, 27 August 2022

2022-08-27T16:58:17Z

Guenter: Guenter moved page Aufgaben:Exercise 2.5: Three Variants of GF(2 to the 4th Power) to Aufgaben:Exercise 2.5: Three Variants of GF(2 power 4)

2022-08-27T16:29:36Z

Guenter moved page Exercise 2.5: Three Variants of GF(2 to the 4th Power) to Exercise 2.5: Three Variants of GF(2 power 4)

Guenter: Guenter moved page Aufgaben:Aufgabe 2.5: Drei Varianten von GF(2 hoch 4) to Aufgaben:Exercise 2.5: Three Variants of GF(2 to the 4th Power)

2022-08-27T16:01:39Z

Guenter moved page Aufgabe 2.5: Drei Varianten von GF(2 hoch 4) to Exercise 2.5: Three Variants of GF(2 to the 4th Power)

Javier: Text replacement - "„" to """

2021-05-28T14:22:20Z

Text replacement - "„" to """

@@ Line 60: / Line 60: @@
 p(x) = x^4 + x +1 =p_1(x)\hspace{0.05cm}.$$
-Thus, the <u>proposed solution 1</u> is correct.
+Thus,&nbsp; the <u>proposed solution 1</u>&nbsp; is correct.
-'''(3)'''&nbsp; Starting from polynomial $p_2(x) = x^4 + x^3 + 1$ one obtains from the determining equation $p(\alpha) = 0$ the result $\alpha^4 = \alpha^3 + 1$. This further yields:
+[[File:P_ID2512__KC_A_2_5d_neu.png|right|frame|Complete power tables over&nbsp; $\rm GF(2^4)$&nbsp; for two different polynomials <br>$($Sorry,&nbsp; we used here the German terms$)$]]
-[[File:P_ID2512__KC_A_2_5d_neu.png|center|frame|Complete power tables over $\rm GF(2^4)$ for two different polynomials]]
+'''(4)''' The polynomials&nbsp; $p_1(x) = x^4 + x + 1$&nbsp; and&nbsp; $p_2(x) = x^4 + x^3 + 1$&nbsp; are primitive.
+*This can be seen from the fact that&nbsp; $\alpha^i \ne 1$&nbsp; for&nbsp; $0 < i < 14$&nbsp; in each case.
-−
-'''(4)'''&nbsp; The two polynomials&nbsp; $p_1(x) = x^4 + x + 1$&nbsp; and&nbsp; $p_2(x) = x^4 + x^3 + 1$&nbsp; are primitive.
+*In contrast,&nbsp; $\alpha^{15} = \alpha^0 = 1$ holds.&nbsp; In both cases,&nbsp; the Galois field can be expressed as follows:
 :$${\rm GF}(2^4) = \{\hspace{0.1cm}0\hspace{0.05cm},\hspace{0.1cm} \alpha^{0}  = 1,\hspace{0.05cm}\hspace{0.1cm}
 \alpha\hspace{0.05cm},\hspace{0.1cm} \alpha^{2},\hspace{0.1cm}  ... \hspace{0.1cm}  , \hspace{0.1cm}\alpha^{14}\hspace{0.1cm}\}\hspace{0.05cm}. $$
-For the polynomial&nbsp; $p_3(x) = x^4 + x^3 + x^2 + x +1$&nbsp; we get:
+&rArr; &nbsp; For the polynomial&nbsp; $p_3(x) = x^4 + x^3 + x^2 + x +1$&nbsp; we get:
-:$$\alpha^4 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} \alpha^3 + \alpha^2 + \alpha  +1\hspace{0.25cm} \Rightarrow\hspace{0.25cm}{\rm Vector\hspace{0.15cm} 1111}\hspace{0.05cm},$$
+:$$\alpha^4 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} \alpha^3 + \alpha^2 + \alpha  +1\hspace{0.25cm} \Rightarrow\hspace{0.25cm}{\rm vector\hspace{0.15cm} 1111}\hspace{0.05cm},$$
-:$$\alpha^5 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} \alpha \cdot \alpha^4 = \alpha^4 + \alpha^3 + \alpha^2 + \alpha  = (\alpha^3 + \alpha^2 + \alpha  +1) + \alpha^3 + \alpha^2 + \alpha  = 1 \hspace{0.25cm} \Rightarrow\hspace{0.25cm}{\rm Vector\hspace{0.15cm} 0001}\hspace{0.05cm}.$$
+:$$\alpha^5 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} \alpha \cdot \alpha^4 = \alpha^4 + \alpha^3 + \alpha^2 + \alpha  = $$
+::$$= (\alpha^3 + \alpha^2 + \alpha  +1) + \alpha^3 + \alpha^2 + \alpha  = 1 \hspace{0.25cm} \Rightarrow\hspace{0.25cm}{\rm vector\hspace{0.15cm} 0001}\hspace{0.05cm}.$$
-*So here already $\alpha^5 = \alpha^0 = 1 \Rightarrow \ p_3(x)$ is not a primitive polynomial &nbsp; &#8658; &nbsp; <u>Proposed solution 2</u>.
+*So here is already&nbsp; $\alpha^5 = \alpha^0 = 1 $ <br>$\Rightarrow \ p_3(x)$ is not a primitive polynomial &nbsp; &#8658; &nbsp; <u>Proposed solution 2</u>.
-*For the other powers, this polynomial holds:
 :$$\alpha^6 = \alpha^{11} = \alpha\hspace{0.05cm},\hspace{0.2cm}
 \alpha^7 = \alpha^{12} = \alpha^2\hspace{0.05cm},\hspace{0.2cm}

@@ Line 2: / Line 2: @@
 [[File:EN_KC_A_2_5.png|right|frame|Powers of two different extension fields over $\rm GF(2^4)$ - a not quite complete list]]
-Irreducible and primitive polynomials have great importance in the description of error correction methods. For example, in [LN97] one finds the following irreducible polynomials of degree&nbsp; $m = 4$:
+Irreducible and primitive polynomials have great importance in the description of error correction methods.&nbsp; For example,&nbsp; in&nbsp; '''[LN97]'''&nbsp; one finds the following irreducible polynomials of degree&nbsp; $m = 4$:
 * $p_1(x) = x^4 + x +1$,
 * $p_2(x) = x^4 + x^3 + 1$,
 * $p_3(x) = x^4 + x^3 + x^2 + x + 1$.
-The first two polynomials are also primitive. This can be seen from the power tables given on the right &ndash; the lower table&nbsp; $\rm (B)$&nbsp; however not quite complete.
+The first two polynomials are also primitive.&nbsp; This can be seen from the power tables given on the right &ndash; the lower table&nbsp; $\rm (B)$&nbsp; however not quite complete.
-*From both tables we see that all powers&nbsp; $\alpha^i$&nbsp; for&nbsp; $1 &#8804; i &#8804; 14$&nbsp; are unequal&nbsp; $1$&nbsp; in the polynomial representation. Only for&nbsp; $i = 15$&nbsp; does it follow that
 :$$\alpha^{15} = \alpha^{0} = 1 \hspace{0.3cm} \Rightarrow\hspace{0.3cm}{\rm Coefficient\hspace{0.15cm}vector\hspace{0.15cm} 0001}\hspace{0.05cm} .$$
-*It is not specified whether the tables &nbsp;$\rm (A)$&nbsp; and &nbsp;$\rm (B)$&nbsp; result from the polynomial&nbsp; $p_1(x) = x^4 + x + 1$&nbsp; or from&nbsp; $p_2(x) =x^4 + x^3 + 1$&nbsp;. You are to make these assignments in subtasks '''(1)''' and '''(2)'''.
+*It is not specified whether the tables &nbsp;$\rm (A)$&nbsp; and &nbsp;$\rm (B)$&nbsp; result from the polynomial &nbsp; $p_1(x) = x^4 + x + 1$ &nbsp; or from &nbsp; $p_2(x) =x^4 + x^3 + 1$. &nbsp; You are to make these assignments in subtasks&nbsp; '''(1)'''&nbsp; and&nbsp; '''(2)'''.
-*In the subtask '''(3)''' you are also to complete the missing powers&nbsp; $\alpha^5, \ \alpha^6, \ \alpha^7$&nbsp; and&nbsp; $\alpha^8$&nbsp; in the table&nbsp; $\rm (B)$&nbsp; .
-*The subtask '''(4)''' refers to the also irreducible polynomial&nbsp; $p_3(x) = x^4 + x^3 + x^2 + x +1$. According to the above criteria, you are to decide whether this polynomial is primitive.
+*In the subtask&nbsp; '''(3)'''&nbsp; you are also to complete the missing powers&nbsp; $\alpha^5, \ \alpha^6, \ \alpha^7$&nbsp; and&nbsp; $\alpha^8$&nbsp; in the table&nbsp; $\rm (B)$.
@@ Line 22: / Line 24: @@
 Hints:
 *The exercise belongs to the chapter&nbsp; [[Channel_Coding/Extension_Field|"Extension Field"]].
-*The literature citation&nbsp; [LN97]&nbsp; refers to the book "Lidl, R.; Niederreiter, H.: ''Finite Fields''. Encyclopedia of Mathematics and its Application. 2nd ed. Cambridge: University Press, 1997."
@@ Line 38: / Line 41: @@
 + $p_2(x) = x^4 + x^3 + 1$.
-{Complete the entries missing in the table &nbsp;$\rm (B)$&nbsp;. Which of the following are correct?
+{Complete the entries missing in the table &nbsp;$\rm (B)$.&nbsp; Which of the following entries are correct?
 |type="[]"}
-+ $\alpha^5 = \alpha^3 + \alpha + 1$ &nbsp; &rArr; &nbsp; Coefficient vector "$1011$",
++ $\alpha^5 = \alpha^3 + \alpha + 1$ &nbsp; &rArr; &nbsp; Coefficient vector&nbsp; "$1011$",
-- $\alpha^6 = \alpha^2 + 1$ &nbsp; &rArr; &nbsp; Coefficient vector "$0111$",
+- $\alpha^6 = \alpha^2 + 1$ &nbsp; &rArr; &nbsp; Coefficient vector&nbsp; "$0111$",
-- $\alpha^7 = \alpha^3 + \alpha^2 + \alpha + 1$ &nbsp; &rArr; &nbsp; Coefficient vector "$1111$"
+- $\alpha^7 = \alpha^3 + \alpha^2 + \alpha + 1$ &nbsp; &rArr; &nbsp; Coefficient vector&nbsp; "$1111$"
-+ $\alpha^8 = \alpha^3 + \alpha^2 + \alpha$ &nbsp; &rArr; &nbsp; Coefficient vector "$1110$".
++ $\alpha^8 = \alpha^3 + \alpha^2 + \alpha$ &nbsp; &rArr; &nbsp; Coefficient vector&nbsp; "$1110$".
-{Is&nbsp; $p_3(x) = x^4 + x^3 + x^2 + x + 1$&nbsp; a primitive polynomial? Clarify this question using powers&nbsp; $\alpha^i$&nbsp; $(i$ where necessary$)$.
+{Is the polynomial &nbsp; $p_3(x) = x^4 + x^3 + x^2 + x + 1$ &nbsp; primitive?&nbsp; Clarify this question using the powers&nbsp; $\alpha^i$&nbsp; $(i$&nbsp; where necessary$)$.
 |type="()"}
 - Yes.

@@ Line 1: / Line 1: @@
 {{quiz-Header|Buchseite=Channel_Coding/Extension_Field}}
-[[File:P_ID2508__KC_A_2_5.png|right|frame|Powers of two different extension fields over $\rm GF(2^4)$ - a not quite complete list]]
+[[File:EN_KC_A_2_5.png|right|frame|Powers of two different extension fields over $\rm GF(2^4)$ - a not quite complete list]]
 Irreducible and primitive polynomials have great importance in the description of error correction methods. For example, in [LN97] one finds the following irreducible polynomials of degree&nbsp; $m = 4$:
 * $p_1(x) = x^4 + x +1$,
@@ Line 21: / Line 21: @@
 Hints:
-*The exercise belongs to the chapter&nbsp; [[Channel_Coding/Extension_Field|"extension field"]].
+*The exercise belongs to the chapter&nbsp; [[Channel_Coding/Extension_Field|"Extension Field"]].
 *The literature citation&nbsp; [LN97]&nbsp; refers to the book "Lidl, R.; Niederreiter, H.: ''Finite Fields''. Encyclopedia of Mathematics and its Application. 2nd ed. Cambridge: University Press, 1997."

@@ Line 67: / Line 67: @@
 '''(3)'''&nbsp; Starting from polynomial $p_2(x) = x^4 + x^3 + 1$ one obtains from the determining equation $p(\alpha) = 0$ the result $\alpha^4 = \alpha^3 + 1$. This further yields:
 :$$\alpha^5 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} \alpha \cdot \alpha^4 = \alpha \cdot (\alpha^3 + 1) = \alpha^4 + \alpha = \alpha^3 + \alpha +1\hspace{0.05cm} \Rightarrow\hspace{0.05cm}{\rm Vector\hspace{0.15cm} 1011},$$
-:$$\alpha^6 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} \alpha \cdot \alpha^5 = \alpha \cdot (\alpha^3 +\alpha + 1) = \alpha^4 + \alpha^2 + \alpha= \alpha^3 +\alpha^2  + \alpha + 1\hspace{0.05cm} \Rightarrow\hspace{0.05cm}{\rm Vektor\hspace{0.15cm} 1111},$$
+:$$\alpha^6 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} \alpha \cdot \alpha^5 = \alpha \cdot (\alpha^3 +\alpha + 1) = \alpha^4 + \alpha^2 + \alpha= \alpha^3 +\alpha^2  + \alpha + 1\hspace{0.05cm} \Rightarrow\hspace{0.05cm}{\rm Vector\hspace{0.15cm} 1111},$$
 :$$\alpha^7 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} \alpha \cdot \alpha^6 = \alpha^4 +\alpha^3 +\alpha^2 +\alpha =  \alpha^2  + \alpha + 1\hspace{0.05cm} \Rightarrow\hspace{0.05cm}{\rm Vector\hspace{0.15cm} 0111},$$
 :$$\alpha^8 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} \alpha \cdot \alpha^7 = \alpha \cdot (\alpha^2  + \alpha + 1) = \alpha^3 +\alpha^2 +\alpha \hspace{0.05cm} \Rightarrow\hspace{0.05cm}{\rm Vector\hspace{0.15cm} 1110}.$$
@@ Line 85: / Line 85: @@
 For the polynomial&nbsp; $p_3(x) = x^4 + x^3 + x^2 + x +1$&nbsp; we get:
-:$$\alpha^4 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} \alpha^3 + \alpha^2 + \alpha  +1\hspace{0.25cm} \Rightarrow\hspace{0.25cm}{\rm Vektor\hspace{0.15cm} 1111}\hspace{0.05cm},$$
+:$$\alpha^4 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} \alpha^3 + \alpha^2 + \alpha  +1\hspace{0.25cm} \Rightarrow\hspace{0.25cm}{\rm Vector\hspace{0.15cm} 1111}\hspace{0.05cm},$$
-:$$\alpha^5 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} \alpha \cdot \alpha^4 = \alpha^4 + \alpha^3 + \alpha^2 + \alpha  = (\alpha^3 + \alpha^2 + \alpha  +1) + \alpha^3 + \alpha^2 + \alpha  = 1 \hspace{0.25cm} \Rightarrow\hspace{0.25cm}{\rm Vektor\hspace{0.15cm} 0001}\hspace{0.05cm}.$$
+:$$\alpha^5 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} \alpha \cdot \alpha^4 = \alpha^4 + \alpha^3 + \alpha^2 + \alpha  = (\alpha^3 + \alpha^2 + \alpha  +1) + \alpha^3 + \alpha^2 + \alpha  = 1 \hspace{0.25cm} \Rightarrow\hspace{0.25cm}{\rm Vector\hspace{0.15cm} 0001}\hspace{0.05cm}.$$
 *So here already $\alpha^5 = \alpha^0 = 1 \Rightarrow \ p_3(x)$ is not a primitive polynomial &nbsp; &#8658; &nbsp; <u>Proposed solution 2</u>.

@@ Line 10: / Line 10: @@
 The first two polynomials are also primitive. This can be seen from the power tables given on the right &ndash; the lower table&nbsp; $\rm (B)$&nbsp; however not quite complete.
 *From both tables we see that all powers&nbsp; $\alpha^i$&nbsp; for&nbsp; $1 &#8804; i &#8804; 14$&nbsp; are unequal&nbsp; $1$&nbsp; in the polynomial representation. Only for&nbsp; $i = 15$&nbsp; does it follow that
-:$$\alpha^{15} = \alpha^{0} = 1 \hspace{0.3cm} \Rightarrow\hspace{0.3cm}{\rm Koeffizientenvektor\hspace{0.15cm} 0001}\hspace{0.05cm} .$$
+:$$\alpha^{15} = \alpha^{0} = 1 \hspace{0.3cm} \Rightarrow\hspace{0.3cm}{\rm Coefficient\hspace{0.15cm}vector\hspace{0.15cm} 0001}\hspace{0.05cm} .$$
 *It is not specified whether the tables &nbsp;$\rm (A)$&nbsp; and &nbsp;$\rm (B)$&nbsp; result from the polynomial&nbsp; $p_1(x) = x^4 + x + 1$&nbsp; or from&nbsp; $p_2(x) =x^4 + x^3 + 1$&nbsp;. You are to make these assignments in subtasks '''(1)''' and '''(2)'''.
 *In the subtask '''(3)''' you are also to complete the missing powers&nbsp; $\alpha^5, \ \alpha^6, \ \alpha^7$&nbsp; and&nbsp; $\alpha^8$&nbsp; in the table&nbsp; $\rm (B)$&nbsp; .

← Older revision		Revision as of 16:58, 27 August 2022
Line 100:		Line 100:


−	[[Category:Channel Coding: Exercises\|^2.2 ~~Erweiterungskörper~~^]]	+	[[Category:Channel Coding: Exercises\|^2.2 Extension Field^]]

← Older revision	Revision as of 16:29, 27 August 2022
(No difference)

← Older revision	Revision as of 16:01, 27 August 2022
(No difference)

@@ Line 23: / Line 23: @@
 ''Hinweise:''
 * Die Aufgabe gehört zum Kapitel&nbsp; [[Channel_Coding/Erweiterungsk%C3%B6rper|Erweiterungskörper]].
-*Das Literaturzitat&nbsp;  [LN97]&nbsp; verweist auf das Buch  &bdquo;Lidl, R.; Niederreiter, H.: ''Finite Fields''. Encyclopedia of Mathematics and its Application. 2. Auflage. Cambridge: University Press, 1997".
+*Das Literaturzitat&nbsp;  [LN97]&nbsp; verweist auf das Buch  "Lidl, R.; Niederreiter, H.: ''Finite Fields''. Encyclopedia of Mathematics and its Application. 2. Auflage. Cambridge: University Press, 1997".
@@ Line 41: / Line 41: @@
 {Ergänzen Sie die in der Tabelle &nbsp;$\rm (B)$&nbsp; fehlenden Einträge. Welche der folgenden Angaben sind richtig?
 |type="[]"}
-+ $\alpha^5 = \alpha^3 + \alpha + 1$ &nbsp; &rArr; &nbsp; Koeffizientenvektor &bdquo;$1011$",
++ $\alpha^5 = \alpha^3 + \alpha + 1$ &nbsp; &rArr; &nbsp; Koeffizientenvektor "$1011$",
-- $\alpha^6 = \alpha^2 + 1$ &nbsp; &rArr; &nbsp; Koeffizientenvektor &bdquo;$0111$",
+- $\alpha^6 = \alpha^2 + 1$ &nbsp; &rArr; &nbsp; Koeffizientenvektor "$0111$",
-- $\alpha^7 = \alpha^3 + \alpha^2 + \alpha + 1$ &nbsp; &rArr; &nbsp; Koeffizientenvektor &bdquo;$1111$",
+- $\alpha^7 = \alpha^3 + \alpha^2 + \alpha + 1$ &nbsp; &rArr; &nbsp; Koeffizientenvektor "$1111$",
-+ $\alpha^8 = \alpha^3 + \alpha^2 + \alpha$ &nbsp; &rArr; &nbsp; Koeffizientenvektor &bdquo;$1110$".
++ $\alpha^8 = \alpha^3 + \alpha^2 + \alpha$ &nbsp; &rArr; &nbsp; Koeffizientenvektor "$1110$".
 {Ist&nbsp; $p_3(x) = x^4 + x^3 + x^2 + x + 1$&nbsp; ein primitives Polynom? Klären Sie diese Frage anhand der Potenzen&nbsp; $\alpha^i$&nbsp; $(i$ soweit erforderlich$)$.