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

Im Abschnitt  $\text{Beispiel 2}$  im Kapitel „Einige Grundlagen der Algebra” wurde bereits gezeigt, dass die  endliche Zahlenmenge  $\{0, 1, 2, 3\}$   ⇒   $q = 4$  nicht die Eigenschaften eines Galoisfeldes  $\rm GF(4)$  erfüllt. Vielmehr ergeben sich für die Addition  modulo 4 und die Multiplikation  modulo 4 folgende Tabellen:

$$ \begin{array}{c} {\rm modulo}\hspace{0.15cm}{\it q} = 4\\ \end{array}\hspace{0.25cm} \Rightarrow\hspace{0.25cm}\text{Addition: } \left[ \begin{array}{c|cccccc} + & 0 & 1 &2 & 3 \\ \hline 0 & 0 & 1 &2 & 3 \\ 1 & 1 & 2 &3 & 0 \\ 2 & 2 & 3 &0 & 1 \\ 3 & 3 & 0 &1 & 2 \end{array} \right] \hspace{-0.1cm} ,\hspace{0.25cm}\text{Multiplikation: } \left[ \begin{array}{c|cccccc} \cdot & 0 & 1 &2 & 3 \\ \hline 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 2 & 3 \\ 2 & 0 & 2 & 0 & 2 \\ 3 & 0 & 3 & 2 & 1 \\ \end{array} \right] . $$

Für  $z_i = 2$  gibt es keine multiplikative Inverse  ${\rm Inv_M}(z_i)$. Dies erkennt man daran, dass kein einziges Element  $z_i ∈ \{0, 1, 2, 3\}$  die Bedingung  $2 · z_i = 1$  erfüllt.

Geht man dagegen vom binären Galoisfeld  ${\rm GF}(2) = \{0, 1\}$  aus und erweitert dieses entsprechend der Gleichung

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

so ergibt sich die ebenfalls  endliche Menge  $\{0, 1, \alpha, 1 + \alpha\}$   ⇒   die Ordnung ist weiterhin  $q=4$.

Führt man die Rechenoperationen modulo  $p(\alpha) = \alpha^2 + \alpha + 1$  durch, so erhält man das folgende Ergebnis:

$$ \begin{array}{c} {\rm modulo}\hspace{0.15cm}{\it p}(\alpha)= \alpha^2 + \alpha + 1\\ \end{array}\hspace{0.25cm} \Rightarrow\hspace{0.25cm} \left[ \begin{array}{c|cccccc} + & 0 & 1 & \alpha & 1\!+\!\alpha \\ \hline 0 & 0 & 1 & \alpha & 1\!+\!\alpha \\ 1 & 1 & 0 & 1\!+\!\alpha & \alpha \\ \alpha & \alpha & 1\!+\!\alpha & 0 & 1 \\ 1\!+\!\alpha & 1\!+\!\alpha & \alpha & 1 & 0 \end{array} \right] \hspace{-0.1cm} ,\hspace{0.5cm} \left[ \begin{array}{c|cccccc} \cdot & 0 & 1 & \alpha & 1\!+\!\alpha \\ \hline 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & \alpha & 1\!+\!\alpha \\ \alpha & 0 & \alpha & 1\!+\!\alpha & 1 \\ 1\!+\!\alpha & 0 & 1\!+\!\alpha & 1 & \alpha \end{array} \right] .$$

Hierzu ist anzumerken:

• Die neutralen Elemente der Addition bzw. Multiplikation sind weiterhin  $N_{\rm A} = 0$  und  $N_{\rm M} = 1$.

• Da bei Modulo–Ausführung kein Unterschied zwischen Addition und Subtraktion besteht, ist  $\alpha + \alpha = \alpha - \alpha = 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) = (\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) = (\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) = (\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}.\]

$\text{Zwischenergebnis:}$ 

• Die Menge  $\{0, \ 1, \ \alpha, \ 1 + \alpha\}$  stellt zusammen mit den beiden Operationen Addition  und Multiplikation  modulo  $p(\alpha)= \alpha^2 + \alpha + 1$  ein Galoisfeld dar. Die Ordnung ist  $q = 4$.
• Dieses mit  $\rm GF(2^2) = GF(4)$  bezeichnete Galoisfeld erfüllt alle im  vorherigen Kapitel   genannten Anforderungen.
  
