Aufgaben:Aufgabe 2.3: Reduzible und irreduzible Polynome: Unterschied zwischen den Versionen

Aus LNTwww
Wechseln zu:Navigation, Suche
 
(Eine dazwischenliegende Version desselben Benutzers wird nicht angezeigt)
Zeile 1: Zeile 1:
 
{{quiz-Header|Buchseite=Kanalcodierung/Erweiterungskörper}}
 
{{quiz-Header|Buchseite=Kanalcodierung/Erweiterungskörper}}
  
[[Datei:P_ID2503__KC_A_2_3.png|right|frame|Polynome von Grad  $m = 2$,  $m = 3$  und  $m = 4$]]
+
[[Datei:P_ID2503__KC_A_2_3.png|right|frame|Einige Polynome von Grad  $m = 2$,  $m = 3$,  $m = 4$]]
Wichtige Voraussetzungen für das Verständnis der Kanalcodierung sind Kenntnisse der Polynomeigenschaften. Wir betrachten in dieser Aufgabe Polynome der Form
+
Wichtige Voraussetzungen für das Verständnis der Kanalcodierung sind Kenntnisse der Polynomeigenschaften. 
 +
 
 +
Wir betrachten in dieser Aufgabe Polynome der Form
 
:$$a(x) =  a_0 + a_1 \cdot x + a_2 \cdot x^2 + \hspace{0.1cm}... \hspace{0.1cm} + a_m \cdot x^{m}
 
:$$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},$$
 
\hspace{0.05cm},$$
  
wobei für die Koeffizienten  $a_i ∈ {\rm GF}(2) = \{0, \, 1\}$  gilt  $(0 ≤ i ≤ m)$ und der höchste Koeffizient stets zu  $a_m = 1$  vorausgesetzt wird. Man bezeichnet  $m$  als den ''Grad''  des Polynoms. Nebenstehend sind zehn Polynome angegeben, wobei der Polynomgrad entweder  $m = 2$  (rote Schrift),  $m = 3$  (blaue Schrift) oder  $m = 4$  (grüne Schrift) ist.
+
*wobei für die Koeffizienten  $a_i ∈ {\rm GF}(2) = \{0, \, 1\}$  gilt  $(0 ≤ i ≤ m)$  
  
Ein Polynom&nbsp; $a(x)$&nbsp; bezeichnet man als <b>reduzibel</b>, wenn es als Produkt zweier Polynome&nbsp; $p(x)$&nbsp; und&nbsp; $q(x)$&nbsp; mit jeweils niedrigerem Grad dargestellt werden kann:
+
*und der höchste Koeffizient stets zu&nbsp; $a_m = 1$&nbsp; vorausgesetzt wird.
 +
 
 +
 
 +
Man bezeichnet&nbsp; $m$&nbsp; als den&nbsp; "Grad"&nbsp; des Polynoms.&nbsp; Nebenstehend sind zehn Polynome angegeben,&nbsp; mit den Polynomgraden
 +
*$m = 2$&nbsp; (rote Schrift),&nbsp;
 +
*$m = 3$&nbsp; (blaue Schrift) oder&nbsp;
 +
*$m = 4$&nbsp; (grüne Schrift).
 +
 
 +
 
 +
Ein Polynom&nbsp; $a(x)$&nbsp; bezeichnet man als&nbsp; <b>reduzibel</b>,&nbsp; wenn es als Produkt zweier Polynome&nbsp; $p(x)$&nbsp; und&nbsp; $q(x)$&nbsp; mit jeweils niedrigerem Grad dargestellt werden kann:
 
:$$a(x) = p(x) \cdot q(x)$$
 
:$$a(x) = p(x) \cdot q(x)$$
  
Ist dies nicht möglich, das heißt, wenn für das Polynom  
+
Ist dies nicht möglich,&nbsp; das heißt,&nbsp; wenn für das Polynom  
 
:$$a(x) = p(x) \cdot q(x) + r(x)$$
 
:$$a(x) = p(x) \cdot q(x) + r(x)$$
  
