Einige Grundlagen der Algebra
Inhaltsverzeichnis
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.
(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 NA, 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 NM, 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 zi 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 zi 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 Z2 = {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}\]
|
|
\[\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 Z2 ist wieder entweder z0 = 0 oder z1 = 1 ⇒ das Kriterium (A) ist erfüllt.
- Die Zahlenmenge Z2 enthält das Nullelement (NA = z0 = 0) und das Einselement (NM = z1 = 1) ⇒ die Kriterien (B) und (C) sind ebenfalls erfüllt.
- Die additiven Inversen InvA(0) = 0 und InvA(1) = (–1) mod 2 = 1 existieren und gehören zu Z2. Ebenso gibt es die multiplikative Inverse InvM(1) = 1 ⇒ die Kriterien (D) und (E) sind erfüllt.
- Die Gültigkeit des Kommutativgesetzes (F) in der Menge Z2 erkennt man an der Symmetrie bezüglich der Tabellendiagonalen. Die Kriterien (G) und (H) werden hier ebenfalls erfüllt.
Die Zahlenmenge Z3 = {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}\]
|
|
\[\hspace{0.35cm} \Rightarrow \hspace{0.35cm}{\rm GF}(3) \hspace{0.05cm}. \]
Dagegen ist die Zahlenmenge Z4 = {0, 1, 2, 3} ⇒ q = 4 kein Galoisfeld. Der Grund hierfür ist, dass es hier zum Element z2 = 2 keine multiplikative Inverse gibt. Bei einem Galoisfeld müsste nämlich gelten: <nobr>2 · InvM(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 z2 = 2) keinen Eintrag mit „1”.
\[Z_4 = \{0, 1, 2, 3 \} \hspace{0.35cm} \Rightarrow \hspace{0.35cm}\]
|
|
\[\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 = Pm mit einer Primzahl P und ganzzahligem m ausdrücken, so lässt sich das Galoisfeld GF(q) über einen Erweiterungskörper finden.
Gruppe, Ring, Körper – algebraische Grundbegriffe
Auf den beiden ersten Seiten sind bereits einige algebraische Grundbegriffe gefallen, ohne dass deren Bedeutungen genauer erläutert wurden. Dies soll nun in aller Kürze aus Sicht eines Nachrichtentechnikers nachgeholt werden, wobei wir uns vorwiegend auf die Darstellung in [Fri96][1] und [KM+08][2] beziehen. Zusammenfassend lässt sich sagen:
Die folgende Grafik verdeutlicht schrittweise, wie sich aus einer Menge durch Definition von Additition, Multiplikation und Division innerhalb dieser Menge eine Gruppe, ein Ring und ein Körper ergibt. Weiter angegeben sind in der Grafik auch in der Literatur häufig verwendete Schriftzeichen für eine Menge, eine Gruppe, einen Ring, einen Körper und einen endlichen Körper. Aufgrund von Restriktionen durch den HTML–Zeichensatz benutzen wir in LNTwww die Zeichen M, G, R, K (bzw. F) sowie GF(q).
Auf den beiden nächsten Seiten werden die hier genannten algebraischen Begriffe noch etwas genauer behandelt. Zum Verstehen der Reed–Solomon–Codes sind diese Kenntnisse allerdings nicht unbedingt erforderlich. Sie könnten also auch direkt zum Kapitel Erweiterungskörper springen.
Algebraische Gruppe und Beispiele
Für die allgemeinen Definitionen von Gruppe (und später Ring) gehen wir von einer Menge mit unendlich vielen Elementen aus:
\[M = \{\hspace{0.1cm}z_1,\hspace{0.1cm} z_2,\hspace{0.1cm} z_3 ,\hspace{0.1cm} ... \hspace{0.1cm}\}\hspace{0.05cm}. \]
- Für alle zi, zj ∈ G gilt (zi + zj) ∈ G ⇒ Closure–Kriterium für „+”.
- Es gibt stets ein hinsichtlich der Addition neutrales Element NA ∈ G, so dass für alle zi ∈ G gilt: zi + NA = zi. Bei einer Zahlengruppe ist NA = 0.
- Für alle zi ∈ G gibt es zudem ein hinsichtlich der Addition inverses Element InvA(zi) ∈ G mit der Eigenschaft zi + InvA(zi) = NA. Bei einer Zahlengruppe ist InvA(zi) = –zi.
- Für alle zi, zj, zk ∈ G gilt: zi + (zj + zk) = (zi + zj) + zk ⇒ Assoziativgesetz für „+”.
- für alle a ∈ G und b ∈ G auch die Summe a + b wieder zu G gehört,
- das Assozitativgesetz gilt,
- mit der 0 das neutrale Element der Addition in G enthalten ist, und
- es für jedes a die additive Inverse b = – a existiert.
Da zudem das Kommutativgesetz erfüllt ist, handelt es sich um eine abelsche Gruppe.
Die Menge der natürlichen Zahlen, {0, 1, 2, ...} ist hinsichtlich Addition keine algebraische Gruppe, da es für kein einziges Element zi die additive Inverse (–zi) gibt.
Algebraischer Ring und Beispiele
Entsprechend der Übersichtsgrafik kommt man von der Gruppe (G, +) durch Definition einer zweiten Rechenoperation – der Multiplikation („·”) – zum Ring (R, +, ·). Man benötigt hierfür also neben einer Additionstabelle auch eine Multiplikationstabelle.
- Hinsichtlich der Addition ist Ring (R, +, ·) eine abelsche Gruppe (G, +).
- Zusätzlich gilt für alle zi, zj ∈ R auch ( zi · zj) ∈ R ⇒ Closure–Kriterium für „·”.
- Es gibt ein hinsichtlich Multiplikation neutrales Element NM ∈ R, so dass für alle zi ∈ R gilt: zi · NM = zi. Bei einem Zahlenring gilt NM = 1.
- Für alle zi, zj, zk ∈ R gilt zi · (zj · zk) = (zi · zj) · zk ⇒ Assoziativgesetz für „·”.
- Für alle zi, zj, zk ∈ R gilt zi · (zj + zk) = zi · zj + zi · zk ⇒ Distributivgesetz für „·”.
Ein Ring (R, +, ·) ist nicht notwendigerweise kommutativ. Gilt tatsächlich auch für alle Elemente zi, zj ∈ R das Kommutativgesetz zi · zj = zj · zi hinsichtlich der Multiplikation, so spricht man in der Fachliteratur von einem kommutativen Ring. Existiert für jedes Element zi ∈ R mit Ausnahme von NA (neutrales Element der Addition, Nullelement) ein hinsichtlich der Multiplikation inverses Element InvM(zi), so dass zi · InvM(zi) = 1 gilt, so liegt ein Divisionsring (englisch: Division Ring) vor.
Weiter sollen die folgenden Voraussetzungen gelten:
- Der Ring ist nullteilerfrei (englisch: free of zero devisors), wenn aus zi · zj = 0 zwingend zi = 0 oder zj = 0 folgt. In der abstrakten Algebra ist ein Nullteiler eines Ringes ein vom Nullelement verschiedenes Element zi, falls es ein Element zj ≠ 0 gibt, so dass das Produkt zi · zj = 0 ist.
- Ein kommutativer nullteilerfreier Ring wird als Integritätsring oder Integritätsbereich (englisch: Integral Domain) bezeichnet.
Vergleicht man die Definitionen von Gruppe, Ring (oben auf dieser Seite), Körper und Galoisfeld, so erkennt man, dass ein Galoisfeld GF(q)
- ein endlicher Körper (englisch: Field) mit q Elementen ist,
- gleichzeitig als Commutative Division Ring aufgefasst werden kann, und
- einen Integritätsbereich (englisch: Integral Domain) beschreibt.
Aufgaben
Zusatzaufgaben:2.1 Welche Tabellen beschreiben Gruppen?
A2.2 Eigenschaften von Galoisfeldern
Zusatzaufgaben:2.2 Galoisfeld GF(5)
Quellenverzeichnis
- ↑ Friedrichs, B.: Kanalcodierung – Grundlagen und Anwendungen in modernen Kommunikations- systemen. Berlin – Heidelberg: Springer, 1996.
- ↑ Kötter, R.; Mayer, T.; Tüchler, M.; Schreckenbach, F.; Brauchle, J.: Channel Coding. Vorlesungsmanuskript, Lehrstuhl für Nachrichtentechnik, Technische Universität München, 2008.