• Im Gegensatz zum Zahlenkörper  $\rm GF(3) = \{0, \ 1, \ 2\}$  mit der Eigenschaft, dass  $q = 3$  eine Primzahl ist, nennt man  $\rm GF(2^2)$  einen  Erweiterungskörper   (englisch:  Extension Field ).

Reduzible und irreduzible Polynome

Das Polynom  $p(\alpha)$  und damit die Bestimmungsgleichung  $p(\alpha) = 0$  darf nicht beliebig vorgegeben werden. Das auf der letzten Seite verwendete Polynom 

$$p(\alpha)= \alpha^2 + \alpha + 1$$

ist geeignet. Nun versuchen wir es mit einem anderen Polynom, nämlich  $p(\alpha)= \alpha^2 + 1$.

$$ \begin{array}{c} {\rm modulo}\hspace{0.15cm}{\it p}(\alpha)= \alpha^2 + 1\\ \end{array}\hspace{0.25cm} \Rightarrow\hspace{0.25cm} \left[ \begin{array}{c|cccccc} + & 0 & 1 & \alpha & 1\!+\!\alpha \\ \hline 0 & 0 & 1 & \alpha & 1\!+\!\alpha \\ 1 & 1 & 0 & 1\!+\!\alpha & \alpha \\ \alpha & \alpha & 1\!+\!\alpha & 0 & 1 \\ 1\!+\!\alpha & 1\!+\!\alpha & \alpha & 1 & 0 \end{array} \right] \hspace{-0.1cm} ,\hspace{0.5cm} \left[ \begin{array}{c|cccccc} \cdot & 0 & 1 & \alpha & 1\!+\!\alpha \\ \hline 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & \alpha & 1\!+\!\alpha \\ \alpha & 0 & \alpha & 1 &1\!+\!\alpha \\ 1\!+\!\alpha & 0 & 1\!+\!\alpha & 1\!+\!\alpha & 0 \end{array} \right] .$$

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(\alpha) = 0$  folgt nun für das Produkt  $\alpha \cdot \alpha = 1$  und das Produkt  $(1 +\alpha) \cdot (1 +\alpha) $  ergibt das Nullelement. Das gemischte Produkt ist  $\alpha \cdot (1 +\alpha) = 1 +\alpha $.
  

• In der letzten Zeile der Multiplikationstabelle und auch in der letzten Spalte steht nun keine „$1$”   ⇒   Hinsichtlich der Bedingung  $p(\alpha)= \alpha^2 + 1= 0$  existiert demzufolge die multiplikative Inverse zu  $1 +\alpha$  nicht.
  

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

$\text{Fassen wir zusammen:}$ 

Aus dem binären Galoisfeld  $\rm 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  $\rm GF(2^2)$  formulieren.   Anmerkung:   Die Umbenennung der Variablen  $\alpha$  in  $x$  hat nur formale Bedeutung im Hinblick auf spätere Seiten.

• Im vorliegenden Fall gibt es nur ein geeignetes Polynom  $p_1(x)= x^2 + x + 1$. Alle anderen möglichen Polynome vom Grad  $m = 2$, nämlich

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

\[p_3(x) =x^2 \hspace{0.76cm} = x \cdot x \hspace{0.05cm},\]

\[p_4(x) = x^2 + x = (x+1) \cdot x\hspace{0.05cm}, \]

lassen sich faktorisieren und ergeben keinen Erweiterungskörper.

• Man nennt die Polynome  $p_2(x)$,  $p_3(x)$  und  $p_4(x)$  reduzibel.
• Der Schluss liegt nahe, dass für einen Erweiterungskörper nur  irreduzible Polynome  wie  $p_1(x)$  geeignet sind.

Interpretation des neuen Elementes „alpha”

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