mit einem Restpolynom&nbsp; $r(x) &ne; 0$&nbsp; gilt, so nennt an das Polynom <b>irreduzibel</b>. Solche irreduziblen Polynome sind für die Beschreibung von Fehlerkorrekturverfahren von besonderer Bedeutung.
+
mit einem Restpolynom&nbsp; $r(x) &ne; 0$&nbsp; gilt,&nbsp; so nennt an das Polynom&nbsp; <b>irreduzibel</b>.&nbsp; Solche irreduziblen Polynome sind für die Beschreibung von Fehlerkorrekturverfahren von besonderer Bedeutung.
  
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.
+
&rArr; &nbsp; Der Nachweis,&nbsp; dass ein Polynom&nbsp; $a(x)$&nbsp; vom Grad&nbsp; $m$&nbsp; irreduzibel ist,&nbsp; erfordert mehrere Polynomdivisionen&nbsp; $a(x)/q(x)$,&nbsp; wobei der Grad des 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,&nbsp; ist nachgewiesen,&nbsp; 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$&rdquo; durch &bdquo;$x&ne;0$&rdquo; zu ersetzen):
+
&rArr; &nbsp; Dieser exakte Nachweis ist sehr aufwändig.&nbsp; Notwendige Voraussetzungen dafür,&nbsp; dass&nbsp; $a(x)$&nbsp; überhaupt ein irreduzibles Polynom sein könnte,&nbsp; sind die beiden Bedingungen&nbsp; $($bei nichtbinärer Betrachtungsweise wäre &bdquo;$x=1$&rdquo; durch &bdquo;$x&ne;0$&rdquo; zu ersetzen$)$:
 
* $a(x = 0) = 1$,
 
* $a(x = 0) = 1$,
 +
 
* $a(x = 1) = 1$.
 
* $a(x = 1) = 1$.
  
Zeile 26: Zeile 38:
 
:$$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 bzw.}\hspace{0.5cm}a(x) = q(x) \cdot (x+1)\hspace{0.05cm}.$$
  
Die oben genannten Voraussetzungen sind zwar notwendig, jedoch nicht hinreichend, wie das folgende Beispiel zeigt:
+
Die oben genannten Voraussetzungen sind zwar notwendig,&nbsp; jedoch nicht hinreichend,&nbsp; wie das folgende Beispiel zeigt:
 
:$$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
 
:$$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}.$$
 
\hspace{0.05cm}.$$
  
Trotzdem ist dieses Polynom reduzibel:
+
Trotzdem ist dieses Polynom nämlich reduzibel:
 
:$$a(x) = (x^3 + x +1)(x^2 + x +1) \hspace{0.05cm}.$$
 
:$$a(x) = (x^3 + x +1)(x^2 + x +1) \hspace{0.05cm}.$$
  
Zeile 37: Zeile 49:
  
  
''Hinweis:''
+
Hinweis:&nbsp; Die Aufgabe gehört zum Kapitel&nbsp; [[Kanalcodierung/Erweiterungsk%C3%B6rper| "Erweiterungskörper"]].
* Die Aufgabe gehört zum Kapitel&nbsp; [[Kanalcodierung/Erweiterungsk%C3%B6rper| Erweiterungskörper]].
 
  
  
Zeile 44: Zeile 55:
 
===Fragebogen===
 
===Fragebogen===
 
<quiz display=simple>
 
<quiz display=simple>
{Wieviele Polynomdivisionen&nbsp; $(N_{\rm D})$&nbsp; sind erforderlich, um exakt nachzuweisen, dass ein&nbsp; ${\rm GF}(2)$&ndash;Polynom&nbsp; $a(x)$&nbsp; vom Grad&nbsp; $m$&nbsp; irreduzibel ist?
+
{Wieviele Polynomdivisionen&nbsp; $(N_{\rm D})$&nbsp; sind erforderlich,&nbsp; um exakt nachzuweisen,&nbsp; dass ein&nbsp; ${\rm GF}(2)$&ndash;Polynom&nbsp; $a(x)$&nbsp; vom Grad&nbsp; $m$&nbsp; irreduzibel ist?
 
|type="{}"}
 
|type="{}"}
 
$m = 2 \text{:} \hspace{0.35cm} N_{\rm D} \ = \ ${ 2 3% }
 
$m = 2 \text{:} \hspace{0.35cm} N_{\rm D} \ = \ ${ 2 3% }
Zeile 72: Zeile 83:
 
===Musterlösung===
 
===Musterlösung===
 
{{ML-Kopf}}
 
