Kanalcodierung/Einige Grundlagen der Algebra

1. Kanalcodierung
2. Reed–Solomon–Codes und deren Decodierung
3. Einige Grundlagen der Algebra

• Vorherige Seite
• Nächste Seite

• Vorherige Seite
• Nächste Seite

Definition eines Galoisfeldes

Bevor wir uns der Beschreibung der Reed–Solomon–Codes zuwenden können, benötigen wir einige algebraische Grundbegriffe. Beginnen wir mit den Eigenschaften eines Galoisfeldes GF(q), benannt nach dem Franzosen Évariste Galois, dessen Biografie für einen Mathematiker eher ungewöhnlich ist.

: Ein Galoisfeld GF(q) ist ein endlicher Körper mit q Elementen z₀, z₁, ... , z_q–1, wenn alle acht nachfolgend aufgeführten Aussagen hinsichtlich der Addition („+”) und der Multiplikation („·”) zutreffen. Addition und Multiplikation sind hierbei modulo q zu verstehen.

(A)  GF(q) ist in sich abgeschlossen  ⇒  Closure:

\[\forall \hspace{0.15cm} z_i \in {\rm GF}(q),\hspace{0.15cm} z_j \in {\rm GF}(q): \hspace{0.25cm}(z_i + z_j)\in {\rm GF}(q),\hspace{0.15cm}(z_i \cdot z_j)\in {\rm GF}(q) \hspace{0.05cm}. \]

(B)  Es gibt ein hinsichtlich der Addition neutrales Element N_A, das man oft auch als das Nullelement bezeichnet  ⇒  Identity for „+”:

\[\exists \hspace{0.15cm} z_j \in {\rm GF}(q) : \hspace{0.25cm}z_i + z_j = z_i \hspace{0.25cm} \Rightarrow \hspace{0.25cm} z_j = N_{\rm A} = {\rm "0"} \hspace{0.25cm}{\rm (Nullelement)} \hspace{0.05cm}.\]

(C)  Es gibt ein hinsichtlich der Multiplikation neutrales Element N_M, das oft auch als das Einselement bezeichnet wird  ⇒  Identity for „·”:

\[\exists \hspace{0.15cm} z_j \in {\rm GF}(q) : \hspace{0.25cm}z_i \cdot z_j = z_i \hspace{0.25cm} \Rightarrow \hspace{0.25cm} z_j = N_{\rm M} = {\rm "1"} \hspace{0.25cm}{\rm (Einselement)} \hspace{0.05cm}. \]

(D)  Für jedes z_i existiert eine additive Inverse  ⇒  Inverse for „+”:

\[\forall \hspace{0.15cm} z_i \in {\rm GF}(q),\hspace{0.15cm} \exists \hspace{0.15cm} {\rm Inv_A}(z_i) \in {\rm GF}(q): \hspace{0.25cm}z_i + {\rm Inv_A}(z_i) = N_{\rm A} = {\rm "0"} \]

\[ \Rightarrow \hspace{0.25cm}{\rm kurz:}\hspace{0.15cm} {\rm Inv_A}(z_i) = - z_i \hspace{0.05cm}. \]

(E)  Für jedes z_i mit Ausnahme des Nullelements existiert die multiplikative Inverse ⇒ Inverse for „·”:

\[\forall \hspace{0.15cm} z_i \in {\rm GF}(q),\hspace{0.15cm} z_i \ne N_{\rm A}, \hspace{0.15cm} \exists \hspace{0.15cm} {\rm Inv_M}(z_i) \in {\rm GF}(q): \hspace{0.25cm}z_i \cdot {\rm Inv_M}(z_i) = N_{\rm M} = {\rm "1"}\]

\[\Rightarrow \hspace{0.25cm}{\rm kurz:}\hspace{0.15cm} {\rm Inv_M}(z_i) = z_i^{-1} \hspace{0.05cm}. \]

(F)  Für Addition und Multiplikation gilt jeweils das Kommutativgesetz  ⇒  Commutative Law:

\[\forall \hspace{0.15cm} z_i \in {\rm GF}(q),\hspace{0.15cm} z_j \in {\rm GF}(q): \hspace{0.25cm}z_i + z_j = z_j + z_i ,\hspace{0.15cm}z_i \cdot z_j = z_j \cdot z_i \hspace{0.05cm}.\]

(G)  Für Addition und Multiplikation gilt jeweils das Assoziativgesetz  ⇒  Associative Law:

