Aufgaben:Aufgabe 2.3Z: Polynomdivision: Unterschied zwischen den Versionen

@@ Zeile 1: / Zeile 1: @@
 {{quiz-Header|Buchseite=Kanalcodierung/Erweiterungskörper}}
-[[Datei:P_ID2504__KC_Z_2_3.png|right|frame|Zur Multiplikation und Division von $\rm GF(2)$–Polynomen]]
+[[Datei:P_ID2504__KC_Z_2_3.png|right|frame|Zur Multiplikation und Division von Polynomen  im Galoisfeld $\rm GF(2)$]]
-In dieser Aufgabe beschäftigen wir uns mit der Multiplikation und insbesondere der Division von Polynomen im Galoisfeld $\rm GF(2)$. In der Abbildung ist jeweils die Vorgehensweise an einem einfachen und selbsterklärenden Beispiel verdeutlicht:
+In dieser Aufgabe beschäftigen wir uns mit der Multiplikation und insbesondere der Division von Polynomen im Galoisfeld $\rm GF(2)$. In der Abbildung ist jeweils die Vorgehensweise an einem einfachen und selbsterklärenden Beispiel angedeutet:
 * Die Multiplikation der beiden Polynome $x^2 + 1$ und $x +1$ liefert das Ergebnis $a(x) = x^3 + x^2 + x + 1$.
-* Die Division des Polynoms $a(x) = x^3$ durch $p(x) = x + 1$ liefert den Quotienten $q(x) = x^2 + x$ und den Rest $r(x) = x$.
+* Die Division des Polynoms $b(x) = x^3$ durch $p(x) = x + 1$ liefert den Quotienten $q(x) = x^2 + x$ und den Rest $r(x) = x$.
 * Man kann das letztere Ergebnis wie folgt überprüfen:
-:$$a(x) \hspace{-0.15cm} \ = \ \hspace{-0.15cm} p(x) \cdot q(x) + r(x)\hspace{0.05cm}= $$
+:$$b(x) \hspace{-0.15cm} \ = \ \hspace{-0.15cm} p(x) \cdot q(x) + r(x)\hspace{0.05cm}= [(x+1) \cdot (x^2+x)] +x =[x^3+ x^2+x^2+ x] +x = x^3\hspace{0.05cm}.$$
-:$$\hspace{0.7cm} \ = \ \hspace{-0.15cm}[(x+1) \cdot (x^2+x)] +x =$$
-:$$\hspace{0.7cm} \ = \ \hspace{-0.15cm}[x^3+ x^2+x^2+ x] +x = x^3\hspace{0.05cm}.$$
 ''Hinweis:''
-* Die Aufgabe gehört zum Themengebiet des Kapitels [[Kanalcodierung/Erweiterungsk%C3%B6rper| Erweiterungskörper]].
+* Die Aufgabe gehört zum Kapitel [[Kanalcodierung/Erweiterungsk%C3%B6rper| Erweiterungskörper]].
@@ Zeile 33: / Zeile 32: @@
 - $(x^5 + x^2 + x)/(x^2 + 1)$.
