Aufgaben: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)$ ein irreduzibles Polynom beschreibt.

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.15cm} N_{\rm D} \ = \ $

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

$m = 4 \text{:} \hspace{0.15cm} 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)  (2)  (3)  (4)  (5)