$$ \begin{array}{c} {\rm modulo}\hspace{0.15cm} p(\alpha)= \alpha^2 + \alpha + 1\\ \end{array}\hspace{0.25cm} \Rightarrow\hspace{0.25cm} \left[ \begin{array}{c|cccccc} + & 0 & 1 & \alpha & 1\!+\!\alpha \\ \hline 0 & 0 & 1 & \alpha & 1\!+\!\alpha \\ 1 & 1 & 0 & 1\!+\!\alpha & \alpha \\ \alpha & \alpha & 1\!+\!\alpha & 0 & 1 \\ 1\!+\!\alpha & 1\!+\!\alpha & \alpha & 1 & 0 \end{array} \right] \hspace{-0.1cm} ,\hspace{0.5cm} \left[ \begin{array}{c|cccccc} \cdot & 0 & 1 & \alpha & 1\!+\!\alpha \\ \hline 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & \alpha & 1\!+\!\alpha \\ \alpha & 0 & \alpha & 1\!+\!\alpha & 1 \\ 1\!+\!\alpha & 0 & 1\!+\!\alpha & 1 & \alpha \end{array} \right] .$$

Übergang von  ${\rm GF}(2)$  auf  ${\rm GF}(2^2)$

Welche Bedeutung hat aber nun das neue Element $\alpha$?

• Das Polynom  $p(\alpha)= \alpha^2 + \alpha + 1 $  hat in  ${\rm GF}(2) = \{0, \ 1\}$  keine Nullstelle. Das bedeutet weiter, dass  $\alpha$  weder  $0$  noch  $1$  sein kann.
  

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

• Vielmehr erhält der eindimensionale Körper  ${\rm GF}(2)$  durch die Einführung des Elementes  $\alpha$  eine zweite Dimension. Er wird also zum Galoisfeld  ${\rm GF}(2^2)$  erweitert, wie die nebenstehende Grafik zeigt.

• Das Element  $\alpha$  hat ähnliche Bedeutung wie die imaginäre Einheit  ${\rm j}$, durch die man die Menge der reellen Zahlen unter der Nebenbedingung  ${\rm j}^2 + 1 = 0$  zur Menge der komplexen Zahlen erweitert.

$\text{Übliche Darstellung des binären Erweiterungskörpers}\ {\rm GF}(2^2)\text{:}$

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

$$ \begin{array}{c} {\rm modulo}\hspace{0.15cm} p(\alpha)= \alpha^2 + \alpha + 1\\ \end{array}\hspace{0.25cm} \Rightarrow\hspace{0.25cm} \left[ \begin{array}{c | cccccc} + & 0 & 1 & \alpha & \alpha^2 \\ \hline 0 & 0 & 1 & \alpha & \alpha^2 \\ 1 & 1 & 0 & \alpha^2 & \alpha \\ \alpha & \alpha & \alpha^2 & 0 & 1 \\ \alpha^2 & \alpha^2 & \alpha & 1 & 0 \end{array} \right] \hspace{-0.1cm} ,\hspace{0.5cm} \left[ \begin{array}{c | cccccc} \cdot & 0 & 1 & \alpha & \alpha^2 \\ \hline 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & \alpha & \alpha^2 \\ \alpha & 0 & \alpha &\alpha^2 & 1 \\ \alpha^2 & 0 & \alpha^2 & 1 & \alpha \end{array} \right] .$$

Polynome über einem endlichen Körper

$\text{Definition:}$  Ein  Polynom  in einem endlichen Körper  ${\rm GF}(P)$, wobei  $P$  eine Primzahl angibt, hat folgende Form:

\[a(x) = \sum_{i = 0}^{m} a_i \cdot x^{i} = a_0 + a_1 \cdot x + a_2 \cdot x^2 + \hspace{0.1cm}\text{...} \hspace{0.1cm} + a_m \cdot x^{m} \hspace{0.05cm}.\]

Anzumerken ist:

• Alle Koeffizienten  $a_i $  sind Elemente des Körpers:   $a_i \in {\rm GF}(P)$.
  

• Ist der führende Koeffizient  $a_m ≠ 0$, so gibt  $m$ den  Grad  des Polynoms an.

Betrachten wir ein dazu zweites Polynom mit Grad  $M$,