{{ML-Kopf}}
'''(1)'''&nbsp; Das Polynom $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; Das Polynom&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}$
*mit $a_m = 1$  
+
*mit&nbsp; $a_m = 1$
*und gegebenen Koeffizienten $a_0, \ a_1, \hspace{0.05cm}\text{ ...} \hspace{0.1cm} , \ a_{m-1}$ (jeweils $0$ oder $1$)
+
 +
*und gegebenen Koeffizienten&nbsp; $a_0, \ a_1, \hspace{0.05cm}\text{ ...} \hspace{0.1cm} , \ a_{m-1}$&nbsp; $($jeweils&nbsp; $0$&nbsp; oder&nbsp; $1)$  
  
  
ist dann irreduzibel, wenn es kein einziges Polynom $q(x)$ gibt, so dass die Modulo&ndash;$2$&ndash;Division $a(x)/q(x)$ keinen Rest ergibt. Der Grad aller zu betrachtenden Teilerpolynome $q(x)$ ist mindestens $1$ und höchstens $m-1$.
+
ist dann irreduzibel,&nbsp; wenn es kein einziges Polynom&nbsp; $q(x)$&nbsp; gibt,&nbsp; so dass die Modulo&ndash;2&ndash;Division &nbsp; $a(x)/q(x)$ &nbsp; keinen Rest ergibt.&nbsp; Der Grad aller zu betrachtenden Teilerpolynome&nbsp; $q(x)$&nbsp; ist dabei mindestens&nbsp; $1$&nbsp; und höchstens&nbsp; $m-1$.
* Für $m = 2$ sind zwei Polynomdivisionen $a(x)/q_i(x)$ erforderlich, nämlich mit
+
* Für&nbsp; $m = 2$&nbsp; sind zwei Polynomdivisionen&nbsp; $a(x)/q_i(x)$&nbsp; erforderlich,&nbsp; nämlich mit
 
:$$q_1(x) = x \hspace{0.5cm}{\rm und}\hspace{0.5cm}q_2(x) = x+1
 
:$$q_1(x) = x \hspace{0.5cm}{\rm und}\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.3cm} \Rightarrow\hspace{0.3cm}N_{\rm D}\hspace{0.15cm}\underline{= 2}
 
\hspace{0.05cm}.$$
 
\hspace{0.05cm}.$$
* Für $m = 3$ gibt es schon $N_{\rm D} \ \underline{= 6}$ Teilerpolynome, nämlich neben $q_1(x) = x$ und $q_2(x) = x + 1$ noch
+
* Für&nbsp; $m = 3$&nbsp; gibt es schon&nbsp; $N_{\rm D} \ \underline{= 6}$&nbsp; Teilerpolynome,&nbsp; nämlich neben&nbsp; $q_1(x) = x$&nbsp; und&nbsp; $q_2(x) = x + 1$&nbsp; noch
 
:$$q_3(x) = x^2\hspace{0.05cm},\hspace{0.2cm}q_4(x) = x^2+1\hspace{0.05cm},\hspace{0.2cm}
 
:$$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}.$$
 
q_5(x) = x^2 + x\hspace{0.05cm},\hspace{0.2cm}q_6(x) = x^2+x+1\hspace{0.05cm}.$$
  
* Für $m = 4$ müssen außer $q_1(x), \hspace{0.05cm}\text{ ...} \hspace{0.1cm} , \ q_6(x)$ auch noch alle möglichen Teilerpolynome mit Grad $m = 3$ berücksichtigt werden, also:
+
* Für&nbsp; $m = 4$&nbsp; müssen außer&nbsp; $q_1(x), \hspace{0.05cm}\text{ ...} \hspace{0.1cm} , \ q_6(x)$&nbsp; auch noch alle möglichen Teilerpolynome mit Grad&nbsp; $m = 3$&nbsp; berücksichtigt werden,&nbsp; also:
:$$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\}  
+
:$$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}.$$
 
\hspace{0.05cm}.$$
  
:Für den Index gilt dabei $7 &#8804; i &#8804; 14 \ \Rightarrow \ N_{\rm D} \ \underline{= 14}$.
+
:Für den Index gilt dabei&nbsp; $7 &#8804; i &#8804; 14 \ \Rightarrow \ N_{\rm D} \ \underline{= 14}$.
  
  
'''(2)'''&nbsp; Für das erste Polynom gilt: $a_1(x = 0) = 0$. Deshalb ist dieses Polynom reduzibel: &nbsp; $a_1(x) = x \cdot (x + 1)$.
+
'''(2)'''&nbsp; Für das erste Polynom gilt:&nbsp; $a_1(x = 0) = 0$.&nbsp; Deshalb ist dieses Polynom reduzibel: &nbsp;  
 +
