Kanalcodierung/Erweiterungskörper

1. Kanalcodierung
2. Reed–Solomon–Codes und deren Decodierung
3. Erweiterungskörper

• Vorherige Seite
• Nächste Seite

• Vorherige Seite
• Nächste Seite

GF(2²) – Beispiel eines Erweiterungskörpers (1)

Im Kapitel 2.1 wurde bereits gezeigt, dass die endliche Zahlenmenge {0, 1, 2, 3}  ⇒  q = 4 nicht die Eigenschaften eines Galoisfeldes GF(4) erfüllt. Vielmehr ergeben sich für die Addition modulo 4 und die Multiplikation modulo 4 folgende Tabellen:

\[{\rm Operationen } \hspace{0.15cm}{\rm modulo}\hspace{0.15cm}{\it q} = 4 \hspace{0.25cm} \Rightarrow\hspace{0.25cm}\]

+ 0 1 2 3 0 0 1 2 3 1 1 2 3 0 2 2 3 0 1 3 3 0 1 2

. 0 1 2 3 0 0 0 0 0 1 0 1 2 3 2 0 2 0 2 3 0 3 2 1

Für z_i = 2 gibt es keine multiplikative Inverse Inv_M(z_i). Dies erkennt man daran, dass kein einziges Element z_j ∈ {0, 1, 2, 3} die Bedingung 2 · z_j = 1 erfüllt. Geht man dagegen vom binären Galoisfeld GF(2) = {0, 1} aus und erweitert dieses entsprechend der Gleichung

\[{\rm GF}(2^2)= \big\{k_0+k_1\cdot \alpha \ | \ k_0, k_1\in{\rm GF}(2) = \{ 0, 1\} \big \}\hspace{0.05cm}, \]

so ergibt sich die ebenfalls endliche Menge {0, 1, α, 1 + α}  ⇒  die Ordnung ist weiterhin q = 4. Führt man die Rechenoperationen modulo p(α) = α² + α + 1 durch, so erhält man das folgende Ergebnis:

\[{\rm modulo} \hspace{0.15cm} {\it p} (\alpha) \hspace{0.25cm}\Rightarrow \]

+ 0 1 α 1+α 0 0 1 α 1+α 1 1 0 1+α α α α 1+α 0 1 1+α 1+α α 1 0

. 0 1 α 1+α 0 0 0 0 0 1 0 1 α 1+α α 0 α 1+α 1 1+α 0 1+α 1 α

Hierzu ist anzumerken:

• Die neutralen Elemente der Addition bzw. Multiplikation sind weiterhin N_A = 0 und N_M = 1.

• Da bei Modulo–Ausführung kein Unterschied zwischen Addition und Subtraktion besteht, ist α + α = α – α = 0. Für alle z_i gilt somit: Die additive Inverse von z_i ist das Element z_i selbst.

• Die Einträge in der Multiplikationstabelle ergeben sich nach folgenden Berechnungen:

\[\big [ \alpha \cdot (1+\alpha) \big ] \hspace{0.15cm}{\rm mod} \hspace{0.15cm} p(\alpha) \hspace{-0.15cm} = \hspace{-0.15cm} (\alpha^2 + \alpha) \hspace{0.15cm}{\rm mod} \hspace{0.15cm} (\alpha^2 + \alpha + 1)= 1\hspace{0.05cm},\]

\[\big [ \alpha \cdot \alpha \big ] \hspace{0.15cm}{\rm mod} \hspace{0.15cm} p(\alpha) \hspace{-0.15cm} = \hspace{-0.15cm} (\alpha^2 ) \hspace{0.15cm}{\rm mod} \hspace{0.15cm} (\alpha^2 + \alpha + 1)= 1+\alpha\hspace{0.05cm},\]

\[\big [ (1+\alpha) \cdot (1+\alpha) \big ] \hspace{0.15cm}{\rm mod} \hspace{0.15cm} p(\alpha) \hspace{-0.15cm} = \hspace{-0.15cm} (\alpha^2 + 1) \hspace{0.15cm}{\rm mod} \hspace{0.15cm} (\alpha^2 + \alpha + 1)= \alpha\hspace{0.05cm}.\]

• Damit existieren für alle Elemente mit Ausnahme des Nullelements die multiplikativen Inversen:

\[{\rm Inv_M}( 1) = 1 \hspace{0.05cm},\hspace{0.2cm}{\rm Inv_M}(\alpha) = 1+\alpha \hspace{0.05cm},\hspace{0.2cm}{\rm Inv_M}(1+\alpha) = \alpha \hspace{0.05cm}.\]

Daraus folgt: Die Menge {0, 1, α, 1 + α} stellt zusammen mit den zwei Rechenoperationen Addition und Multiplikation modulo p(α) = α² + α + 1 ein Galoisfeld der Ordnung q = 4 dar. Dieses mit GF(2²) = GF(4) bezeichnete Galoisfeld erfüllt alle in Kapitel 2.1 genannten Eigenschaften.

Im Gegensatz zum Zahlenkörper GF(3) = {0, 1, 2} mit der Eigenschaft, dass q = 3 eine Primzahl ist, nennt man GF(2²) einen Erweiterungskörper (englisch: Extension Field).

GF(2²) – Beispiel eines Erweiterungskörpers (2)

Das Polynom p(α) und damit die Bestimmungsgleichung p(α) = 0 darf nicht beliebig vorgegeben werden. Zum Beleg hierfür vergleichen wir die Verknüpfungstabellen für zwei verschiedene Polynome.

