Aufgabe 2.3: Reduzible und irreduzible Polynome
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
Musterlösung