\[b(x) = \sum_{i = 0}^{M} b_i \cdot x^{i} = b_0 + b_1 \cdot x + b_2 \cdot x^2 + \hspace{0.1cm}\text{...} \hspace{0.1cm} + b_M \cdot x^{M} \hspace{0.05cm},\]

so erhält man für die Summe (bzw. Differenz) und das Produkt jeweils in  ${\rm GF}(P)$:

\[a(x) \pm b(x) = \sum_{i = 0}^{{\rm max}\hspace{0.05cm}(m, \hspace{0.05cm}M)} \hspace{0.15cm}(a_i \pm b_i) \cdot x^{i} \hspace{0.05cm},\]

\[a(x) \cdot b(x) = \sum_{i = 0}^{m + M} \hspace{0.15cm}c_i \cdot x^{i}\hspace{0.05cm},\hspace{0.5cm} c_i = \sum_{j = 0}^{i}\hspace{0.15cm}a_j \cdot b_{i-j} \hspace{0.05cm}.\]

$\text{Beispiel 1:}$  Es gelte  $a(x) = x^3 + x + 1$   und  $b(x) = x^2 + x + 1$.

Im binären Galoisfeld    ⇒   ${\rm GF}(2)$  ergibt sich nach den obigen Gleichungen für die Summe, die Differenz und das Produkt der beiden Polynome:

\[s(x) = a(x) + b(x) = x^3 + x^2 \hspace{0.05cm}, \]

\[d(x) = a(x) - b(x) = x^3 + x^2 = s(x)\hspace{0.05cm},\]

\[c(x) = a(x) \cdot b(x) =\sum_{i = 0}^{3 + 2} \hspace{0.15cm}c_i \cdot x^{i}\hspace{0.05cm},\hspace{0.5cm} c_i = \sum_{j = 0}^{i}\hspace{0.15cm}a_j \cdot b_{i-j} \hspace{0.05cm}.\]

Mit  $a_0 = a_1 = a_3 = b_0 = b_1 =b_2 = 1$   und   $a_2 = a_4 = a_5 = b_3 = b_4 =b_5 = 0$  erhält man:

\[c_0 = a_0 \cdot b_0 = 1 \cdot 1 = 1 \hspace{0.05cm},\]

\[c_1 = a_0 \cdot b_1 + a_1 \cdot b_0 = 1 \cdot 1 + 1 \cdot 1 = 0 \hspace{0.05cm},\]

\[c_2 =a_0 \cdot b_2 + a_1 \cdot b_1 + a_2 \cdot b_0 = 1 \cdot 1 + 1 \cdot 1 + 0 \cdot 1 = 0 \hspace{0.05cm},\]

\[c_3 = a_0 \cdot b_3 + a_1 \cdot b_2 + a_2 \cdot b_1 + a_3 \cdot b_0 = 1 \cdot 0 + 1 \cdot 1 + 0 \cdot 1 + 1 \cdot 1 = 0 \hspace{0.05cm},\]

\[c_4=a_0 \cdot b_4 + a_1 \cdot b_3 + \hspace{0.05cm}\text{...}\hspace{0.05cm}+ \hspace{0.05cm}a_4 \cdot b_0 =1 \cdot 0 + 1 \cdot 0 + 0 \cdot 1 + 1 \cdot 1 + 0 \cdot 1 = 1 \hspace{0.05cm},\]

\[c_5 = a_0 \cdot b_5 + a_1 \cdot b_4 + \hspace{0.05cm}\text{...}\hspace{0.05cm}+ \hspace{0.05cm} a_5 \cdot b_0 =1 \cdot 0 + 1 \cdot 0 + 0 \cdot 0 + 1 \cdot 1 + 0 \cdot 1 + 0 \cdot 1= 1 \]

\[\Rightarrow \hspace{0.3cm} c(x) = x^5 + x^4 +1 \hspace{0.05cm}.\]

Im Galoisfeld  ${\rm GF}(3)$  erhält man aufgrund der Modulo–3–Operationen andere Ergebnisse:

\[s(x) = (x^3 + x + 1) + (x^2 + x + 1) = x^3 + x^2 + 2x + 2\hspace{0.05cm},\]

\[d(x) = (x^3 + x + 1) - (x^2 + x + 1) = x^3 + 2x^2 \hspace{0.05cm},\]