:$$a_1(x) = x \cdot (x + 1).$$
  
 
Dagegen gilt für das zweite Polynom:
 
Dagegen gilt für das zweite Polynom:
Zeile 99: Zeile 112:
 
\hspace{0.05cm}.$$
 
\hspace{0.05cm}.$$
  
Diese notwendige, aber nicht hinreichende Eigenschaft zeigt, dass $a_2(x)$ irreduzibel sein könnte. Der endgültige Beweis ergibt sich erst durch zwei Modulo&ndash;2&ndash;Divisionen:
+
Diese notwendige,&nbsp; aber nicht hinreichende Eigenschaft zeigt,&nbsp; dass&nbsp; $a_2(x)$&nbsp; irreduzibel sein könnte.&nbsp;
* $a_2(x)$ geteilt durch $x$ liefert $x + 1$, Rest $r(x) = 1$,
+
 
* $a_2(x)$ geteilt durch $x + 1$ liefert $x$, Rest $r(x) = 1$.
+
Der endgültige Beweis ergibt sich erst durch zwei Modulo&ndash;2&ndash;Divisionen:
 +
* $a_2(x)$&nbsp; geteilt durch&nbsp; $x$&nbsp; liefert&nbsp; $x + 1$,&nbsp; Rest $r(x) = 1$,
 +
 
 +
* $a_2(x)$&nbsp; geteilt durch&nbsp; $x + 1$&nbsp; liefert&nbsp; $x$,&nbsp; Rest $r(x) = 1$.
  
  
Richtig ist demnach der <u>Lösungsvorschlag 2</u>.
+
Richtig ist demnach der&nbsp; <u>Lösungsvorschlag 2</u>.
  
  
'''(3)'''&nbsp; Die drei ersten Polynome sind reduzibel, wie die folgenden Rechenergebnisse zeigen:
+
'''(3)'''&nbsp; Die drei ersten Polynome sind reduzibel,&nbsp; wie die folgenden Rechenergebnisse zeigen:
 
:$$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
 
:$$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}.$$
 
\hspace{0.05cm}.$$
Zeile 116: Zeile 132:
 
:$$a_5(x)  \hspace{-0.15cm} \ = \ \hspace{-0.15cm} x \cdot (x + 1)\cdot(x + 1) \hspace{0.05cm}.$$
 
:$$a_5(x)  \hspace{-0.15cm} \ = \ \hspace{-0.15cm} x \cdot (x + 1)\cdot(x + 1) \hspace{0.05cm}.$$
  
Das Polynom $a_6(x)$ ist sowohl für $x = 0$ als auch für $x = 1$ ungleich $0$. Das heißt, dass  
+
Das Polynom&nbsp; $a_6(x)$&nbsp; ist sowohl für&nbsp; $x = 0$&nbsp; als auch für&nbsp; $x = 1$&nbsp; ungleich&nbsp; $0$.&nbsp; Das heißt,&nbsp; dass  
* &bdquo;nichts dagegen spricht&rdquo;, dass $a_6(x)$ irreduzibel ist,
+
* &bdquo;nichts dagegen spricht&rdquo;,&nbsp; dass $a_6(x)$&nbsp; irreduzibel ist,
* die Division durch die irreduziblen Grad&ndash;1&ndash;Polynome $x$ bzw. $x + 1$ nicht ohne Rest möglich ist.
+
 
 +
* die Division durch die irreduziblen Grad&ndash;1&ndash;Polynome&nbsp; $x$&nbsp; bzw.&nbsp; $x + 1$&nbsp; nicht ohne Rest möglich ist.
  
  
Da aber auch die Division durch das einzige irreduzible Grad&ndash;2&ndash;Polynom einen Rest liefert, ist bewiesen, dass $a_6(x)$ ein irreduzibles Polynom ist:  
+
Da aber auch die Division durch das einzige irreduzible Grad&ndash;2&ndash;Polynom einen Rest liefert,&nbsp; ist bewiesen,&nbsp; dass&nbsp; $a_6(x)$&nbsp; ein irreduzibles Polynom ist:  
 
:$$(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},$$
 