\[\forall \hspace{0.15cm} z_i,\hspace{0.1cm} z_j ,\hspace{0.1cm} z_k \in {\rm GF}(q): \hspace{0.25cm}(z_i + z_j) + z_k = z_i + (z_j + z_k ),\hspace{0.15cm}(z_i \cdot z_j) \cdot z_k = z_i \cdot (z_j \cdot z_k ) \hspace{0.05cm}.\]

(H)  Für die Kombination „Addition – Multiplikation” gilt das Distributivgesetz  ⇒  Distributive Law:

\[\forall \hspace{0.15cm} z_i,\hspace{0.15cm} z_j ,\hspace{0.15cm} z_k \in {\rm GF}(q): \hspace{0.25cm}(z_i + z_j) \cdot z_k = z_i \cdot z_k + z_j \cdot z_k \hspace{0.05cm}.\]

Es sei nochmals darauf hingewiesen, dass Addition („+”) und Multiplikation („·”) modulo q zu verstehen sind. Hierbei bezeichnet die Ordnung q die Anzahl der Elemente des Galoisfeldes.

Beispiele und Eigenschaften von Galoisfeldern

Wir überprüfen zunächst, ob für die binäre Zahlenmenge Z₂ = {0, 1}  ⇒  q = 2 (gültig für den einfachen Binärcode) die auf der letzten Seite genannten acht Kriterien tatsächlich erfüllt werden, so dass man tatsächlich von „GF(2)” sprechen kann. Sie sehen nachfolgend die Additions– und Multiplikationstabelle:

\[Z_2 = {0, 1 } \hspace{0.35cm} \Rightarrow \hspace{0.35cm}\]

+ 0 1 0 0 1 1 1 0

. 0 1 0 0 0 1 0 1

\[\hspace{0.35cm} \Rightarrow \hspace{0.35cm}{\rm GF}(2) \hspace{0.05cm}.\]

Man erkennt aus dieser Darstellung:

• Jedes Element der Additions– und der Multiplikationstabelle von Z₂ ist wieder entweder z₀ = 0 oder z₁ = 1  ⇒  das Kriterium (A) ist erfüllt.
  

• Die Zahlenmenge Z₂ enthält das Nullelement (N_A = z₀ = 0) und das Einselement (N_M = z₁ = 1)  ⇒  die Kriterien (B) und (C) sind ebenfalls erfüllt.
  

• Die additiven Inversen Inv_A(0) = 0 und Inv_A(1) = (–1) mod 2 = 1 existieren und gehören zu Z₂. Ebenso gibt es die multiplikative Inverse Inv_M(1) = 1  ⇒  die Kriterien (D) und (E) sind erfüllt.
  

• Die Gültigkeit des Kommutativgesetzes (F) in der Menge Z₂ erkennt man an der Symmetrie bezüglich der Tabellendiagonalen. Die Kriterien (G) und (H) werden hier ebenfalls erfüllt.
  
  

Die Zahlenmenge Z₃ = {0, 1, 2}  ⇒  q = 3 erfüllt alle acht Kriterien und ist somit ein Galoisfeld GF(3):

\[Z_3 = \{0, 1, 2 \} \hspace{0.35cm} \Rightarrow \hspace{0.35cm}\]

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

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

\[\hspace{0.35cm} \Rightarrow \hspace{0.35cm}{\rm GF}(3) \hspace{0.05cm}. \]

Dagegen ist die Zahlenmenge Z₄ = {0, 1, 2, 3}  ⇒  q = 4 kein Galoisfeld. Der Grund hierfür ist, dass es hier zum Element z₂ = 2 keine multiplikative Inverse gibt. Bei einem Galoisfeld müsste nämlich gelten: <nobr>2 · Inv_M(2) = 1.</nobr> In nachfolgender Multiplikationstabelle gibt es aber in der dritten Zeile und in der dritten Spalte (jeweils gültig für den Multiplikanden z₂ = 2) keinen Eintrag mit „1”.

\[Z_4 = \{0, 1, 2, 3 \} \hspace{0.35cm} \Rightarrow \hspace{0.35cm}\]

+ 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

\[\hspace{0.35cm} \Rightarrow \hspace{0.35cm}{\rm kein \hspace{0.15cm}GF}(4) \hspace{0.05cm}. \]

Das Ergebnis dieser Seite soll hier ohne weiteren Beweis verallgemeinert werden:

• Ein Galoisfeld GF(q) kann in der hier beschriebenen Weise als Ring von Integergrößen modulo q nur dann gebildet werden, wenn q eine Primzahl ist: q = 2, q = 3, q = 5, q = 7, q = 11, ...
  

• Kann man aber die Ordnung q in der Form q = P^m mit einer Primzahl P und ganzzahligem m ausdrücken, so lässt sich das Galoisfeld GF(q) über einen Erweiterungskörper finden.