-{Es sei $a(x) = x^6 + x^5 + 1$ und $p(x) = x^3 + x^2 + 1$. Bestimmen Sie $q(x)$ und $r(x)$ entsprechend der Beschreibungsgleichung $a(x) = p(x) \cdot q(x) + r(x)$.
+{Es sei $a(x) = x^6 + x^5 + 1$ und $p(x) = x^3 + x^2 + 1$. <br>Bestimmen Sie $q(x)$ und $r(x)$ entsprechend der Beschreibungsgleichung $a(x) = p(x) \cdot q(x) + r(x)$.
 |type="[]"}
 - $q(x) = x^3 + x^2 + 1, \hspace{0.2cm} r(x) = 0$,

Version vom 8. Januar 2018, 10:20 Uhr

Zurück zum Buch

Zur Multiplikation und Division von Polynomen im Galoisfeld $\rm GF(2)$

In dieser Aufgabe beschäftigen wir uns mit der Multiplikation und insbesondere der Division von Polynomen im Galoisfeld $\rm GF(2)$. In der Abbildung ist jeweils die Vorgehensweise an einem einfachen und selbsterklärenden Beispiel angedeutet:

Die Multiplikation der beiden Polynome $x^2 + 1$ und $x +1$ liefert das Ergebnis $a(x) = x^3 + x^2 + x + 1$.
Die Division des Polynoms $b(x) = x^3$ durch $p(x) = x + 1$ liefert den Quotienten $q(x) = x^2 + x$ und den Rest $r(x) = x$.
Man kann das letztere Ergebnis wie folgt überprüfen:

$$b(x) \hspace{-0.15cm} \ = \ \hspace{-0.15cm} p(x) \cdot q(x) + r(x)\hspace{0.05cm}= [(x+1) \cdot (x^2+x)] +x =[x^3+ x^2+x^2+ x] +x = x^3\hspace{0.05cm}.$$

Hinweis:

Die Aufgabe gehört zum Kapitel Erweiterungskörper.

Fragebogen

Welches Ergebnis liefert $a(x) = (x^3 + x + 1) \cdot (x^2 + 1)$?

	$a(x) = x^5 + x^3 + x^2 + 1$,
	$a(x) = x^5 + x^2 + x + 1$.
	$a(x) = x^6 + x^3 + x^2 + 1$-

Welche der Polynomdivisionen ergeben keinen Rest $r(x)$?

	$(x^5 + x^2 + x + 1)/(x^3 + x + 1)$.
	$(x^5 + x^2 + x + 1)/(x^2 + 1)$,
	$(x^5 + x^2 + x + 1)/(x^2)$,
	$(x^5 + x^2 + x)/(x^2 + 1)$.

Es sei $a(x) = x^6 + x^5 + 1$ und $p(x) = x^3 + x^2 + 1$.
Bestimmen Sie $q(x)$ und $r(x)$ entsprechend der Beschreibungsgleichung $a(x) = p(x) \cdot q(x) + r(x)$.

	$q(x) = x^3 + x^2 + 1, \hspace{0.2cm} r(x) = 0$,
	$q(x) = x^3 + 1, \hspace{0.2cm} r(x) = 0$,
	$q(x) = x^3 + 1, \hspace{0.2cm} r(x) = x^2$.

Musterlösung

(1) Die Modulo–2–Multiplikation der beiden Polynome führt zum Ergebnis

$$a(x) \hspace{-0.15cm} \ = \ \hspace{-0.15cm} (x^3+ x+1) \cdot (x^2+1)= $$

$$\hspace{0.7cm} \ = \ \hspace{-0.15cm} x^5+x^3+ x^2+ x^3+x+1 = x^5+ x^2+x+1\hspace{0.05cm}.$$

Richtig ist somit der Lösungsvorschlag 2. Der letzte Lösungsvorschlag kann schon alleine deshalb nicht simmen, da der Grad des Produktpolynoms $≠ 5$ wäre.

(2) Mit den Abkürzungen

$$a(x) = x^5+ x^2+x+1\hspace{0.05cm},\hspace{0.4cm}p(x) = x^3+ x+1\hspace{0.05cm},\hspace{0.4cm}q(x) = x^2+ 1$$

und dem Ergebnis aus der Teilaufgabe (1) erhält man $a(x) = p(x) \cdot q(x)$. Das heißt: Die Divisionen $a(x)/p(x)$ und $a(x)/q(x)$ sind restfrei möglich ⇒ Richtig sind die Lösungsvorschläge 1 und 2. Auch ohne Rechnung erkennt man, dass $a(x)/x^2$ einen Rest ergeben muss. Nach Rechnung ergibt sich explizit:

$$(x^5 + x^2+x+1)/(x^2) = x^3 + 1 \hspace{0.05cm},\hspace{0.4cm}{\rm Rest}\hspace{0.15cm} r(x) = x+1\hspace{0.05cm}.$$

Beispiel 1 zur Polynomdivision

Zum letzten Lösungsvorschlag. Wir verwenden zur Abkürzung $b(x) = x^5 + x^2 + x = a(x) + 1$. Damit ist der vorgegebene Quotient:

$$b(x)/q(x) = a(x)/q(x) + 1/q(x) \hspace{0.05cm}.$$

Der erste Quotient $a(x)/q(x)$ ergibt entsprechend der Teilaufgabe (2) genau $p(x)$ ohne Rest, der zweite Quotient $0$ mit Rest $1$. Somit ist hier der Rest des Quotienten $b(x)/q(x)$ gleich $r(x) = 1$, wie auch die nebenstehende Rechnung zeigt.

(3) Die Polynomdivision ist nachfolgend ausführlich erläutert. Richtig ist der Lösungsvorschlag 3.

Beispiel 2 zur Polynomdivision