:$$(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},$$
  
Mit gleichem Rechengang kann auch gezeigt werden, dass $a_7(x)$ ebenfalls irreduzibel ist &nbsp; &#8658; &nbsp; <u>Lösungsvorschläge 4 und 5</u>.
+
Mit gleichem Rechengang kann auch gezeigt werden, dass&nbsp; $a_7(x)$&nbsp; ebenfalls irreduzibel ist &nbsp; &#8658; &nbsp; <u>Lösungsvorschläge 4 und 5</u>.
  
  
'''(4)'''&nbsp; Aus $a_8(x + 1) = 0$ folgt die Reduzibilität von $a_8(x)$. Für die beiden anderen Polynome gilt dagegen:
+
'''(4)'''&nbsp; Aus&nbsp; $a_8(x + 1) = 0$&nbsp; folgt die Reduzibilität von&nbsp; $a_8(x)$.&nbsp; Für die beiden anderen Polynome gilt dagegen:
 
:$$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_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}.$$
 
:$$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}.$$
  
Beide könnten also irreduzibel sein. Der exakte Nachweis der Irreduzibilität ist aufwändiger:  
+
Beide könnten also irreduzibel sein.&nbsp; Der exakte Nachweis der Irreduzibilität ist aufwändiger:  
*Man muss zur Überprüfung zwar nicht alle vier Divisorpolynome mit Grad $m = 2$ heranziehen, nämlich $x^2, \ x^2 + 1, \ x^2 + x + 1$, sondern es genügt die Division durch das einzige irreduzible Grad&ndash;2&ndash;Polynom. Man erhält hinsichtlich des Polynoms $a_9(x)$:
+
*Man muss zur Überprüfung zwar nicht alle vier Divisorpolynome mit Grad&nbsp; $m = 2$ heranziehen,&nbsp; nämlich $x^2, \ x^2 + 1, \ x^2 + x + 1$,&nbsp; sondern es genügt die Division durch das einzige irreduzible Grad&ndash;2&ndash;Polynom.&nbsp; Man erhält hinsichtlich des Polynoms&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 Rest}\hspace{0.15cm} r(x) = x\hspace{0.05cm}.$$
  
Zeile 139: Zeile 156:
 
:$$(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 Rest}\hspace{0.15cm} r(x) = x +1\hspace{0.05cm}.$$
  
Betrachten wir schließlich noch das Polynom $a_{10}(x) = x^4 + x^2 + 1$. Hier gilt
+
Betrachten wir schließlich noch das Polynom&nbsp; $a_{10}(x) = x^4 + x^2 + 1$.&nbsp; Hier gilt
 
:$$(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 Rest}\hspace{0.15cm} r(x) = 0\hspace{0.05cm}.$$
  
Daraus folgt: Nur das Polynom $a_9(x)$ ist irreduzibel &nbsp;&#8658;&nbsp; <u>Lösungsvorschlag 2</u>.
+
Daraus folgt:&nbsp; Nur das Polynom&nbsp; $a_9(x)$&nbsp; ist irreduzibel &nbsp; &#8658; &nbsp; <u>Lösungsvorschlag 2</u>.
 
{{ML-Fuß}}
 
{{ML-Fuß}}
  

Aktuelle Version vom 29. September 2022, 16:48 Uhr

Einige Polynome von Grad  $m = 2$,  $m = 3$,  $m = 4$

Wichtige Voraussetzungen für das Verständnis der Kanalcodierung sind Kenntnisse der Polynomeigenschaften. 

Wir betrachten in dieser Aufgabe Polynome der Form

$$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},$$
  • wobei für die Koeffizienten  $a_i ∈ {\rm GF}(2) = \{0, \, 1\}$  gilt  $(0 ≤ i ≤ m)$
  • und der höchste Koeffizient stets zu  $a_m = 1$  vorausgesetzt wird.


Man bezeichnet  $m$  als den  "Grad"  des Polynoms.  Nebenstehend sind zehn Polynome angegeben,  mit den Polynomgraden

  • $m = 2$  (rote Schrift), 
  • $m = 3$  (blaue Schrift) oder 
  • $m = 4$  (grüne Schrift).


Ein Polynom  $a(x)$  bezeichnet man als  reduzibel,  wenn es als Produkt zweier Polynome  $p(x)$  und  $q(x)$  mit jeweils niedrigerem Grad dargestellt werden kann:

