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

Hinweis:

• Die Aufgabe gehört zum Themengebiet des Kapitels Erweiterungskörper.

Fragebogen

1

Input-Box Frage

$xyz \ = \ $ $ab$

2

Multiple-Choice

	correct
	false

3

Multiple-Choice

	correct
	false

4

Multiple-Choice

	correct
	false

Musterlösung

Solution

(1)  (2)  (3)  (4)  (5)