Aufgaben:Aufgabe 2.5: Drei Varianten von GF(2 hoch 4): Unterschied zwischen den Versionen
Aus LNTwww
| Zeile 1: | Zeile 1: | ||
{{quiz-Header|Buchseite=Kanalcodierung/Erweiterungskörper}} | {{quiz-Header|Buchseite=Kanalcodierung/Erweiterungskörper}} | ||
| − | [[Datei:P_ID2508__KC_A_2_5.png|right|frame|Potenzen zweier verschiedener Erweiterungskörper über $\rm GF(2^4)$ – eine nicht ganz vollständige Liste]] | + | [[Datei:P_ID2508__KC_A_2_5.png|right|frame|Potenzen zweier verschiedener Erweiterungskörper über $\rm GF(2^4)$ – eine nicht ganz vollständige Liste]] |
| − | Irreduzible und primitive Polynome haben große Bedeutung für die Beschreibung von Verfahren zur Fehlerkorrektur. In [LN97] findet man zum Beispiel die folgenden irreduziblen Polynome vom Grad $m = 4$: | + | Irreduzible und primitive Polynome haben große Bedeutung für die Beschreibung von Verfahren zur Fehlerkorrektur. In '''[LN97]''' findet man zum Beispiel die folgenden irreduziblen Polynome vom Grad $m = 4$: |
* $p_1(x) = x^4 + x +1$, | * $p_1(x) = x^4 + x +1$, | ||
| + | |||
* $p_2(x) = x^4 + x^3 + 1$, | * $p_2(x) = x^4 + x^3 + 1$, | ||
| + | |||
* $p_3(x) = x^4 + x^3 + x^2 + x + 1$. | * $p_3(x) = x^4 + x^3 + x^2 + x + 1$. | ||
| − | Die beiden ersten Polynome sind auch primitiv. Dies erkennt man aus den Potenztabellen, die rechts angegeben sind – die untere Tabelle $\rm (B)$ allerdings nicht ganz vollständig. | + | Die beiden ersten Polynome sind auch primitiv. Dies erkennt man aus den Potenztabellen, die rechts angegeben sind – die untere Tabelle $\rm (B)$ allerdings nicht ganz vollständig. |
| − | *Aus beiden Tabellen erkennt man, dass alle Potenzen $\alpha^i$ für $1 ≤ i ≤ 14$ in der Polynomdarstellung ungleich $1$ sind. Erst für $i = 15$ ergibt sich | + | *Aus beiden Tabellen erkennt man, dass alle Potenzen $\alpha^i$ für $1 ≤ i ≤ 14$ in der Polynomdarstellung ungleich $1$ sind. Erst für $i = 15$ ergibt sich |
:$$\alpha^{15} = \alpha^{0} = 1 \hspace{0.3cm} \Rightarrow\hspace{0.3cm}{\rm Koeffizientenvektor\hspace{0.15cm} 0001}\hspace{0.05cm} .$$ | :$$\alpha^{15} = \alpha^{0} = 1 \hspace{0.3cm} \Rightarrow\hspace{0.3cm}{\rm Koeffizientenvektor\hspace{0.15cm} 0001}\hspace{0.05cm} .$$ | ||
| − | *Nicht angegeben wird, ob sich die Tabellen $\rm (A)$ und $\rm (B)$ aus dem Polynom $p_1(x) = x^4 + x + 1$ oder aus $p_2(x) =x^4 + x^3 + 1$ ergibt. Diese Zuordnungen sollen Sie in den Teilaufgaben '''(1)''' und '''(2)''' treffen. | + | *Nicht angegeben wird, ob sich die Tabellen $\rm (A)$ und $\rm (B)$ aus dem Polynom $p_1(x) = x^4 + x + 1$ oder aus $p_2(x) =x^4 + x^3 + 1$ ergibt. Diese Zuordnungen sollen Sie in den Teilaufgaben '''(1)''' und '''(2)''' treffen. |
| − | *In der Teilaufgabe '''(3)''' sollen Sie zudem die fehlenden Potenzen $\alpha^5, \ \alpha^6, \ \alpha^7$ und $\alpha^8$ in der Tabelle $\rm (B)$ ergänzen. | + | |
| − | + | *In der Teilaufgabe '''(3)''' sollen Sie zudem die fehlenden Potenzen $\alpha^5, \ \alpha^6, \ \alpha^7$ und $\alpha^8$ in der Tabelle $\rm (B)$ ergänzen. | |
| − | |||
| + | *Die Teilaufgabe '''(4)''' bezieht sich auf das ebenfalls irreduzible Polynom $p_3(x) = x^4 + x^3 + x^2 + x +1$. Entsprechend den oben genannten Kriterien sollen Sie entscheiden, ob dieses Polynom primitiv ist. | ||
| + | Hinweise: | ||
| + | * Die Aufgabe gehört zum Kapitel [[Kanalcodierung/Erweiterungsk%C3%B6rper|"Erweiterungskörper"]]. | ||
| − | + | *Das Literaturzitat '''[LN97]''' verweist auf das Buch "Lidl, R.; Niederreiter, H.: Finite Fields. Encyclopedia of Mathematics and its Application. 2. Auflage. Cambridge: University Press, 1997". | |
| − | |||
| − | *Das Literaturzitat [LN97] verweist auf das Buch | ||
| Zeile 39: | Zeile 41: | ||
+ $p_2(x) = x^4 + x^3 + 1$. | + $p_2(x) = x^4 + x^3 + 1$. | ||
| − | {Ergänzen Sie die in der Tabelle $\rm (B)$ fehlenden Einträge. Welche der folgenden Angaben sind richtig? | + | {Ergänzen Sie die in der Tabelle $\rm (B)$ fehlenden Einträge. Welche der folgenden Angaben sind richtig? |
|type="[]"} | |type="[]"} | ||
| − | + $\alpha^5 = \alpha^3 + \alpha + 1$ ⇒ Koeffizientenvektor „$1011$”, | + | + $\alpha^5 = \alpha^3 + \alpha + 1$ ⇒ Koeffizientenvektor „$1011$”, |
| − | - $\alpha^6 = \alpha^2 + 1$ ⇒ Koeffizientenvektor „$0111$”, | + | - $\alpha^6 = \alpha^2 + 1$ ⇒ Koeffizientenvektor „$0111$”, |
| − | - $\alpha^7 = \alpha^3 + \alpha^2 + \alpha + 1$ ⇒ Koeffizientenvektor „$1111$”, | + | - $\alpha^7 = \alpha^3 + \alpha^2 + \alpha + 1$ ⇒ Koeffizientenvektor „$1111$”, |
| − | + $\alpha^8 = \alpha^3 + \alpha^2 + \alpha$ ⇒ Koeffizientenvektor „$1110$”. | + | + $\alpha^8 = \alpha^3 + \alpha^2 + \alpha$ ⇒ Koeffizientenvektor „$1110$”. |
| − | {Ist $p_3(x) = x^4 + x^3 + x^2 + x + 1$ ein primitives Polynom? Klären Sie diese Frage anhand der Potenzen $\alpha^i$ $(i$ soweit erforderlich$)$. | + | {Ist $p_3(x) = x^4 + x^3 + x^2 + x + 1$ ein primitives Polynom? Klären Sie diese Frage anhand der Potenzen $\alpha^i$ $(i$ soweit erforderlich$)$. |
|type="()"} | |type="()"} | ||
- Ja. | - Ja. | ||
Version vom 4. Oktober 2022, 11:13 Uhr
Potenzen zweier verschiedener Erweiterungskörper über $\rm GF(2^4)$ – eine nicht ganz vollständige Liste
Irreduzible und primitive Polynome haben große Bedeutung für die Beschreibung von Verfahren zur Fehlerkorrektur. In [LN97] findet man zum Beispiel die folgenden irreduziblen Polynome vom Grad $m = 4$:
- $p_1(x) = x^4 + x +1$,
- $p_2(x) = x^4 + x^3 + 1$,
- $p_3(x) = x^4 + x^3 + x^2 + x + 1$.
Die beiden ersten Polynome sind auch primitiv. Dies erkennt man aus den Potenztabellen, die rechts angegeben sind – die untere Tabelle $\rm (B)$ allerdings nicht ganz vollständig.
- Aus beiden Tabellen erkennt man, dass alle Potenzen $\alpha^i$ für $1 ≤ i ≤ 14$ in der Polynomdarstellung ungleich $1$ sind. Erst für $i = 15$ ergibt sich
- $$\alpha^{15} = \alpha^{0} = 1 \hspace{0.3cm} \Rightarrow\hspace{0.3cm}{\rm Koeffizientenvektor\hspace{0.15cm} 0001}\hspace{0.05cm} .$$
- Nicht angegeben wird, ob sich die Tabellen $\rm (A)$ und $\rm (B)$ aus dem Polynom $p_1(x) = x^4 + x + 1$ oder aus $p_2(x) =x^4 + x^3 + 1$ ergibt. Diese Zuordnungen sollen Sie in den Teilaufgaben (1) und (2) treffen.
- In der Teilaufgabe (3) sollen Sie zudem die fehlenden Potenzen $\alpha^5, \ \alpha^6, \ \alpha^7$ und $\alpha^8$ in der Tabelle $\rm (B)$ ergänzen.
- Die Teilaufgabe (4) bezieht sich auf das ebenfalls irreduzible Polynom $p_3(x) = x^4 + x^3 + x^2 + x +1$. Entsprechend den oben genannten Kriterien sollen Sie entscheiden, ob dieses Polynom primitiv ist.
Hinweise:
- Die Aufgabe gehört zum Kapitel "Erweiterungskörper".
- Das Literaturzitat [LN97] verweist auf das Buch "Lidl, R.; Niederreiter, H.: Finite Fields. Encyclopedia of Mathematics and its Application. 2. Auflage. Cambridge: University Press, 1997".
Fragebogen
Musterlösung
(1) Aus der oberen Potenztabelle $\rm (A)$ auf der Angabenseite erkennt man unter anderem die Eigenschaft
- $$\alpha^{4} = \alpha + 1 \hspace{0.3cm} \Rightarrow\hspace{0.3cm}\alpha^{4} + \alpha + 1 = 0 \hspace{0.3cm} \Rightarrow\hspace{0.3cm} p(x) = x^4 + x +1 =p_1(x)\hspace{0.05cm}.$$
Richtig ist somit der Lösungsvorschlag 1.
(2) Nach gleicher Vorgehensweise kann gezeigt werden, dass die Potenztabelle $\rm (B)$ auf dem Polynom $p_2(x) = x^4 + x^3 + 1$ basiert ⇒ Lösungsvorschlag 2.
(3) Ausgehend von Polynom $p_2(x) = x^4 + x^3 + 1$ erhält man aus der Bestimmungsgleichung $p(\alpha) = 0$ das Ergebnis $\alpha^4 = \alpha^3 + 1$. Damit ergibt sich weiter:
- $$\alpha^5 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} \alpha \cdot \alpha^4 = \alpha \cdot (\alpha^3 + 1) = \alpha^4 + \alpha = \alpha^3 + \alpha +1\hspace{0.05cm} \Rightarrow\hspace{0.05cm}{\rm Vektor\hspace{0.15cm} 1011},$$
- $$\alpha^6 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} \alpha \cdot \alpha^5 = \alpha \cdot (\alpha^3 +\alpha + 1) = \alpha^4 + \alpha^2 + \alpha= \alpha^3 +\alpha^2 + \alpha + 1\hspace{0.05cm} \Rightarrow\hspace{0.05cm}{\rm Vektor\hspace{0.15cm} 1111},$$
- $$\alpha^7 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} \alpha \cdot \alpha^6 = \alpha^4 +\alpha^3 +\alpha^2 +\alpha = \alpha^2 + \alpha + 1\hspace{0.05cm} \Rightarrow\hspace{0.05cm}{\rm Vektor\hspace{0.15cm} 0111},$$
- $$\alpha^8 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} \alpha \cdot \alpha^7 = \alpha \cdot (\alpha^2 + \alpha + 1) = \alpha^3 +\alpha^2 +\alpha \hspace{0.05cm} \Rightarrow\hspace{0.05cm}{\rm Vektor\hspace{0.15cm} 1110}.$$
- Richtig sind somit nur die Lösungsvorschläge 1 und 4. Die beiden anderen Angaben sind vertauscht.
- Nachfolgend finden Sie die vollständigen Potenztabellen für $p_1(x) = x^4 + x + 1$ (links, rot hinterlegt) und für $p_2(x) = x^4 + x^3 + 1$ (rechts, blau hinterlegt).
Vollständige Potenztabellen über $\rm GF(2^4)$ für zwei unterschiedliche Polynome
(4) Die beiden Polynome $p_1(x) = x^4 + x + 1$ und $p_2(x) = x^4 + x^3 + 1$ sind primitiv.
- Dies erkennt man daran, dass $\alpha^i$ für $0 < i < 14$ jeweils ungleich $1$ ist.
- Dagegen gilt $\alpha^{15} = \alpha^0 = 1$. In beiden Fällen kann das Galoisfeld wie folgt ausgedrückt werden:
- $${\rm GF}(2^4) = \{\hspace{0.1cm}0\hspace{0.05cm},\hspace{0.1cm} \alpha^{0} = 1,\hspace{0.05cm}\hspace{0.1cm} \alpha\hspace{0.05cm},\hspace{0.1cm} \alpha^{2},\hspace{0.1cm} ... \hspace{0.1cm} , \hspace{0.1cm}\alpha^{14}\hspace{0.1cm}\}\hspace{0.05cm}. $$
Für das Polynom $p_3(x) = x^4 + x^3 + x^2 + x +1$ erhält man :
- $$\alpha^4 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} \alpha^3 + \alpha^2 + \alpha +1\hspace{0.25cm} \Rightarrow\hspace{0.25cm}{\rm Vektor\hspace{0.15cm} 1111}\hspace{0.05cm},$$
- $$\alpha^5 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} \alpha \cdot \alpha^4 = \alpha^4 + \alpha^3 + \alpha^2 + \alpha = (\alpha^3 + \alpha^2 + \alpha +1) + \alpha^3 + \alpha^2 + \alpha = 1 \hspace{0.25cm} \Rightarrow\hspace{0.25cm}{\rm Vektor\hspace{0.15cm} 0001}\hspace{0.05cm}.$$
- Hier ist also bereits $\alpha^5 = \alpha^0 = 1 \ \Rightarrow \ p_3(x)$ ist kein primitives Polynom ⇒ Lösungsvorschlag 2.
- Für die weiteren Potenzen gilt für dieses Polynom:
- $$\alpha^6 = \alpha^{11} = \alpha\hspace{0.05cm},\hspace{0.2cm} \alpha^7 = \alpha^{12} = \alpha^2\hspace{0.05cm},\hspace{0.2cm} \alpha^8 = \alpha^{13} = \alpha^3\hspace{0.05cm},$$
- $$\alpha^9 = \alpha^{14} = \alpha^4\hspace{0.05cm},\hspace{0.2cm} \alpha^{10} = \alpha^{15} = \alpha^0 = 1\hspace{0.05cm}.$$