\[c(x) = (x^3 + x + 1) \cdot (x^2 + x + 1) = x^5 + x^4 + 2x^3 + 2x^2 + 2x +1\hspace{0.05cm}.\]

$\text{Definition:}$  Ein Polynom  $a(x)$  bezeichnet man als  reduzibel  (englisch:  reducible), 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) \hspace{0.05cm}.\]

Ist diese Faktorisierung nicht möglich, das heißt, wenn

\[a(x) = p(x) \cdot q(x) + r(x)\hspace{0.05cm},\hspace{0.5cm} r(x) \ne 0\]

gilt, so spricht man von einem  irreduziblen  (englisch:  irreducible oder prime) Polynom.

$\text{Beispiel 2:}$  Es gelte  $b(x) = x^3 + x + 1$,    $p_1(x) = x^2 + x + 1$   und   $p_2(x) = x^2 + 1$.

Die Grafik verdeutlicht links die Modulo–2–Multiplikation  $a(x)= b(x) \cdot p_1(x)$. Das Ergebnis ist  $a(x) = x^5 + x^4 + 1$.

Beispiel für Polynom–Multiplikation und –Division

Im rechten Teil der obigen Grafik ist die Modulo–2–Division  $q(x)= a(x)/ p_2(x)$  mit dem Ergebnis  $q(x) = x^3 + x^2 + x + 1$  dargestellt. Es verbleibt der Rest  $r(x) = x$. Allein nach dieser Rechnung könnte  $a(x) = x^5 + x^4 + 1$  durchaus ein irreduzibles Polynom sein.

Der Nachweis, dass das Polynom  $a(x) = x^5 + x^4 + 1$  tatsächlich irreduzibel ist, wäre allerdings erst dann erbracht, wenn  $a(x)/p(x)$  für alle

\[p(x) = \sum_{i = 0}^{m} a_i \cdot x^{i} = a_m \cdot x^{m} + a_{m-1} \cdot x^{m-1} + \hspace{0.1cm}\text{...} \hspace{0.1cm}+ a_2 \cdot x^2 + a_1 \cdot x + a_0 \hspace{0.05cm}\]

einen Rest  $r(x) ≠ 0$  liefert. Dies würde im vorliegenden Beispiel (nahezu)  $2^5 = 32$  Divisionen erfordern.

Aufgrund unserer linken Berechnung können wir hier sofort erkennen, dass  $a(x)$  mit Sicherheit kein irreduzibles Polynom ist, da zum Beispiel  $a(x) = x^5 + x^4 + 1$  dividiert durch  $p_1(x) = x^2 + x + 1$  das Polynom  $b(x) = x^3 + x + 1$  ohne Rest ergibt.

Verallgemeinerte Definition eines Erweiterungskörpers

Wir gehen von folgenden Voraussetzungen aus:

• einem Galoisfeld ${\rm GF}(P)$, wobei $P$ eine Primzahl angibt,
  

• einem irreduziblen Polynom $p(x)$ über ${\rm GF}(P)$ mit dem Grad $m$:

\[p(x) = a_m \cdot x^{m} + a_{m-1} \cdot x^{m-1} + \hspace{0.1cm}\text{...} \hspace{0.1cm}+ a_2 \cdot x^2 + a_1 \cdot x + a_0 \hspace{0.05cm}, \hspace{0.3cm} a_i \in {\rm G}(P)\hspace{0.05cm}, \hspace{0.15cm}a_m \ne 0\hspace{0.05cm}. \]

Mit den genannten Voraussetzungen gilt allgemein:

$\text{Definition:}$  Es sei $P$ eine Primzahl, $m$ ganzzahlig, $p(x)$ ein irreduzibles Polynom vom Grad $m$ und es gelte $p(\alpha) = 0$.

Ein Erweiterungskörper lässt sich dann wie folgt beschreiben.

