Aufgaben:Aufgabe 2.3: Reduzible und irreduzible Polynome: Unterschied zwischen den Versionen
| Zeile 2: | Zeile 2: | ||
[[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|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 <span style="color: rgb(204, 0, 0);"><b>reduzibel</b></span>, 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 <span style="color: rgb(204, 0, 0);"><b>irreduzibel</b></span>. 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 [[Kanalcodierung/Erweiterungsk%C3%B6rper| Erweiterungskörper]] | ||
Version vom 15. Dezember 2017, 15:45 Uhr
[[Datei:P_ID2503__KC_A_2_3.png|right|frame|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 :'"`UNIQ-MathJax3-QINU`"' 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
