Aufgaben:Aufgabe 2.3Z: Polynomdivision: Unterschied zwischen den Versionen
Aus LNTwww
| (4 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt) | |||
| Zeile 1: | Zeile 1: | ||
{{quiz-Header|Buchseite=Kanalcodierung/Erweiterungskörper}} | {{quiz-Header|Buchseite=Kanalcodierung/Erweiterungskörper}} | ||
| − | [[Datei:P_ID2504__KC_Z_2_3.png|right|frame| | + | [[Datei:P_ID2504__KC_Z_2_3.png|right|frame|Multiplikation und Division von Polynomen in $\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: | + | 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 (hoffentlich) 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 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$. | + | |
| + | * 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: | * 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}.$$ | + | :$$b(x) \hspace{-0.15cm} \ = \ \hspace{-0.15cm} p(x) \cdot q(x) + r(x)\hspace{0.05cm}= \big[(x+1) \cdot (x^2+x)\big] +x =\big[x^3+ x^2+x^2+ x\big] +x = x^3\hspace{0.05cm}.$$ |
| − | + | Hinweis: Die Aufgabe gehört zum Kapitel [[Kanalcodierung/Erweiterungsk%C3%B6rper| "Erweiterungskörper"]]. | |
| − | |||
| Zeile 19: | Zeile 20: | ||
===Fragebogen=== | ===Fragebogen=== | ||
<quiz display=simple> | <quiz display=simple> | ||
| − | {Welches Ergebnis liefert $a(x) = (x^3 + x + 1) \cdot (x^2 + 1)$? | + | {Welches Ergebnis liefert $a(x) = (x^3 + x + 1) \cdot (x^2 + 1)$? |
| − | |type=" | + | |type="()"} |
- $a(x) = x^5 + x^3 + x^2 + 1$, | - $a(x) = x^5 + x^3 + x^2 + 1$, | ||
+ $a(x) = x^5 + x^2 + x + 1$. | + $a(x) = x^5 + x^2 + x + 1$. | ||
- $a(x) = x^6 + x^3 + x^2 + 1$- | - $a(x) = x^6 + x^3 + x^2 + 1$- | ||
| − | {Welche der Polynomdivisionen ergeben keinen Rest $r(x)$? | + | {Welche der Polynomdivisionen ergeben keinen Rest $r(x) \ne 0$? |
|type="[]"} | |type="[]"} | ||
+ $(x^5 + x^2 + x + 1)/(x^3 + x + 1)$. | + $(x^5 + x^2 + x + 1)/(x^3 + x + 1)$. | ||
| Zeile 32: | Zeile 33: | ||
- $(x^5 + x^2 + x)/(x^2 + 1)$. | - $(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$. <br>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=" | + | |type="()"} |
- $q(x) = x^3 + x^2 + 1, \hspace{0.2cm} r(x) = 0$, | - $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) = 0$, | ||
| Zeile 44: | Zeile 45: | ||
:$$a(x) \hspace{-0.15cm} \ = \ \hspace{-0.15cm} (x^3+ x+1) \cdot (x^2+1)= x^5+x^3+ x^2+ x^3+x+1 = x^5+ x^2+x+1\hspace{0.05cm}.$$ | :$$a(x) \hspace{-0.15cm} \ = \ \hspace{-0.15cm} (x^3+ x+1) \cdot (x^2+1)= x^5+x^3+ x^2+ x^3+x+1 = x^5+ x^2+x+1\hspace{0.05cm}.$$ | ||
| − | Richtig ist somit der <u>Lösungsvorschlag 2</u>. Der letzte Lösungsvorschlag kann schon alleine deshalb nicht simmen, da der Grad des Produktpolynoms ungleich $5$ wäre. | + | *Richtig ist somit der <u>Lösungsvorschlag 2</u>. |
| + | |||
| + | *Der letzte Lösungsvorschlag kann schon alleine deshalb nicht simmen, da der Grad des Produktpolynoms ungleich $5$ wäre. | ||
| − | [[Datei:P_ID2506__KC_Z_2_3b_neu.png|right|frame|Beispiel 1 zur Polynomdivision]] | + | |
| + | [[Datei:P_ID2506__KC_Z_2_3b_neu.png|right|frame|'''Beispiel 1''' zur Polynomdivision]] | ||
'''(2)''' Mit den Abkürzungen | '''(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$$ | :$$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 <u>Lösungsvorschläge 1 und 2</u>. | + | 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 | ||
| + | <br>⇒ Richtig sind die <u>Lösungsvorschläge 1 und 2</u>. | ||
| − | Auch ohne Rechnung erkennt man, dass $a(x)/x^2$ einen Rest ergeben muss. Nach Rechnung ergibt sich explizit: | + | 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}.$$ | :$$(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}.$$ | ||
| − | Zum letzten Lösungsvorschlag. Wir verwenden zur Abkürzung $b(x) = x^5 + x^2 + x = a(x) + 1$. Damit ist der vorgegebene Quotient: | + | 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}.$$ | :$$b(x)/q(x) = a(x)/q(x) + 1/q(x) \hspace{0.05cm}.$$ | ||
| − | [[Datei:P_ID2505__KC_Z_2_3c.png|Right|frame|Beispiel 2 zur Polynomdivision]] | + | [[Datei:P_ID2505__KC_Z_2_3c.png|Right|frame|'''Beispiel 2''' zur Polynomdivision]] |
| − | 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 | + | *Der erste Quotient $a(x)/q(x)$ ergibt entsprechend der Teilaufgabe '''(2)''' genau $p(x)$ ohne Rest, der zweite Quotient hat das Ergebnis $0$ mit Rest $1$. |
| + | |||
| + | *Somit ist hier der Rest des Quotienten $b(x)/q(x)$ gleich $r(x) = 1$, wie die Rechnung im '''Beispiel 1''' zeigt. | ||
| + | |||
| − | '''(3)''' Die Polynomdivision ist im Beispiel 2 ausführlich erläutert. Richtig ist der <u>Lösungsvorschlag 3</u>. | + | '''(3)''' Die Polynomdivision ist im '''Beispiel 2''' ausführlich erläutert. Richtig ist der <u>Lösungsvorschlag 3</u>. |
Aktuelle Version vom 2. Oktober 2022, 13:58 Uhr
Multiplikation und Division von Polynomen in $\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 (hoffentlich) 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}= \big[(x+1) \cdot (x^2+x)\big] +x =\big[x^3+ x^2+x^2+ x\big] +x = x^3\hspace{0.05cm}.$$
Hinweis: Die Aufgabe gehört zum Kapitel "Erweiterungskörper".
Fragebogen
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)= 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 ungleich $5$ wäre.
Beispiel 1 zur Polynomdivision
(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}.$$
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}.$$
Beispiel 2 zur Polynomdivision
- Der erste Quotient $a(x)/q(x)$ ergibt entsprechend der Teilaufgabe (2) genau $p(x)$ ohne Rest, der zweite Quotient hat das Ergebnis $0$ mit Rest $1$.
- Somit ist hier der Rest des Quotienten $b(x)/q(x)$ gleich $r(x) = 1$, wie die Rechnung im Beispiel 1 zeigt.
(3) Die Polynomdivision ist im Beispiel 2 ausführlich erläutert. Richtig ist der Lösungsvorschlag 3.