$$a(x) = p(x) \cdot q(x)$$

Ist dies nicht möglich,  das heißt,  wenn für das Polynom

$$a(x) = p(x) \cdot q(x) + r(x)$$

mit einem Restpolynom  $r(x) ≠ 0$  gilt,  so nennt an das Polynom  irreduzibel.  Solche irreduziblen Polynome sind für die Beschreibung von Fehlerkorrekturverfahren von besonderer Bedeutung.

⇒   Der Nachweis,  dass ein Polynom  $a(x)$  vom Grad  $m$  irreduzibel ist,  erfordert mehrere Polynomdivisionen  $a(x)/q(x)$,  wobei der Grad des Divisorpolynoms  $q(x)$  stets kleiner ist als  $m$. Nur wenn alle diese Modulo–2–Divisionen stets einen Rest  $r(x) ≠ 0$  liefern,  ist nachgewiesen,  dass  $a(x)$  tatsächlich ein irreduzibles Polynom ist.

⇒   Dieser exakte Nachweis ist sehr aufwändig.  Notwendige Voraussetzungen dafür,  dass  $a(x)$  überhaupt ein irreduzibles Polynom sein könnte,  sind die beiden Bedingungen  $($bei nichtbinärer Betrachtungsweise wäre „$x=1$” durch „$x≠0$” zu ersetzen$)$:

  • $a(x = 0) = 1$,
  • $a(x = 1) = 1$.


Ansonsten könnte man für das zu untersuchende Polynom schreiben:

$$a(x) = q(x) \cdot x \hspace{0.5cm}{\rm bzw.}\hspace{0.5cm}a(x) = q(x) \cdot (x+1)\hspace{0.05cm}.$$

Die oben genannten Voraussetzungen sind zwar notwendig,  jedoch nicht hinreichend,  wie das folgende Beispiel zeigt:

$$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}.$$

Trotzdem ist dieses Polynom nämlich reduzibel:

$$a(x) = (x^3 + x +1)(x^2 + x +1) \hspace{0.05cm}.$$



Hinweis:  Die Aufgabe gehört zum Kapitel  "Erweiterungskörper".


Fragebogen

1

Wieviele Polynomdivisionen  $(N_{\rm D})$  sind erforderlich,  um exakt nachzuweisen,  dass ein  ${\rm GF}(2)$–Polynom  $a(x)$  vom Grad  $m$  irreduzibel ist?

$m = 2 \text{:} \hspace{0.35cm} N_{\rm D} \ = \ $

$m = 3 \text{:} \hspace{0.35cm} N_{\rm D} \ = \ $

$m = 4 \text{:} \hspace{0.35cm} N_{\rm D} \ = \ $

2

Welche der Grad–2–Polynome sind irreduzibel?

$a_1(x) = x^2 + x$,
$a_2(x) = x^2 + x + 1$.

3

Welche der Grad–3–Polynome sind irreduzibel?

$a_3(x) = x^3$,
$a_4(x) = x^3 + 1$,
$a_5(x) = x^3 + x$,
$a_6(x) = x^3 + x + 1$,
$a_7(x) = x^3 + x^2 + 1$.

4

Welche der Grad–4–Polynome sind irreduzibel?

$a_8(x) = x^4 + 1$,
$a_9(x) = x^4 + x^3 + 1$,
$a_{10}(x) = x^4 + x^2 + 1$.


Musterlösung

(1)  Das Polynom  $a(x) = a_0 + a_1 \cdot x + a_2 \cdot x^2 + \hspace{0.1cm}... \hspace{0.1cm} + a_m \cdot x^{m}$

  • mit  $a_m = 1$
  • und gegebenen Koeffizienten  $a_0, \ a_1, \hspace{0.05cm}\text{ ...} \hspace{0.1cm} , \ a_{m-1}$  $($jeweils  $0$  oder  $1)$


ist dann irreduzibel,  wenn es kein einziges Polynom  $q(x)$  gibt,  so dass die Modulo–2–Division   $a(x)/q(x)$   keinen Rest ergibt.  Der Grad aller zu betrachtenden Teilerpolynome  $q(x)$  ist dabei mindestens  $1$  und höchstens  $m-1$.

  • Für  $m = 2$  sind zwei Polynomdivisionen  $a(x)/q_i(x)$  erforderlich,  nämlich mit
