Aufgaben:Exercise 2.3: Reducible and Irreducible Polynomials - Revision history

Guenter at 15:14, 29 September 2022

2022-09-29T15:14:45Z

Guenter at 14:54, 29 September 2022

2022-09-29T14:54:09Z

Noah at 12:55, 31 August 2022

2022-08-31T12:55:50Z

Noah at 12:51, 31 August 2022

2022-08-31T12:51:18Z

Noah at 12:48, 31 August 2022

2022-08-31T12:48:53Z

Show changes

Noah at 12:29, 31 August 2022

2022-08-31T12:29:43Z

Noah at 12:29, 31 August 2022

2022-08-31T12:29:26Z

Guenter at 16:56, 27 August 2022

2022-08-27T16:56:21Z

Guenter: Guenter moved page Aufgaben:Aufgabe 2.3: Reduzible und irreduzible Polynome to Aufgaben:Exercise 2.3: Reducible and Irreducible Polynomials

2022-08-27T15:55:03Z

Guenter moved page Aufgabe 2.3: Reduzible und irreduzible Polynome to Exercise 2.3: Reducible and Irreducible Polynomials

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

2021-05-28T14:25:23Z

Text replacement - "„" to """

@@ Line 83: / Line 83: @@
 ===Solution===
 {{ML-Kopf}}
-'''(1)'''&nbsp; The polynomial $a(x) = a_0 + a_1 \cdot x + a_2 \cdot x^2 + \hspace{0.1cm}... \hspace{0.1cm} + a_m \cdot x^{m}$
+'''(1)'''&nbsp; The polynomial&nbsp; $a(x) = a_0 + a_1 \cdot x + a_2 \cdot x^2 + \hspace{0.1cm}... \hspace{0.1cm} + a_m \cdot x^{m}$
-*with $a_m = 1$
+*with&nbsp; $a_m = 1$
-*and given coefficients $a_0, \ a_1, \hspace{0.05cm}\text{ ...} \hspace{0.1cm} , \ a_{m-1}$ ($0$ or $1$ in each case).
-is irreducible if there is no single polynomial $q(x)$ such that the modulo $2$ division $a(x)/q(x)$ yields no remainder. The degree of all divisor polynomials $q(x)$ to be considered is at least $1$ and at most $m-1$.
+is irreducible if there is no single polynomial&nbsp; $q(x)$&nbsp; such that the modulo&nbsp; $2$&nbsp; division&nbsp; $a(x)/q(x)$&nbsp; yields no remainder.&nbsp; The degree of all divisor polynomials&nbsp; $q(x)$&nbsp; to be considered is at least&nbsp; $1$&nbsp; and at most&nbsp; $m-1$.
-* For $m = 2$ two polynomial divisions $a(x)/q_i(x)$ are necessary, namely with
+* For&nbsp; $m = 2$&nbsp; two polynomial divisions&nbsp; $a(x)/q_i(x)$&nbsp; are necessary,&nbsp; namely with
 :$$q_1(x) = x \hspace{0.5cm}{\rm and}\hspace{0.5cm}q_2(x) = x+1
 \hspace{0.3cm} \Rightarrow\hspace{0.3cm}N_{\rm D}\hspace{0.15cm}\underline{= 2}
 \hspace{0.05cm}.$$
-* For $m = 3$ there are already $N_{\rm D} \ \underline{= 6}$ divisor polynomials, namely besides $q_1(x) = x$ and $q_2(x) = x + 1$ also
+* For&nbsp; $m = 3$&nbsp; there are already&nbsp; $N_{\rm D} \ \underline{= 6}$&nbsp; divisor polynomials,&nbsp; namely besides&nbsp; $q_1(x) = x$&nbsp; and&nbsp; $q_2(x) = x + 1$&nbsp; also
 :$$q_3(x) = x^2\hspace{0.05cm},\hspace{0.2cm}q_4(x) = x^2+1\hspace{0.05cm},\hspace{0.2cm}
 q_5(x) = x^2 + x\hspace{0.05cm},\hspace{0.2cm}q_6(x) = x^2+x+1\hspace{0.05cm}.$$
-* For $m = 4$, besides $q_1(x), \hspace{0.05cm}\text{ ...} \hspace{0.1cm} , \ q_6(x)$ all possible divisor polynomials with degree $m = 3$ must also be considered, thus:
+* For&nbsp; $m = 4$,&nbsp; besides&nbsp; $q_1(x), \hspace{0.05cm}\text{ ...} \hspace{0.1cm} , \ q_6(x)$&nbsp; all possible divisor polynomials with degree&nbsp; $m = 3$&nbsp; must also be considered,&nbsp; thus:
 :$$q_i(x) =  a_0 + a_1 \cdot x + a_2 \cdot x^2 + x^3\hspace{0.05cm},\hspace{0.5cm}a_0, a_1, a_2 \in \{0,1\}
 \hspace{0.05cm}.$$
@@ Line 104: / Line 105: @@
-'''(2)'''&nbsp; For the first polynomial holds: $a_1(x = 0) = 0$. Therefore this polynomial is reducible: $a_1(x) = x \cdot (x + 1)$.
+'''(2)'''&nbsp; For the first polynomial holds:&nbsp; $a_1(x = 0) = 0$.&nbsp; Therefore this polynomial is reducible:
-On the other hand, the following is true for the second polynomial:
+On the other hand,&nbsp; the following is true for the second polynomial:
 :$$a_2(x = 0) = 1\hspace{0.05cm},\hspace{0.2cm}a_2(x = 1) = 1
 \hspace{0.05cm}.$$
-This necessary but not sufficient property shows that $a_2(x)$ could be irreducible. The final proof is obtained only by two modulo 2 divisions:
+This necessary but not sufficient property shows that&nbsp; $a_2(x)$&nbsp; could be irreducible.&nbsp; The final proof is obtained only by two modulo-2 divisions:
-* $a_2(x)$ divided by $x$ yields $x + 1$, remainder $r(x) = 1$,
+* $a_2(x)$&nbsp; divided by&nbsp; $x$&nbsp; yields&nbsp; $x + 1$,&nbsp; remainder&nbsp; $r(x) = 1$,
 '''(3)'''&nbsp; The first three polynomials are reducible, as the following calculation results show:
 :$$a_3(x = 0) = 0\hspace{0.05cm},\hspace{0.2cm}a_4(x = 1) = 0\hspace{0.05cm},\hspace{0.2cm}a_5(x = 0) = 0\hspace{0.05cm},\hspace{0.2cm}a_5(x = 1) = 0
 \hspace{0.05cm}.$$
@@ Line 127: / Line 130: @@
 :$$a_5(x)  \hspace{-0.15cm} \ = \ \hspace{-0.15cm} x \cdot (x + 1)\cdot(x + 1) \hspace{0.05cm}.$$
-The polynomial $a_6(x)$ is not equal to $0$ for both $x = 0$ and $x = 1$. This means that
+The polynomial&nbsp; $a_6(x)$&nbsp; is not equal to&nbsp; $0$&nbsp; for both&nbsp; $x = 0$&nbsp; and&nbsp; $x = 1$&nbsp;. This means that
-* "nothing speaks against" $a_6(x)$ being irreducible,
+* "nothing speaks against"&nbsp; $a_6(x)$&nbsp; being irreducible,
-* division by the irreducible degree 1 polynomials $x$ and $x + 1$, respectively, is not possible without remainder.
+* division by the irreducible degree-1 polynomials&nbsp; $x$&nbsp; and&nbsp; $x + 1$,&nbsp; respectively,&nbsp; is not possible without remainder.
-However, since division by the single irreducible degree 2 polynomial also yields a remainder, it is proved that $a_6(x)$ is an irreducible polynomial:
+However,&nbsp; since division by the single irreducible degree-2 polynomial also yields a remainder,&nbsp; it is proved that&nbsp; $a_6(x)$&nbsp; is an irreducible polynomial:
 :$$(x^3 + x+1)/(x^2 + x+1) = x + 1 \hspace{0.05cm},\hspace{0.4cm}{\rm Rest}\hspace{0.15cm} r(x) = x\hspace{0.05cm},$$
-Using the same computational procedure, it can also be shown that $a_7(x)$ is also irreducible &nbsp; &#8658; &nbsp; <u>Solutions 4 and 5</u>.
+Using the same computational procedure,&nbsp; it can also be shown that&nbsp; $a_7(x)$&nbsp; is also irreducible &nbsp; &#8658; &nbsp; <u>Solutions 4 and 5</u>.
-'''(4)'''&nbsp; From $a_8(x + 1) = 0$ follows the reducibility of $a_8(x)$. For the other two polynomials, however, holds:
+'''(4)'''&nbsp; From&nbsp; $a_8(x + 1) = 0$&nbsp; follows the reducibility of&nbsp; $a_8(x)$.&nbsp; For the other two polynomials,&nbsp; however,&nbsp; holds:
 :$$a_9(x = 0)  \hspace{-0.15cm} \ = \ \hspace{-0.15cm} 1\hspace{0.05cm},\hspace{0.35cm}a_9(x = 1) = 1  \hspace{0.05cm},$$
 :$$a_{10}(x = 0)  \hspace{-0.15cm} \ = \ \hspace{-0.15cm}1\hspace{0.05cm},\hspace{0.2cm}a_{10}(x = 1) = 1  \hspace{0.05cm}.$$
-So both could be irreducible. The exact proof of irreducibility is more complicated:
+So both could be irreducible.&nbsp; The exact proof of irreducibility is more complicated:
-*It is not necessary to use all four divisor polynomials with degree $m = 2$, namely $x^2, \ x^2 + 1, \ x^2 + x + 1$, but it is sufficient to divide by the only irreducible degree 2 polynomial. One obtains with respect to the polynomial $a_9(x)$:
+*It is not necessary to use all four divisor polynomials with degree&nbsp; $m = 2$,&nbsp; namely $x^2, \ x^2 + 1, \ x^2 + x + 1$,&nbsp; but it is sufficient to divide by the only irreducible degree-2 polynomial.&nbsp; One obtains with respect to the polynomial&nbsp; $a_9(x)$:
-:$$(x^4 + x^3+1)/(x^2 + x+1) = x^2 + 1 \hspace{0.05cm},\hspace{0.4cm}{\rm Rest}\hspace{0.15cm} r(x) = x\hspace{0.05cm}.$$
+:$$(x^4 + x^3+1)/(x^2 + x+1) = x^2 + 1 \hspace{0.05cm},\hspace{0.4cm}{\rm remainder}\hspace{0.15cm} r(x) = x\hspace{0.05cm}.$$
-Also the division by the two irreducible degree 3 polynomials yields a remainder in each case:
+Also the division by the two irreducible degree-3 polynomials yields a remainder in each case:
-:$$(x^4 + x^3+1)/(x^3 + x+1) \hspace{-0.15cm} \ = \ \hspace{-0.15cm} x + 1 \hspace{0.05cm},\hspace{0.4cm}{\rm Rest}\hspace{0.15cm} r(x) = x^2\hspace{0.05cm},$$
+:$$(x^4 + x^3+1)/(x^3 + x+1) \hspace{-0.15cm} \ = \ \hspace{-0.15cm} x + 1 \hspace{0.05cm},\hspace{0.4cm}{\rm remainder}\hspace{0.15cm} r(x) = x^2\hspace{0.05cm},$$
-:$$(x^4 + x^3+1)/(x^3 + x^2+1) \hspace{-0.15cm} \ = \ \hspace{-0.15cm} x  \hspace{0.05cm},\hspace{0.95cm}{\rm Rest}\hspace{0.15cm} r(x) = x +1\hspace{0.05cm}.$$
+:$$(x^4 + x^3+1)/(x^3 + x^2+1) \hspace{-0.15cm} \ = \ \hspace{-0.15cm} x  \hspace{0.05cm},\hspace{0.95cm}{\rm remainder}\hspace{0.15cm} r(x) = x +1\hspace{0.05cm}.$$
-Finally, let us consider the polynomial $a_{10}(x) = x^4 + x^2 + 1$. Here holds
+Finally,&nbsp; let us consider the polynomial&nbsp; $a_{10}(x) = x^4 + x^2 + 1$.&nbsp; Here holds
-:$$(x^4 + x^2+1)/(x^2 + x+1) = x^2 + x+1 \hspace{0.05cm},\hspace{0.4cm}{\rm Rest}\hspace{0.15cm} r(x) = 0\hspace{0.05cm}.$$
+:$$(x^4 + x^2+1)/(x^2 + x+1) = x^2 + x+1 \hspace{0.05cm},\hspace{0.4cm}{\rm remainder}\hspace{0.15cm} r(x) = 0\hspace{0.05cm}.$$
-It follows: Only the polynomial $a_9(x)$ is irreducible &nbsp;&#8658;&nbsp; <u>proposed solution 2</u>.
+It follows:&nbsp; Only the polynomial&nbsp; $a_9(x)$&nbsp; is irreducible &nbsp; &#8658; &nbsp; <u>proposed solution 2</u>.
 {{ML-Fuß}}

@@ Line 1: / Line 1: @@
 {{quiz-Header|Buchseite=Channel_Coding/Extension_Field}}
-[[File:P_ID2503__KC_A_2_3.png|right|frame|Polynomials of degree&nbsp; $m = 2$,&nbsp; $m = 3$&nbsp; and&nbsp; $m = 4$]]
+[[File:P_ID2503__KC_A_2_3.png|right|frame|Polynomials of degree&nbsp; $m = 2$,&nbsp; $m = 3$,&nbsp; $m = 4$]]
-Important prerequisites for understanding channel coding are knowledge of polynomial properties. In this exercise we consider polynomials of the form
+Important prerequisites for understanding channel coding are knowledge of polynomial properties.
 :$$a(x) =  a_0 + a_1 \cdot x + a_2 \cdot x^2 + \hspace{0.1cm}... \hspace{0.1cm} + a_m \cdot x^{m}
 \hspace{0.05cm},$$
-where for the coefficients&nbsp; $a_i &#8712; {\rm GF}(2) = \{0, \, 1\}$&nbsp; holds&nbsp; $(0 &#8804; i &#8804; m)$ and the highest coefficient is always assumed to&nbsp; $a_m = 1$&nbsp;. One refers to&nbsp; $m$&nbsp; as the ''degree''&nbsp; of the polynomial. Adjacent are ten polynomials where the polynomial degree is either&nbsp; $m = 2$&nbsp; (red font),&nbsp; $m = 3$&nbsp; (blue font) or&nbsp; $m = 4$&nbsp; (green font).
+*where for the coefficients&nbsp; $a_i &#8712; {\rm GF}(2) = \{0, \, 1\}$&nbsp; holds&nbsp; $(0 &#8804; i &#8804; m)$
-A polynomial&nbsp; $a(x)$&nbsp; is called <b>reducible</b> if it can be represented as the product of two polynomials&nbsp; $p(x)$&nbsp; and&nbsp; $q(x)$&nbsp; each of lower degree:
+A polynomial&nbsp; $a(x)$&nbsp; is called&nbsp; <b>reducible</b>&nbsp; if it can be represented as the product of two polynomials&nbsp; $p(x)$&nbsp; and&nbsp; $q(x)$&nbsp; of lower degree:
 :$$a(x) = p(x) \cdot q(x)$$
-If this is not possible, that is, if for the polynomial
+If this splitting is not possible,&nbsp; that is,&nbsp; if for the polynomial
 :$$a(x) = p(x) \cdot q(x) + r(x)$$
-with a residual polynomial&nbsp; $r(x) &ne; 0$&nbsp; holds, then the polynomial is called irreducible. Such irreducible polynomials are of special importance for the description of error correction methods.
+with a residual polynomial&nbsp; $r(x) &ne; 0$&nbsp; holds,&nbsp; then the polynomial is called&nbsp; '''irreducible'''.&nbsp; Such irreducible polynomials are of special importance for the description of error correction methods.
-The proof that a polynomial&nbsp; $a(x)$&nbsp; of degree&nbsp; $m$&nbsp; is irreducible requires several polynomial divisions&nbsp; $a(x)/q(x)$, where the degree of the respective divisor polynomial&nbsp; $q(x)$&nbsp; is always smaller than&nbsp; $m$. Only if all these modulo $2$ divisions always yield a remainder&nbsp; $r(x) &ne; 0$&nbsp; is it proved that&nbsp; $a(x)$&nbsp; is indeed an irreducible polynomial.
+&rArr; &nbsp; The proof that a polynomial&nbsp; $a(x)$&nbsp; of degree&nbsp; $m$&nbsp; is irreducible requires several polynomial divisions&nbsp; $a(x)/q(x)$,&nbsp; where the degree of the respective divisor polynomial&nbsp; $q(x)$&nbsp; is always smaller than&nbsp; $m$. &nbsp; Only if all these  divisions&nbsp; $($modulo $2)$&nbsp; always yield a remainder&nbsp; $r(x) &ne; 0$&nbsp; it is proved that&nbsp; $a(x)$&nbsp; is indeed an irreducible polynomial.
-This exact proof is very complex. Necessary conditions for&nbsp; $a(x)$&nbsp; to be an irreducible polynomial at all are the two conditions (in nonbinary approach "$x=1$" would have to be replaced by "$x&ne;0$"):
+&rArr; &nbsp; This exact proof is very complex.&nbsp; Necessary conditions for&nbsp; $a(x)$&nbsp; to be an irreducible polynomial at all are the two conditions&nbsp; $($in nonbinary approach&nbsp; "$x=1$"&nbsp; would have to be replaced by&nbsp; "$x&ne;0$"$)$:
 * $a(x = 0) = 1$,
 * $a(x = 1) = 1$.
-Otherwise, one could write for the polynomial under investigation:
+Otherwise,&nbsp; one could write for the polynomial under investigation:
-:$$a(x) = q(x) \cdot x \hspace{0.5cm}{\rm bzw.}\hspace{0.5cm}a(x) = q(x) \cdot (x+1)\hspace{0.05cm}.$$
+:$$a(x) = q(x) \cdot x \hspace{0.5cm}{\rm resp.}\hspace{0.5cm}a(x) = q(x) \cdot (x+1)\hspace{0.05cm}.$$
-The above conditions are necessary, but not sufficient, as the following example shows:
+The above conditions are necessary,&nbsp; but not sufficient,&nbsp; as the following example shows:
 :$$a(x) = x^5 + x^4 +1 \hspace{0.3cm} \Rightarrow\hspace{0.3cm}a(x = 0) = 1\hspace{0.05cm},\hspace{0.2cm}a(x = 1) = 1
 \hspace{0.05cm}.$$
-Nevertheless, this polynomial is reducible:
+Nevertheless,&nbsp; this polynomial is reducible:
 :$$a(x) = (x^3 + x +1)(x^2 + x +1) \hspace{0.05cm}.$$
+Hint:&nbsp; This exercise belongs to the chapter&nbsp; [[Channel_Coding/Extension_Field| "Extension field"]].
@@ Line 50: / Line 61: @@
 $m = 4 \text{:} \hspace{0.35cm} N_{\rm D} \ = \ ${ 14 3% }
-{Which of the degree 2 polynomials are irreducible?
+{Which of the degree&ndash;2 polynomials are irreducible?
 |type="[]"}
 - $a_1(x) = x^2 + x$,
 + $a_2(x) = x^2 + x + 1$.
-{Which of the degree 3 polynomials are irreducible?
+{Which of the degree&ndash;3 polynomials are irreducible?
 |type="[]"}
 - $a_3(x) = x^3$,
@@ Line 63: / Line 74: @@
 + $a_7(x) = x^3 + x^2 + 1$.
-{Which of the degree 4 polynomials are irreducible?
+{Which of the degree&ndash;4 polynomials are irreducible?
 |type="[]"}
 - $a_8(x) = x^4 + 1$,

@@ Line 104: / Line 104: @@
-The correct solution is therefore <u>solution suggestion 2</u>.
+The correct solution is therefore <u>proposed solution 2</u>.
@@ Line 142: / Line 142: @@
 :$$(x^4 + x^2+1)/(x^2 + x+1) = x^2 + x+1 \hspace{0.05cm},\hspace{0.4cm}{\rm Rest}\hspace{0.15cm} r(x) = 0\hspace{0.05cm}.$$
-It follows: Only the polynomial $a_9(x)$ is irreducible &nbsp;&#8658;&nbsp; <u>Solution suggestion2</u>.
+It follows: Only the polynomial $a_9(x)$ is irreducible &nbsp;&#8658;&nbsp; <u>proposed solution 2</u>.
 {{ML-Fuß}}

← Older revision		Revision as of 12:51, 31 August 2022
Line 37:		Line 37:


−	~~Hints~~:	+	Hint:
	* This exercise belongs to the chapter  [[Channel_Coding/Extension_Field\| "Extension field"]].		* This exercise belongs to the chapter  [[Channel_Coding/Extension_Field\| "Extension field"]].

← Older revision		Revision as of 12:29, 31 August 2022
Line 38:		Line 38:

	Hints:		Hints:
−	* This exercise belongs to the chapter  [[Channel_Coding/Extension_Field\| Extension field]].	+	* This exercise belongs to the chapter  [[Channel_Coding/Extension_Field\| "Extension field"]].

← Older revision		Revision as of 16:56, 27 August 2022
Line 147:		Line 147:


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

@@ Line 18: / Line 18: @@
 Der Nachweis, dass ein Polynom&nbsp; $a(x)$&nbsp; vom Grad&nbsp; $m$&nbsp; irreduzibel ist, erfordert mehrere Polynomdivisionen&nbsp; $a(x)/q(x)$, wobei der Grad des jeweiligen Divisorpolynoms&nbsp; $q(x)$&nbsp; stets kleiner ist als&nbsp; $m$. Nur wenn alle diese Modulo&ndash;$2$&ndash;Divisionen stets einen Rest&nbsp; $r(x) &ne; 0$&nbsp; liefern, ist nachgewiesen, dass&nbsp; $a(x)$&nbsp; tatsächlich ein irreduzibles Polynom ist.
-Dieser exakte Nachweis ist sehr aufwändig. Notwendige Voraussetzungen dafür, dass&nbsp; $a(x)$&nbsp; überhaupt ein irreduzibles Polynom sein könnte, sind die beiden Bedingungen (bei nichtbinärer Betrachtungsweise wäre &bdquo;$x=1$" durch &bdquo;$x&ne;0$" zu ersetzen):
+Dieser exakte Nachweis ist sehr aufwändig. Notwendige Voraussetzungen dafür, dass&nbsp; $a(x)$&nbsp; überhaupt ein irreduzibles Polynom sein könnte, sind die beiden Bedingungen (bei nichtbinärer Betrachtungsweise wäre "$x=1$" durch "$x&ne;0$" zu ersetzen):
 * $a(x = 0) = 1$,
 * $a(x = 1) = 1$.
@@ Line 117: / Line 117: @@
 Das Polynom $a_6(x)$ ist sowohl für $x = 0$ als auch für $x = 1$ ungleich $0$. Das heißt, dass
-* &bdquo;nichts dagegen spricht", dass $a_6(x)$ irreduzibel ist,
+* "nichts dagegen spricht", dass $a_6(x)$ irreduzibel ist,
 * die Division durch die irreduziblen Grad&ndash;1&ndash;Polynome $x$ bzw. $x + 1$ nicht ohne Rest möglich ist.