Exercise 2.3: Reducible and Irreducible Polynomials

• Return to book

Polynome von Grad $m = 2$, $m = 3$ und $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, wobei der Polynomgrad entweder $m = 2$ (rote Schrift), $m = 3$ (blaue Schrift) oder $m = 4$ (grüne Schrift) ist.

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 jeweiligen 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 „$=1$” durch „$≠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 reduzibel:

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

Hinweise:

• Die Aufgabe gehört zum Themengebiet des Kapitels Erweiterungskörper.
• Sollte die Eingabe des Zahlenwertes „0” erforderlich sein, so geben Sie bitte „0.” ein.

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

Solution

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

• Schließlich müssen für $m = 4$ außer $q_1(x), \ ... \ , \ 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}.$$

1. 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,

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

ist nachgewiesen, dass $a_6(x)$ ein irreduzibles Polynom ist. 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{1.1cm}{\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.