$$q_1(x) = x \hspace{0.5cm}{\rm und}\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}.$$
  • Für  $m = 3$  gibt es schon  $N_{\rm D} \ \underline{= 6}$  Teilerpolynome,  nämlich neben  $q_1(x) = x$  und  $q_2(x) = x + 1$  noch
$$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}.$$
  • Für  $m = 4$  müssen außer  $q_1(x), \hspace{0.05cm}\text{ ...} \hspace{0.1cm} , \ q_6(x)$  auch noch alle möglichen Teilerpolynome mit Grad  $m = 3$  berücksichtigt werden,  also:
$$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}.$$
Für den Index gilt dabei  $7 ≤ i ≤ 14 \ \Rightarrow \ N_{\rm D} \ \underline{= 14}$.


(2)  Für das erste Polynom gilt:  $a_1(x = 0) = 0$.  Deshalb ist dieses Polynom reduzibel:  

$$a_1(x) = x \cdot (x + 1).$$

Dagegen gilt für das zweite Polynom:

$$a_2(x = 0) = 1\hspace{0.05cm},\hspace{0.2cm}a_2(x = 1) = 1 \hspace{0.05cm}.$$

Diese notwendige,  aber nicht hinreichende Eigenschaft zeigt,  dass  $a_2(x)$  irreduzibel sein könnte. 

Der endgültige Beweis ergibt sich erst durch zwei Modulo–2–Divisionen:

  • $a_2(x)$  geteilt durch  $x$  liefert  $x + 1$,  Rest $r(x) = 1$,
  • $a_2(x)$  geteilt durch  $x + 1$  liefert  $x$,  Rest $r(x) = 1$.


Richtig ist demnach der  Lösungsvorschlag 2.


(3)  Die drei ersten Polynome sind reduzibel,  wie die folgenden Rechenergebnisse zeigen:

$$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}.$$

Das hätte man auch durch Nachdenken herausfinden können:

$$a_3(x) \hspace{-0.15cm} \ = \ \hspace{-0.15cm} x \cdot x \cdot x \hspace{0.05cm},$$
$$a_4(x) \hspace{-0.15cm} \ = \ \hspace{-0.15cm} (x^2 + x + 1)\cdot(x + 1) \hspace{0.05cm},$$
$$a_5(x) \hspace{-0.15cm} \ = \ \hspace{-0.15cm} x \cdot (x + 1)\cdot(x + 1) \hspace{0.05cm}.$$

Das Polynom  $a_6(x)$  ist sowohl für  $x = 0$  als auch für  $x = 1$  ungleich  $0$.  Das heißt,  dass

  • „nichts dagegen spricht”,  dass $a_6(x)$  irreduzibel ist,
  • die Division durch die irreduziblen Grad–1–Polynome  $x$  bzw.  $x + 1$  nicht ohne Rest möglich ist.


Da aber auch die Division durch das einzige irreduzible Grad–2–Polynom einen Rest liefert,  ist bewiesen,  dass  $a_6(x)$  ein irreduzibles Polynom ist:

$$(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},$$

Mit gleichem Rechengang kann auch gezeigt werden, dass  $a_7(x)$  ebenfalls irreduzibel ist   ⇒   Lösungsvorschläge 4 und 5.


(4)  Aus  $a_8(x + 1) = 0$  folgt die Reduzibilität von  $a_8(x)$.  Für die beiden anderen Polynome gilt dagegen:

$$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}.$$

Beide könnten also irreduzibel sein.  Der exakte Nachweis der Irreduzibilität ist aufwändiger:

  • Man muss zur Überprüfung zwar nicht alle vier Divisorpolynome mit Grad  $m = 2$ heranziehen,  nämlich $x^2, \ x^2 + 1, \ x^2 + x + 1$,  sondern es genügt die Division durch das einzige irreduzible Grad–2–Polynom.  Man erhält hinsichtlich des Polynoms  $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}.$$

Auch die Division durch die beiden irreduziblen Grad–3–Polynome liefert jeweils einen Rest:

$$(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^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}.$$

Betrachten wir schließlich noch das Polynom  $a_{10}(x) = x^4 + x^2 + 1$.  Hier gilt

$$(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}.$$

Daraus folgt:  Nur das Polynom  $a_9(x)$  ist irreduzibel   ⇒   Lösungsvorschlag 2.