\[{\rm GF}(P^m)= \Big\{ k_{m-1} \hspace{0.01cm}\cdot \hspace{0.02cm}\alpha^{m-1} \hspace{0.05cm}+ \hspace{0.05cm}\text{...} \hspace{0.05cm}+ \hspace{0.05cm}k_1 \hspace{0.01cm}\cdot \hspace{0.02cm} \alpha \hspace{0.05cm}+ \hspace{0.05cm} k_0\hspace{0.05cm} \Big{\vert}\hspace{0.02cm} \ k_i\in{\rm GF}(P) = \{ 0, 1, \hspace{0.05cm}\text{...} \hspace{0.05cm}, P-1\}\Big \}\]

• Die Addition und Multiplikation in diesem Erweiterungskörper entspricht dann der Polynomaddition und Polynommultiplikation modulo $p(\alpha)$.
  

• Ein Galoisfeld ${\rm GF}(q)$ mit $q$ Elementen lässt sich also immer dann angeben, wenn die Elementenanzahl in der Form $q = P^m$ geschrieben werden kann ($P$ kennzeichnet eine Primzahl, $m$ sei ganzzahlig).

Mögliche Galoisfelder ${\rm GF}(q)$ für $q ≤ 64$

Die Grafik zeigt, für welche $q$–Werte sich jeweils ein Galoisfeld konstruieren lässt. Für die schraffiert eingezeichneten Werte ist kein endlicher Körper angebbar. Weiter ist anzumerken:

• Die gelb hinterlegten Positionen $q=P$   ⇒   $m = 1$ markieren Zahlenmengen $\{0, 1,\hspace{0.05cm}\text{ ...} \hspace{0.05cm}, q- 1\}$ mit Galoiseigenschaften, siehe Seite Definition eines Galoisfeldes.
  

• Die anderen farblich hinterlegten Positionen markieren Erweiterungskörper mit $q=P^m$,   $m ≥ 2$. Für $q ≤ 64$ basieren diese auf den Primzahlen $2$, $3$, $5$ und $7$.
  

• Mit roter Schrift hervorgehoben sind binäre Körper   ⇒   $q=2^m$,   $m ≥ 1$, die auf der nächsten Seite noch genauer betrachtet werden. Alle anderen Erweiterungskörper sind blau beschriftet.
  

Binäre Erweiterungskörper – Primitive Polynome

Im Folgenden betrachten wir binäre Erweiterungskörper mit

\[q = 2^m \hspace{0.15cm}(m \ge 2) \hspace{0.3cm} \Rightarrow\hspace{0.3cm} q = 4, 8, 16, 32, 64, \text{...}\]

Elementen. In der Tabelle sind für $2 ≤ m ≤ 6$ alle irreduziblen Polynome des Galoisfeldes ${\rm GF}(2)$ angegeben. Die Polynome in Spalte 2 und 3 sind nicht nur irreduzibel, sondern zusätzlich auch primitiv.

Hinweis:   Primitive Polynome liefern auch die Grundlage für die Realisierung von Pseudo–Noise–Generatoren.

Irreduzible und primitive Polynome

Bevor wir uns der Definition eines primitiven Polynoms zuwenden, sollen zunächst die Besonderheiten solcher primitiver Elemente am Beispiel von

\[{\rm GF}(q) = \{\hspace{0.05cm}z_0 = 0,\hspace{0.1cm} z_1 = 1,\hspace{0.05cm} \text{...}\hspace{0.05cm} , \hspace{0.05cm}z_{q-1}\}\]

genannt werden. Das Element $z_i = \beta$ wird dann als primitiv bezeichnet,

• wenn die Potenz $\beta^{\hspace{0.05cm}i}$ modulo $q$ zum ersten Mal für $i = q-1$ zum Ergebnis „$1$” führt, so dass
  

• $\beta^{\hspace{0.05cm}i}$ für $1 ≤ i ≤ q- 1$ genau die Elemente $z_1$, ... , $z_{q-1}$ liefert, also alle Elemente von ${\rm GF}(q)$ mit Ausnahme des Nullelementes $z_0 = 0$.
  

$\text{Beispiel 3:}$  Von der Zahlenmenge $Z_5 = \{0, 1, 2, 3, 4\}$ sind „$2$” und „$3$” primitive Elemente wegen