Polynom entsprechend der letzten Seite  ⇒  p(α) = α² + α + 1:

+ 0 1 α 1+α 0 0 1 α 1+α 1 1 0 1+α α α α 1+α 0 1 1+α 1+α α 1 0

. 0 1 α 1+α 0 0 0 0 0 1 0 1 α 1+α α 0 α 1+α 1 1+α 0 1+α 1 α

Neuer (allerdings ungeeigneter) Ansatz  ⇒  p(α) = α² + 1:

+ 0 1 α 1+α 0 0 1 α 1+α 1 1 0 1+α α α α 1+α 0 1 1+α 1+α α 1 0

. 0 1 α 1+α 0 0 0 0 0 1 0 1 α 1+α α 0 α 1 1+α 1+α 0 1+α 1+α 0

Die Additionstabelle ist in beiden Fällen identisch und auch die Multiplikationstabellen unterscheiden sich nur durch die vier Einträge in den beiden unteren Zeilen und den beiden hinteren Spalten:

• Aus p(α) = 0 folgt nun für das Produkt α · α = 1 und das Produkt (1+α) · (1+α) ergibt das Element 0. Das gemischte Produkt α · (1+α) ist nun 1+α.
  

• In der letzten Zeile der Multipliaktionstabelle und auch in der letzten Spalte steht nun keine „1” ⇒ Hinsichtlich der Bedingung p(α) = α² + 1 = 0 existiert die multiplikative Inverse zu 1+α nicht.
  

• Damit erfüllt aber die endliche Menge {0, 1, α, 1+α} zusammen mit Rechenoperationen modulo p(α) = α² + 1 auch nicht die Voraussetzungen eines Erweiterungskörpers GF(2²).
  
  

Fassen wir zusammen: Aus dem binären Galoisfeld GF(2) = {0, 1} lässt sich unter Zuhilfenahme eines Polynoms vom Grad m = 2 mit binären Koeffizienten,

\[p(x) = x^2 + k_1 \cdot x + k_0 \hspace{0.05cm}, \hspace{0.45cm}k_0\hspace{0.05cm},\hspace{0.1cm}k_1 \in \{0, 1\} \hspace{0.05cm},\]

ein Erweiterungskörper GF(2²) formulieren. Im vorliegenden Fall gibt es nur ein geeignetes Polynom p₁(x) = x² + x + 1. Alle anderen möglichen Polynome vom Grad m = 2, nämlich

\[p_2(x) \hspace{-0.15cm} = \hspace{-0.15cm} x^2 + 1 \hspace{0.06cm} = (x+1) \cdot (x+1)\hspace{0.05cm},\] \[p_3(x) \hspace{-0.15cm} = \hspace{-0.15cm} x^2 \hspace{0.76cm} = x \cdot x \hspace{0.05cm},\] \[p_4(x) \hspace{-0.15cm} = \hspace{-0.15cm} x^2 + x = (x+1) \cdot x \]

lassen sich faktorisieren und ergeben keinen Erweiterungskörper. Man nennt die Polynome p₂(x), p₃(x) und p₄(x) reduzibel.

Anmerkung: Die Umbenennung der Funktionsvariablen α in x hat nur formale Bedeutung im Hinblick auf die folgenden Seiten.

GF(2²) – Beispiel eines Erweiterungskörpers (3)

Wir betrachten weiterhin den Körper GF(2²) = {0, 1, α, 1+α} entsprechend den beiden folgenden Operationstabellen, basierend auf der Nebenbedingung  p(α) = α² + α + 1 = 0 (irreduzibles Ploynom):

+ 0 1 α 1+α 0 0 1 α 1+α 1 1 0 1+α α α α 1+α 0 1 1+α 1+α α 1 0

. 0 1 α 1+α 0 0 0 0 0 1 0 1 α 1+α α 0 α 1+α 1 1+α 0 1+α 1 α

Welche Bedeutung hat aber nun das neue Element α?

• Das Polynom p(α) = α² + α + 1 hat keine Nullstelle in GF(2) = {0, 1}. Das bedeutet weiter, dass α weder 0 noch 1 sein kann.
  

• Wäre α = 0 bzw. α = 1, so wären zudem zwei der vier Mengenelemente {0, 1, α, 1+α} jeweils identisch. Entweder „0” und „α” sowie „1” und „1+α” oder „1” und „α” sowie „0” und „1+α”.
  

• Vielmehr erhält der eindimensionale Körper GF(2) durch die Einführung des Elementes α eine zweite Dimension. Er wird also zum Galoisfeld GF(2²) erweitert, wie die folgende Grafik zeigt.
  

• Das Element α hat ähnliche Bedeutung wie die imaginäre Einheit j, durch die man die Menge der reellen Zahlen unter der Nebenbedingung j² + 1 = 0 zur Menge der komplexen Zahlen erweitert.
  

• Aufgrund der Identität α² = 1 + α, die aus der Nebenbedingung p(α) = 0 folgt, kann man in gleicher Weise GF(2²) = {0, 1, α, α²} schreiben, wobei nun folgende Operationstabellen gelten:

+ 0 1 α α2 0 0 1 α α2 1 1 0 α2 α α α α2 0 1 α2 α2 α 1 0

. 0 1 α α2 0 0 0 0 0 1 0 1 α α2 α 0 α α2 1 α2 0 α2 1 α