\[2^1 \hspace{-0.1cm} = \hspace{-0.1cm} 2\hspace{0.05cm},\hspace{0.2cm} 2^2 = 4\hspace{0.05cm},\hspace{0.2cm} 2^3 = 8 \hspace{0.1cm}{\rm mod} \hspace{0.1cm} 5 = 3\hspace{0.05cm},\hspace{0.2cm} 2^4 = 16 \hspace{0.1cm}{\rm mod} \hspace{0.1cm} 5 = 1\hspace{0.05cm},\]

\[3^1 \hspace{-0.1cm} = \hspace{-0.1cm} 3\hspace{0.05cm},\hspace{0.2cm} 3^2 = 9\hspace{0.1cm}{\rm mod} \hspace{0.1cm} 5 = 4\hspace{0.05cm},\hspace{0.2cm} 3^3 = 27 \hspace{0.1cm}{\rm mod} \hspace{0.1cm} 5 = 2\hspace{0.05cm},\hspace{0.2cm} 3^4 = 81 \hspace{0.1cm}{\rm mod} \hspace{0.1cm} 5 = 1\]

• Dagegen ist „$4$” kein primitives Element, weil bereits $4^2 = 1$ ist:

\[4^1 = 4\hspace{0.05cm},\hspace{0.2cm} 4^2 = 16 \hspace{0.1cm}{\rm mod} \hspace{0.1cm} 5 = 1\hspace{0.05cm},\hspace{0.2cm} 4^3 = 64 \hspace{0.1cm}{\rm mod} \hspace{0.1cm} 5 = 4\hspace{0.05cm},\hspace{0.2cm} 4^4 = 256 \hspace{0.1cm}{\rm mod} \hspace{0.1cm} 5 = 1\hspace{0.05cm}.\]

$\text{Definition:}$  Ein irreduzibles Polynom bezeichnet man gleichzeitig als ein primitives Polynom, wenn die Wurzel $\alpha$ bezüglich des Polynoms $p(x)$ ein primitives Element von ${\rm GF}(q)$ ist. Dann gilt

\[{\rm GF}(q) = \{\hspace{0.1cm}\alpha^{-\infty} = 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} \text{...} \hspace{0.1cm} , \hspace{0.1cm}\alpha^{q-2}\hspace{0.1cm}\}\hspace{0.05cm}. \]

• Alle in Spalte 2 der obigen Tabelle angegebenen Polynome sind sowohl irreduzibel als auch primitiv. Ist $p_1(x)$ ein primitives Polynom, so ist auch das dazu reziproke Polynom $p_2 (x) = x^m \cdot p_1(x^{-1})$ primitiv.
• Alle Polynome in Spalte 3 sind reziprok zum Polynom in Spalte 2. Beispielsweise gilt für $m = 3$:

\[p_1(x) = x^3 + x + 1 \hspace{0.3cm} \Rightarrow\hspace{0.3cm}p_2(x) = x^3 \cdot [x^{-3} + x^{-1} + 1 ]= x^3 + x^2 + 1 \hspace{0.05cm}.\]

• Die irreduziblen Polynome der Spalte 4 sind dagegen nicht primitiv; sie spielen nur eine untergeordnete Rolle zur Beschreibung von Fehlerkorrekturverfahren.
  

$\text{Beispiel 4:}$  Zur Verdeutlichung dieser Aussagen betrachten wir beispielhaft

• das Galoisfeld $\rm GF(2^3) = GF(8)$, sowie
  
• das Polynom $p(x) = x^3 + x + 1$.
  
  

Aus der Bedingung $p(\alpha) = 0$ erhält man in $\rm GF(2^3)$ weiter:

\[\alpha^3 + \alpha + 1 = 0 \hspace{0.3cm} \Rightarrow\hspace{0.3cm}\alpha^3 = \alpha + 1 \hspace{0.05cm},\]

und damit für die Potenzen $\alpha^{i}$ der Wurzel für $i ≥ 4$:

\[\alpha^4 = \alpha \cdot \alpha^3 = \alpha \cdot (\alpha + 1) = \alpha^2 + \alpha \hspace{0.05cm},\]

\[\alpha^5 = \alpha^2 \cdot \alpha^3 = \alpha^2 \cdot (\alpha + 1) = \alpha^3 + \alpha^2 = \alpha^2 + \alpha + 1 \hspace{0.05cm},\]

\[\alpha^6 = \alpha^3 \cdot \alpha^3 = (\alpha + 1) \cdot (\alpha + 1) = \alpha^2 + \alpha + \alpha + 1= \alpha^2 + 1 \hspace{0.05cm},\]

\[\alpha^7 = \alpha^4 \cdot \alpha^3 = (\alpha^2 + \alpha) \cdot (\alpha + 1) = \alpha^3 + \alpha^2 + \alpha^2 + \alpha = \alpha + 1 + \alpha = 1 = \alpha^0 \hspace{0.05cm}.\]

$\text{Beispiel 5:}$  Die Elemente $z_0$, $z_1$, ... , $z_7$ des Galoisfeldes $\rm GF(2^3)$ lassen sich entsprechend der nebenstehenden Tabelle wie folgt darstellen:

Elemente von $\rm GF(2^3)$ in drei verschiedenen Darstellungen

• als Potenzen von $\alpha$   ⇒   Exponentendarstellung,
  

• als Polynome der Form $k_2 \cdot \alpha^2 + k_1 \cdot \alpha + k_0$ mit binären Koeffizienten $k_2$, $k_1$, $k_0$ (jeweils $0$ oder $1$)   ⇒   Polynomdarstellung,
  

• als Vektoren der Koeffizienten $(k_2, \ k_1, \ k_0)$   ⇒   Koeffizientendarstellung.
  
  

Für Addition (oder Subtraktion) zweier Elemente eignen sich Polynom– und Vektordarstellung gleichermaßen, wobei die Komponenten modulo 2 zu addieren sind, zum Beispiel:

\[z_5 + z_7 =(\alpha^2 + \alpha) + (\alpha^2 + 1) = \alpha + 1 = \alpha^3 = z_4 \hspace{0.05cm},\]

\[{\rm oder}\hspace{0.15cm} z_5 + z_7 =(110) + (101) = (011) = z_4 \hspace{0.05cm},\]

\[\hspace{0.15cm} z_1 + z_2 + z_3 =(001) + (010) + (100)= (111) = z_6 \hspace{0.05cm}.\]

Für Multiplikationen ist die Exponentendarstellung gut geeignet, wie folgende Beispiele zeigen:

$\rm GF(2^3)$ in 3D–Darstellung

\[z_3 \cdot z_4 =\alpha^2 \cdot \alpha^3 = \alpha^{2+3}= \alpha^{5} = z_6 \hspace{0.05cm},\]

\[z_0 \cdot z_5 =\alpha^{-\infty} \cdot \alpha^4 = \alpha^{-\infty} = z_0 \hspace{0.05cm},\]

\[z_5 \cdot z_7 = \alpha^4 \cdot \alpha^6 = \alpha^{10}= \alpha^{7} \cdot \alpha^{3} = 1 \cdot \alpha^{3}= z_4 \hspace{0.05cm}.\]

Man erkennt, dass sich die Exponenten modulo $q-1$ ergeben (im Beispiel modulo $7$).

Die Grafik zeigt den endlichen Erweiterungskörper $\rm GF(2^3)$ in einer 3D–Darstellung:

• Die Achsen sind mit $\alpha^0 =1$, $\alpha^1$ und $\alpha^2$ bezeichnet.
• Die $2^3 = 8$ Punkte im 3D–Raum sind mit den Koeffizientenvektoren beschriftet.
• Die Zuordnung der Koeffizienten $k_2$, $k_1$, $k_0$ zu den Achsen ist farblich deutlich gemacht.

Aufgaben zum Kapitel

Aufgabe 2.3: Reduzible und irreduzible Polynome

Aufgabe 2.3Z: Polynomdivision

Aufgabe 2.4: $\rm GF(2^2)$–Darstellungsformen

Aufgabe 2.4Z: Endliche und unendliche Körper

Aufgabe 2.5: Drei Varianten von $\rm GF(2^4)$

Aufgabe 2.5Z: Einige Berechnungen über $\rm GF(2^3)$

Aufgabe 2.6: ${\rm GF}(P^m)$. Welches $P$, welches $m$?