KLEINE EINFÜHRUNG IN DIE KODIERUNGSTHEORIE

VORLESUNG VON B. PAREIGIS IM SS 1998

Inhaltsverzeichnis

Einleitung 1 1. Der Satz von Shannon 1 2. Die Hamming-Metrik 4 3. Lineare Codes 6 4. Kontrollmatrizen und Hamming-Metrik 9 5. Systematische Codes 12 6. Standardtafeln und Dekodierung 13 7. Hamming-Codes 16 8. Polynomringe und endliche Körper 18 9. Zyklische Codes 21 10. Beispiel eines BCH-Codes 22

Einleitung

Im Sommersemester 1998 habe ich in der Reihe der Fortbildungsveranstaltungen des Mathematischen Instituts der Ludwig-Maxililians-Universität München eine 1-stündige Vorlesung über Kodierungstheorie für Lehrer an Gymnasien in Bayern angeboten.

Es war das Ziel dieser Vorlesung, einen Begriff über die Möglichkeit und die Grenzen von vielen heute verwendeten Kodierungsmöglichkeiten zur Fehlerkorrektur zu vermitteln. Nicht die vielen Probleme der Verschlüsselung von Daten, um Zugriffe von Unbefugten zu vermeiden, sondern die Techniken zur Vermeidung oder Korrektur von Fehlern bei der Übertragung von Daten standen im Mittelpunkt der Vorlesung. Einfache Codes lassen sich schon mit Hilfsmitteln der linearen Algebra erstellen. Die Darstellung dieser Methoden und der Methoden der Fehlerkorrektur standen im Mittelpunkt der Vorlesung. Die moderne Kodierungstheorie verwendet zur Erstellung leistungsfähigerer Codes Hilfsmittel der Zahlentheorie und der algebraischen und arithmetischen Geometrie. Darauf konnte ich wegen der Kürze der Zeit nicht eingehen.

München, im Juli 1998 B. Pareigis

1. Der Satz von Shannon

Bemerkung 1.1. Informationen werden auf die verschiedenste Weise übertragen. Als Beispiele sehen wir Telefon, Funk, Fernsehen, Übertragung von Bildern aus dem Weltall (von den Sonden Mariner oder Voyager), Übertragung mit Hilfe von CD’s, militärische Informationsübertragung, das Internet, Bankenverkehr, Codekarten für Bankkunden, aber auch für Telefon oder Zugänge zu Gebäuden, Email, Datenkompression bei Sicherungskopien im Computer, Barcodes, usw. Jeder dieser Übertragungswege hat zunächst einmal die Aufgabe, Information von einem Ort oder Zeitpunkt zu einem anderen zu übertragen. Die abgesandte Information muß korrekt beim Empfänger ankommen. Sie soll während der Übertragung weitgehend frei von äußeren Einflüssen bleiben und je nach Anwendung offen lesbar für jedermann oder aber nur für den Empfänger sein.

Bei der Informationsübertragung entstehen Fehler durch

• zufällige Störungen (Rauschen, Systemfehler),

• willkürliche Verfälschung. Eine Korrektur kann

• durch Rückfrage erfolgen, falls der Empfänger den Fehler erkennt (Fehlererkennung),

• oder durch Kodierung der Information (zu offenem oder geheimem Text) (Fehlerkor-

rektur). Eine Übertragung z.B. per CD oder aus dem Weltall läßt praktisch keine Nachfrage und Wiederholung zu, sie sollte so kodiert werden, daß Fehler nachträglich allein aufgrund der empfangenen Information korrigiert werden können.

Definition 1.2. Wir nehmen an, daß die zu übertragende Information in Form einer Bitfolge, also einer Folge bestehend aus 0 oder 1, gegeben ist. Uns werden in dieser Vorlesung lediglich Fehler interessieren, die durch zufällige Störungen auf dem Informationskanal entstehen. Willkürliche Verfälschungen und systematische Fehler sollen hier nicht studiert werden.

Wir nehmen also für den Informationskanal an, daß

- ein übertragenes Bit 1 mit fester Wahrscheinlichkeit p das Bit 0 und mit der Wahrscheinlichkeit 1 − p das Bit 1 ergibt, und

- ein übertragenes Bit 0 mit derselben Wahrscheinlichkeit p das Bit 1 und mit der Wahrscheinlichkeit 1 − p das Bit 0 ergibt.

Dabei gilt 0 ≤ p ≤ 1/2. Wenn 1/2 < p ≤ 1 gilt, dann kann man durch Invertieren der Bits (0 ↦ 1, 1 ↦ 0) auf die vorherige Annahme zurückkommen. Der Fall p = 1/2 bedeutet offenbar vollständigen Informationsverlust.

Wir nehmen weiterhin an, daß auf dem Kanal jeweils genau ein Bit je Zeiteinheit (z.B. pro Millisekunde) übertragen wird.

Einen solchen Kanal nennt man einen diskreten, binären, symmetrischen Kanal ohne Speicher (BSC).

Beispiele 1.3. für Kodierungen:

1) Paritäts-Prüfsumme (Parity Check): Bei einem Computerspeicher verwendet man zur Speicherung von 1 Byte (= 8 Bits) B = (b_{1} … b_{8}) ein weiteres Kontrollbit b_{9}, also 9 Bits, wobei das 9. Kontrollbit wie folgt bestimmt wird: wenn n die Anzahl der Bits eines Bytes ist, die auf 1 gesetzt sind, so ist das

Kontrollbit = \begin{cases}1,  falls n ungerade, \\ 0,  falls n gerade. \end{cases}

Zur Überprüfung testet man, ob für die Summe aller übertragenen 9 Bits gilt

∑_{i=1}^{9} b_{i} ≡ 0 mod (2).

Wenn diese Bedingung verletzt ist, dann ist sicher bei der Übertragung ein Fehler aufgetreten. Wenn ein einziges Bit falsch übertragen wird, dann wird diese Kontrollbedingung schon verletzt. Eine solche Kodierung kann also einen Fehler (pro übertragenes Byte) erkennen. Dieses Verfahren wird bei vielen PCs verwendet. Wird ein Fehler erkannt, so kann dieser nicht automatisch korrigiert werden, der Computer bleibt also sicherheitshalber stehen.

2) Das Morsealphabet, das mit den Zeichen . (dit) und − (dah) aufgebaut wird. Genauer werden die ”Strings“ aus den Buchstaben {. (dit), − (dah), (kurze Pause), (lange Pause)} gebildet. Mit diesen Zeichen können die Buchstaben des Alphabets gebildet werden (z.B. a = .- ; b = -...).

Definition 1.4. Wörterbuch der Kodierung: Ein Code ist eine Menge C (von Zeichen, die geeignet ist, Informationen zu speichern und zu übermitteln).

Eine Chiffre oder eine Verschlüsselung (Kodierung oder Chiffrierung) ist eine Abbildung f : C_{1} → C_{2} eines Codes in einen anderen.

Eine Dechiffrierung einer Chiffre f : C_{1} → C_{2} ist eine Abbildung g : C_{2} → C_{1} mit gf = id. Die Quelle einer Chiffre f : C_{1} → C_{2} heißt Klartext, ein Element des Klartextes heißt

Nachrichtenwort.

Ein Element des Bildes einer Chiffre heißt Codewort.

Eine Kodierung heißt lineare Kodierung, wenn C_{1} und C_{2} Vektorräume sind und f : C_{1} → C_{2} eine lineare Abbildung ist.

Ein Blockcode ist ein Code, dessen Wörter aus Buchstaben eines Alphabets (typischerweise aus den Bits 0 und 1) zusammengesetzt sind und alle gleiche Länge haben, d. h. aus gleich vielen Buchstaben bestehen.

Wir betrachten hauptsächlich Kodierungen f, die injektiv sind. Falls dies nicht der Fall ist, ist die oben angegebene Bedingung für eine Dekodierung nicht erfüllbar. Es gibt jedoch Beispiele, in denen eine Kodierung mit einer nicht injektiven Abbildung sinnvoll ist, z.B. die Graphik-Kompressions-Protokolle JPEG, GIF und andere.

Beispiele 1.5. für Codes und Kodierungen:

1) Sprachen sind beliebige Mengen (und damit Codes) von ”strings“ oder Wörtern über einem beliebigen Alphabet A.

2) Das Zahlensystem, d. h. die mit den Ziffern 0, …, 9 und den Zeichen . und − dargestellten Zahlen, ist ein Code.

3) Die q- und die z-Gruppen in der Morsesprache, das sind Gruppen von drei Buchstaben des (Buchstaben-)Alphabets, die mit q bzw. z beginnen, z.B. qth = Standort, bilden einen Code.

4) Die Barcodes zur Bezeichnung von Waren im Supermarkt sind Codes.

5) Der ISBN-Code (International Standard Book Number), wie z.B. 3-519-02211-7, ist ein Code, wobei die einzelnen Gruppen folgendes bedeuten:

1. 3 = Erscheinungsland

2. 519 = Verlag

3. 02211 = fortlaufende Buchnummer

4. 7 = Prüfnummer (in {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, X}).

Die Prüfung auf eine korrekte Übertragung (Fehlererkennung) geschieht im Beispiel durch Überprüfung von 10·3+9·5+8·1+7·9+6·0+5·2+4·2+3·1+2·1+1·7 ≡ 0 mod 11. Die Restklassenberechnung modulo 11 kann durch Bildung der alternierenden Quersumme vorgenommen werden. (http://infoshare1.princeton.edu/katmandu/marc/aut020.html)

6) Beliebiger Text der Umgangssprache kann in einen linearen Code K^{n} für K = GF (q) übersetzt werden, indem man zunächst den Text jeweils in Gruppen von l Buchstaben und Abstände (und evtl. sonstige Zeichen) zusammenfaßt. Bei der Verwendung von a, …, z, A, …, Z,Zwischenraum sind also 53^{l} verschiedene solche Textgruppen möglich. Diesen weist man in einer beliebig festzulegenden Weise ebenso viele verschiedene Elemente in K^{n} zu. Damit bestimmt sich l aus 53^{l} ≤ q^{n} als l ≤ n · \frac{ln(q)}{ln(53)}.

Bemerkung 1.6. Wir werden im folgenden immer Blockcodes verwenden, d. h. die Elemente der beiden Codes einer Kodierung haben alle gleiche Länge, z.B. gleiche Anzahl von Bits. Ein Blockcode der Länge k hat also q^{k} Wörter, wenn q die Anzahl der Zeichen des verwendeten Alphabets ist, also für {0, 1} ist q = 2.

Wir verwenden zur Übertragung einen binären, symmetrischen Kanal (BSC). Wenn eine Kodierung mit Blockcodes f : C_{1} → C_{2} gegeben ist, wobei C_{1} Wörter der Länge k und C_{2} Wörter der Länge n besitzt und das verwendete Alphabet {0, 1} ist, so werden bei der Übertragung von n Bits, also in n Zeiteinheiten lediglich k Informationsbits übermittelt. Die Durchsatzrate der Kodierung ist dann k/n. Weiter ist die Bit-Fehler-Wahrscheinlichkeit die Wahrscheinlichkeit, daß ein Bit eines Klartextwortes trotz erfolgter Fehlerkorrektur falsch ankommt.

Wir formulieren jetzt den Satz von Shannon, ohne ihn allerdings zu beweisen. Er dient zum Verständnis der Möglichkeiten der Kodierungstheorie und außerdem als Motivation dafür, möglichst viele verschiedene Kodierungen zu finden und zu studieren.

Theorem 1.7. Der Satz von Shannon (Claude Shannon: A mathematical theory of communication - 1948.) Sei ein binärer symmetrischer Kanal mit einer Bit-Fehler-Wahr-scheinlichkeit 0 ≤ p < \frac{1}{2} gegeben. Dann gibt es eine Zahl C > 0, die Kanalkapazität, so daß es zu jedem ε > 0 und zu jeder Durchsatzrate 0 < R < C einen Blockcode B mit Bit-Fehler-Wahrscheinlichkeit P (B) < ε gibt.

Die Kanalkapazität ist C = 1 + p log_{2}(p) + (1 − p) log_{2}(1 − p).

Bemerkung 1.8. Der Zusammenhang zwischen Durchsatzrate R und Bit-Fehler-Wahr-scheinlichkeit P ist annähernd gegeben durch die folgende Kurve

[figure: .1; .2; .3; .4; .5; R; 1; 2; 3; 4; P]

Alle Punkte im Bereich oberhalb der Kurve sind mit Codes erreichbar, d. h. zu jedem Paar (P, R) oberhalb der Kurve gibt es Codes, deren Durchsatzrate und Bit-Fehler-Wahrschein-lichkeit diesen Wert beliebig genau annähern.

Der Satz von Shannon beruht auf einem reinen Existenzbeweis. Er gibt keine Möglichkeit zur Konstruktion geeigneter Codes an. Der Satz gilt wesentlich allgemeiner, u.a. auch für lineare Codes. Die praktisch verwendeten Blockcodes können sehr lang werden, z.B. 10^{100} mögliche Codewörter.

2. Die Hamming-Metrik Beispiel 2.1. Der (7,4)-Hamming-Code: Wir verwenden als Codewörter Linearkombinationen der Zeilen-Vektoren von

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 \end{matrix} )

in dem Vektorraum K^{7} mit K := 𝔽_{2} = {0, 1}. Die Information ist in den ersten 4 Bits enthalten. Diese können beliebig mit 0 oder 1 besetzt werden. Also haben wir 2^{4} = 16 Codewörter. Die Durchsatzrate ist 4/7 = 0.57.

Dieser Code hat eine der verblüffendsten Fehlerkorrektur-Möglichkeiten. Wir verwenden die Vektoren

a = (0001111),
b = (0110011),
c = (1010101).

Wenn in einem übertragenen Codewort ein Fehler auftritt, z.B. wenn x = (1011010) übertragen wird als y = (1010010) mit einem Fehler im 4. Bit, dann rechne man ⟨y, a⟩ = 1, ⟨y, b⟩ = 0, ⟨y, c⟩ = 0 und erhält die Binärzahl 100 oder den Wert 4. Zur Fehlerkorrektur ist nun die 4. Stelle zu korrigieren.

Dieser Code kann grundsätzlich einen Fehler pro Codewort korrigieren. Er hat eine Durchsatzrate von 0.57. Die Bit-Fehler-Wahrscheinlichkeit ergibt wie folgt.

q^{7} (keine Fehler) + 7pq^{6} (ein Fehler) = 0.4783 + 0.3720 = 0.8503

ist die Wahrscheinlichkeit für ein korrekt empfangenes Codewort, also ist die Wort-Fehler-wahrscheinlichkeit 0.1497. Das entspricht einer Bit-Fehler-Wahrscheinlichkeit von 0.0398.

Wir wollen Erkenntnisse über lineare Abbildungen und Matrizen verwenden, um Probleme der linearen Kodierung zu formulieren und zu lösen.

Wir werden in diesem Abschnitt als Grundkörper durchgehend den endlichen Körper K := GF (q) mit q Elementen verwenden. GF ist dabei eine Abkürzung für das Wort Galois-Feld. Man kann zeigen, daß es genau dann einen Körper mit q Elementen gibt, wenn q ein Primzahlpotenz ist, d. h. wenn es eine Primzahl p und eine natürliche Zahl n mit q = p^{n} gibt. Dieser Körper ist zudem durch die Angabe von q bis auf Isomorphie eindeutig bestimmt.

Wir kennen bisher lediglich die endlichen Körper GF (p) = ℤ/pℤ für Primzahlen p. Zunächst werden unsere Anwendungen nur den Körper ℤ/2ℤ mit zwei Elementen (binäres System der Computer!) benutzen. Daher werden wir die Konstruktion der übrigen Körper GF (q) erst später diskutieren. Wir verweisen den interessierten Leser jedoch jetzt schon auf Lehrbücher der Algebra.

Wir werden im folgenden nur lineare Codes der Form C = K^{n} mit K = GF (q) verwenden mit der linearen Chiffrierung f : K^{k} → K^{n}. Wegen der notwendigen Dechiffrierung wird f immer als Monomorphismus vorausgesetzt.

Eine Kodierung f : C_{1} → C_{2} bildet den Code C_{1} auf eine Teilmenge von C_{2} ab. Bei einer Störung der Übertragung von Codewörtern aus C_{2} kann es vorkommen, daß ein empfangenes Wort aus C_{2} kein Codewort mehr ist, also nicht im Bild von f liegt. Es erhebt sich die Frage beim Empfänger, das Codewort aus dem empfangenen Wort mit Hilfe der Redundanz zurückzugewinnen.

Man kann beweisen, daß bei Verwendung eines binären symmetrischen Kanals das wahrscheinlichste Codewort (maximum likelyhood) gerade durch den kürzesten Abstand der Hamming-Metrik gegeben ist. Daher sollten die Codewörter möglichst gleichmäßige Abstände im Sinne der Hamming-Metrik besitzen und es sollte der Raum C_{2} mit dem Bild von f im Sinne einer möglichst dichten Kugelpackung gefüllt werden.

Definition 2.2. Sei K^{n} ein linearer Code. Die Hamming-Metrik auf K^{n} ist die Abbildung d : K^{n} × K^{n} → ℕ_{0} mit d(x, y) := Anzahl der i ∈ {1, …, n} mit ξ_{i} ≠ η_{i}. Die Auffassung ist hierbei, daß d(x, y) die Anzahl der Koeffizienten von x angibt, die in y anders (falsch) angegeben werden. Der Wert d(x, y) heißt Hamming-Abstand von x und y. Die Hamming-Gewichtsfunktion ist die Abbildung ∥.∥ : K^{n} → ℕ_{0} mit ∥x∥ := d(x, 0). Das ist die Anzahl der von Null verschiedenen Komponenten von x.

Definition 2.3. Ein Paar (M, d) heißt metrischer Raum mit der Metrik d, wenn M eine Menge und d : M × M → ℝ eine Abbildung sind mit

1) ∀x, y ∈ M[d(x, y) = 0 ⟺ x = y],

2) ∀x, y ∈ M[d(x, y) = d(y, x)],

3) ∀x, y, z ∈ M[d(x, z) ≤ d(x, y) + d(y, z)] (Dreiecksungleichung).

Lemma 2.4. Die Hamming-Metrik ist eine Metrik auf K^{n}.

Beweis. folgt unmittelbar aus der Definition.

Wir vermerken noch eine leicht einzusehende zusätzliche Translationsinvarianz d(x, y) = d(x+z, y +z), die zeigt, daß d durch das Hamming-Gewicht ∥.∥ schon vollständig bestimmt ist, denn d(x, y) = ∥x − y∥.

Ein weiteres bekanntes Beispiel für eine Metrik ist der reelle Vektorraum ℝ^{n} mit der sogenannten euklidischen Metrik

d(x, y) = \sqrt{∑_{i=1}^{n}(ξ_{i} − η_{i})^{2}}.

Lemma 2.5. Für das Hamming-Gewicht ∥.∥ : K^{n} → ℕ_{0} gelten 1) ∥x∥ = 0 ⟺ x = 0,

2) ∀λ ≠ 0 [∥λx∥ = ∥x∥],

3) ∥x + y∥ ≤ ∥x∥ + ∥y∥.

Beweis. leicht nachzurechnen, da ∥x∥ die Anzahl der von Null verschiedenen Komponenten von x ist.

3. Lineare Codes

Bemerkung 3.1. Im folgenden Abschnitt gehen wir von der allgemeinen Vorstellung aus:

Klartext

⟶^{Kodierung}

Sender

Übertragung/Störung

⟶ Empfänger

⟶^{Decodierung}

Klartext

Es wird also ein Klartext codiert, über eine Informationsleitung zum Empfänger übermittelt, (wobei der Text aufgrund der Kodierung eventuell auch abhörsicher ist,) wird auf der Übertragungsstrecke mit Störungen verschiedener Art verändert und beim Empfänger wieder decodiert. Wir wollen Methoden finden, die Fehler bei der Übertragung zu erkennen und möglichst auch zu korrigieren. Wenn also x ein codiertes ausgesandtes Wort ist und y das empfangene Wort ist, dann soll festgestellt werden, ob es tatsächlich durch die Kodierung entstanden ist oder verändert wurde und ob man daraus das Wort x rekonstruieren kann.

Definition 3.2. Wenn bei einer Kodierung f : K^{k} → K^{n} Fehler an höchstens r Stellen des übertragenen Wortes immer erkannt werden können, so sagen wir, daß die Kodierung rfehlerentdeckend ist. Wenn Fehler an höchstens s Stellen durch die restliche Information im übertragenen Wort korrigiert werden können, so heißt die Kodierung s-fehlerkorrigierend.

Bemerkung 3.3. In (1.4) haben wir lineare Kodierungen als lineare Abbildungen f : C_{1} → C_{2} zwischen zwei Vektorräumen definiert. Für unsere Anwendungen soll f immer injektiv sein. Ohne Einschränkung können wir C_{2} = K^{n} wählen.

Außer einer bijektiven Umschreibung des Codes C_{1} verlieren wir nichts, wenn wir C_{1} mit dem Bild von f, also einem Untervektorraum V ⊆ K^{n} identifizieren.

Wenn unser Grundkörper K = GF (q) ist mit q, einer Primzahlpotenz, Elementen, so besitzt die Menge der n-Tupel K^{n} genau q^{n} Elemente.

Ein k-dimensionaler Unterraum V ⊆ K^{n} wird ein (n, k)-Code genannt.

Wir betreiben also Theorie von Vektorräumen und Untervektoräumen über einem endlichen Körper GF (q), wenn wir lineare Codes studieren.

Beispiel 3.4. Sei K = GF (2) = 𝔽_{2} = {0, 1} der Körper mit zwei Elementen. In K^{5} betrachten wir den Unterraum

\begin{aligned}V = & \{(0 0 0 0 0), (1 0 0 1 1), (0 1 0 1 0), (1 1 0 0 1), \\ & (0 0 1 0 1), (1 0 1 1 0), (0 1 1 1 1), (1 1 1 0 0)\} \end{aligned}

Dieses ist ein 3-dimensionaler Unterraum und definiert einen (5, 3)-Code mit 2^{3} = 8 Codewörtern. Wir werden dieses Beispiel als Standardbeispiel weiter verwenden.

Bemerkung 3.5. Sei V ⊆ K^{n} eine (n, k)-Code und seien b_{1}, …, b_{k} eine Basis von V. Dann ist V vollständig bestimmt durch die Angabe dieser Basis oder durch die Matrix

B = ( b_{1} ; ⋮ ; b_{k} ) . Diese Matrix hat wegen der linearen Unabhängigkeit der Zeilen b_{1}, …, b_{k}

den Zeilenrang k. Die Vektoren aus V sind genau die Linearkombinationen der Zeilen von B. Die Matrix B wird daher auch eine erzeugende Matrix für V genannt. Sie ist nicht eindeutig, weil es viele verschiedene Basen für V gibt.

Jede (k×n)-Matrix vom Zeilenrang k mit Vektoren aus V definiert eine erzeugende Matrix für V.

Statt die Liste der Codewörter eines Codes anzugeben, ist es ökonomischer, eine erzeugende Matrix anzugeben. Für einen binären (50, 30)-Code hat eine solche Matrix 1500 Einträge, während die Liste der Codewörter mehr als 10^{9} Wörter umfassen würde.

Ein erzeugende Matrix B definiert eine injektive lineare Abbildung B : K^{k} ∋ v ↦ xB ∈ K^{n}. Diese können wir als zugrunde liegende lineare Kodierung begreifen.

Unser Beispielcode hat beispielsweise folgende zwei erzeugende Matrizen:

( \begin{matrix}1 & 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 \end{matrix} ) , ( \begin{matrix}1 & 0 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 & 0 \end{matrix} ) .

Bemerkung 3.6. Wir erinnern daran, daß der Zeilenrang einer Matrix B die Maximalzahl linear unabhängiger Zeilen in B ist. Analog ist der Spaltenrang von B die Maximalzahl linear unabhängiger Spalten von B. Man zeigt in der lineare Algebra, daß Zeilenrang(B) = Spaltenrang(B). Weiter ist der (Zeilen- oder Spalten-)Rang einer Matrix gleich der Dimension des Bildraumes von B : K^{r} ∋ v ↦ xB ∈ K^{s}. Das Bild wird nämlich von den Zeilenvektoren b_{i} = e_{i}B aufgespannt, wobei die e_{i} die kanonische Basis bilden.

Die Transponierte B^{T} einer Matrix B = (b_{ij}|i = 1, …, n; j = 1, …, k) ist die Matrix B^{T} = (c_{ij}|i = 1, …, k; j = 1, …, n) mit c_{ij} = b_{ji}, also die an der Diagonalen gespiegelte Matrix.

Der Rang von B^{T} stimmt offenbar mit dem Rang von B überein.

Lemma 3.7. Sei V ⊆ K^{n} ein k-dimensionaler Unterraum. Dann ist

V^{⊥} = {w ∈ K^{n}|⟨v, w⟩ = vw^{T} = ∑_{i=1}^{n} ν_{i}ω_{i} = 0}

ein Untervektorraum der Dimension n − k.

Beweis. Sei B eine erzeugende Matrix für V. Offenbar gilt vw^{T} = wv^{T} = 0 für alle v ∈ V genau dann, wenn wB^{T} = 0. Da B^{T} : K^{n} → K^{k} mit w ↦ wB^{T} eine lineare Abbildung ist, ist V^{⊥} = Ker(B^{T}), insbesondere also ein Unterraum.

Der Zeilenrang von B ist gleich dem Spaltenrang von B^{T} gleich dem Zeilenrang von B^{T} gleich der Dimension des Bildes von B^{T}. Daher ist die Dimension des Kerns von B^{T} gleich n − k.

Definition 3.8. Sei V ⊆ K^{n} ein Code. Dann heißt der Code V^{⊥} ⊆ K^{n} dualer Code zu V.

Bemerkung 3.9. Seien V ein Code und V^{⊥} der duale Code. Ist v ∈ V, so gilt ⟨v, w⟩ = 0 für alle w ∈ V^{⊥}. Also ist v ∈ V^{⊥⊥} und daher auch V ⊆ V^{⊥⊥}. Da die Dimension dim(V^{⊥⊥}) = n − (n − k) = k = dim(V) ist, gilt V = V^{⊥⊥}.

Beispiel 3.10. Der duale Code V^{⊥} zu unserem Beispielcode ist 2-dimensional und durch

V^{⊥} = {(0 0 0 0 0), (1 1 0 1 0), (1 0 1 0 1), (0 1 1 1 1)}

gegeben. Beachte, daß der Vektor (0 1 1 1 1) sowohl in V als auch in V^{⊥⊥} liegt, im Gegensatz zum Verhalten einer analogen Konstruktion für das euklidische Skalarprodukt.

Eine erzeugende Matrix ist

B′ = ( \begin{matrix}1 & 1 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 & 1 \end{matrix} ) .

Definition 3.11. Sei V ⊆ K^{n} ein Code. Die Transponierte H = B′^{T} einer erzeugenden Matrix B′ des dualen Codes V^{⊥} heißt Kontrollmatrix für V.

Satz 3.12. Jeder (lineare) Code V ⊆ K^{n} stimmt überein mit dem Kern einer zugehörigen Kontrollmatrix H.

Beweis. Ein Vektor v liegt genau dann in V = V^{⊥⊥}, wenn vw^{T} = 0 für alle w ∈ V^{⊥} genau dann, wenn vH = 0 gilt, genau dann wenn er im Kern der Kontrollmatrix H liegt.

Beispiel 3.13. Eine Kontrollmatrix für unseren Beispielcode ist

( \begin{matrix}1 & 1 \\ 1 & 0 \\ 0 & 1 \\ 1 & 0 \\ 0 & 1 \end{matrix} ) .

Die durch die Kontrollmatrix definierten Gleichungen, z.B.

\begin{matrix}ν_{1}1 + ν_{2}1 + ν_{3}0 + ν_{4}1 + ν_{5}0 = 0 \\ ν_{1}1 + ν_{2}0 + ν_{3}1 + ν_{4}0 + ν_{5}1 = 0 \end{matrix}

kann man als verallgemeinerte Paritäts-Prüfsummen auffassen.

Auch der Vektor (0 1 1 1 1)^{T} könnte in einer Kontrollmatrix stehen. Die Gleichung

ν_{1}0 + ν_{2}1 + ν_{3}1 + ν_{4}1 + ν_{5}1 = 0

bedeutet dann, daß jeder Vektor in V eine gerade Anzahl von Einsen in den Bits 2 bis 5 haben muß.

Bemerkung 3.14. Wir können jetzt einen linearen Code V ∈ K^{n} sowohl durch eine erzeugende Matrix B als auch durch eine Kontrollmatrix H vollständig beschreiben. Die wesentlichen Probleme sind jetzt die Dekodierung und die Fehlerkorrektur bzw. Fehlererkennung.

Bei der Dekodierung können wir uns auf den Standpunkt stellen, daß mit der Angabe eines Vektors v im Code V schon alles bekannt ist. Oder aber wir können den Vektor x ∈ K^{k} mit v = xB^{T} suchen.

4. Kontrollmatrizen und Hamming-Metrik

Definition 4.1. Sei V ⊆ K^{n} ein Code mit einer erzeugenden Matrix B. Das Hamming-Gewicht ∥V ∥ = ∥B∥ von V bzw. von B ist das Minimum der Hamming-Gewichte ∥v∥ aller v ∈ V mit v ≠ 0.

Das Hamming-Gewicht eines Codes V ist damit der minimale Hamming-Abstand zweier verschiedener Vektoren im Code: d(v_{1}, v_{2}) = ∥v_{1} − v_{2}∥.

Satz 4.2. Sei V ⊆ K^{n} ein linearer Code mit Kontrollmatrix H. Jede Codewort v ∈ V von Hamming-Gewicht r = ∥v∥ definiert eine lineare Abhängigkeitsrelation zwischen r Zeilenvektoren von H. Jede lineare Abhängigkeitsrelation zwischen r Zeilenvektoren von H definiert ein Codewort v ∈ V vom Hamming-Gewicht r = ∥v∥.

Beweis. Sei H = ( h_{1} ; ⋮ ; h_{n} ) die Kontrollmatrix mit den Zeilenvektoren h_{i}. Sei v = (ν_{1}, …, ν_{n}).

Es ist v ∈ V genau dann, wenn vH = 0 genau dann, wenn ∑ ν_{i}h_{i} = 0. Die Summe hat genau so viele Summanden ≠ 0, wie v von Null verschiedene Koeffizienten hat, wie das Hamming-Gewicht von v ist.

Folgerung 4.3. Sei V ⊆ K^{n} ein (n, k)-linearer Code vom Hamming-Gewicht ∥V ∥ mit Kontrollmatrix H. Dann sind je ∥V ∥−1 Zeilenvektoren von H linear unabhängig, und es gibt ∥V ∥ linear abhängige Zeilenvektoren, d. h. ∥V ∥ ist die Minimalzahl von linear abhängigen Zeilenvektoren von H.

Beweis. Es gibt keinen Vektor v ∈ V, v ≠ 0 vom Hamming-Gewicht ∥V ∥ − 1, daher sind je ∥V ∥ − 1 Zeilenvektoren von H linear unabhängig und umgekehrt. Es gibt einen Vektor v ∈ V, v ≠ 0 vom Hamming-Gewicht ∥V ∥, daher gibt es ∥V ∥ Zeilenvektoren von H, die linear abhängig sind und umgekehrt.

Folgerung 4.4. Für jeden (n, k)-linearen Code V ⊆ K^{n} gilt

∥V ∥ ≤ n − k + 1.

Beweis. Der Rang jeder Kontrollmatrix zu V ist n−k. Damit sind je n−k+1 Zeilenvektoren der Kontrollmatrix linear abhängig. Nach der vorhergehenden Folgerung ist also ∥V ∥ ≤ n − k + 1.

Satz 4.5. (Fehlererkennung) Sei V ⊆ K^{n} ein (n, k)-linearer Code und sei x ∈ K^{n}. Wenn es ein v ∈ V mit v ≠ x gibt, so daß d(v, x) < ∥V ∥, dann ist x ∉ V, d. h. das Wort x ist kein Codewort, also falsch.

Beweis. folgt unmittelbar aus der Tatsache, daß ∥V ∥ der minimale Hamming-Abstand zwischen zwei verschiedenen Codewörtern in V ist.

Satz 4.6. (Fehlerkorrektur) Sei V ⊆ K^{n} ein (n, k)-linearer Code und sei x ∈ K^{n}. Wenn es ein v ∈ V gibt mit d(v, x) < \frac{1}{2}∥V ∥, dann gilt für alle v′ ∈ V, v′ ≠ v : d(v, x) < d(v′, x), d. h. v ist das einzige Element von V mit dem gegebenen Abstand d(v, x) und somit eindeutig durch x bestimmt.

Beweis. Für v′ ∈ V und v′ ≠ v gilt 2d(v, x) < ∥V ∥ ≤ d(v, v′) ≤ d(v, x) + d(x, v′), also d(v, x) < d(v′, x).

Bemerkung 4.7. Wenn bei der Übertragung von v weniger als \frac{1}{2}∥V ∥ Fehler aufgetreten sind und x ∈ K^{n} empfangen wurde, dann ist also v ∈ V mit d(v, x) < \frac{1}{2}∥V ∥ das übertragene Element. Somit ist eine linearer Code immer (∥V ∥−1)-fehlererkennend und \frac{1}{2}(∥V ∥−1)-feh-lerkorrigierend. Es kommt also darauf an, Codes V mit möglichst großem Hamming-Gewicht ∥V ∥ zu finden.

Man wird mit den Voraussetzungen des vorhergehenden Satzes x ∈ K^{n} als v ∈ V dekodieren und hat damit die geringstmögliche Anzahl von Änderungen vorgenommen. Damit verwendet die Korrektur den wahrscheinlichsten Fehlerfall in Sinne von ”maximum likelihood“.

Beispiele 4.8. 1) Paritäts-Prüfungs-Codes: Sei n ≥ 2 und k = n − 1 und f : K^{k} → K^{n} gegeben durch f(α_{1}, …, α_{n−1}) = (α_{1}, …, α_{n}) mit α_{n} = −(α_{1} + … + α_{n−1}). Offenbar ist f eine injektive lineare Abbildung. Weiter ist v ∈ V = Bi(f) genau dann, wenn ∑_{i=1}^{n} α_{i} = 0. Wenn q = 2 ist, dann wird jede ungerade Anzahl von Fehlern dadurch erkannt, daß ∑_{i=1}^{n} α_{i} = 1 gilt. Ein gerade Anzahl von Fehlern wird nicht erkannt. Für v ∈ V und v ≠ 0 müssen mindestens zwei Koeffizienten von Null verschieden sein, also ist ∥V ∥ = 2. Damit kann zwar ein Fehler (und sogar eine ungerade Anzahl von Fehlern) erkannt werden, jedoch ergibt sich keine Möglichkeit zur Korrektur von Fehlern. Diese Kodierungen werden z.B. in PCs verwendet, wenn 8-Bit Worte in 9-Bit Speichern gespeichert werden und das 9. Bit durch die Abbildung f bestimmt wird.

2) Wiederholungscode: Eine einfache Möglichkeit einer sichereren Übertragung auf einer gestörten Übertragungsstrecke ist die dreifache Übertragung jedes einzelnen Wortes. Dabei ist n = 3m und f : K^{k} → K^{n} durch f(x) = (x, x, x) gegeben. Das ist wieder eine linearer Code V = Bi(f). Man sieht sofort, daß ∥V ∥ = 3 ist, also ist dieser Code 2-fehlerentdeckend und 1-fehlerkorrigierend.

Folgerung 4.9. Sei V ⊆ K^{n} ein Code mit Kontrollmatrix H = ( h_{1} ; ⋮ ; h_{n} ).

(a) Sei v ∈ V, und seien bei der Übertragung genau t Fehler aufgetreten. Wenn x ∈ K^{n} der empfangene Wert ist, dann ist die minimale Anzahl der Koeffizienten ξ_{i} ≠ 0, so daß xH = ∑ ξ_{i}h_{i} gilt, höchstens t.

(b) Sei v ∈ V, seien bei der Übertragung genau t Fehler aufgetreten, und sei t < \frac{1}{2}∥V ∥. Wenn x ∈ K^{n} der empfangene Wert ist, dann gibt es t eindeutig bestimmte Koeffizienten ξ_{i} mit xH = ∑ ξ_{i}h_{i}. Der Übertragungsfehler ist dann ∑ ξ_{i}e_{i}, und es gilt v = x − ∑ ξ_{i}e_{i}.

Beweis. Mit (a) kann die Anzahl der aufgetretenen Fehler nach unten abgeschätzt werden. Man braucht v ∈ V nicht zu kennen. Sei ∑ μ_{i}e_{i} der Übertragungsfehler, d. h. x = v+∑ μ_{i}e_{i}. Dann ist xH = vH + ∑ μ_{i}e_{i}H = ∑ μ_{i}h_{i}. Seien genau t Fehler aufgetreten, so ist die Anzahl der Summanden t. Es ist jedoch möglich, durch andere Wahl der Koeffizienten (weniger Koeffizienten) ξ_{i} eine andere Linearkombination ∑ ξ_{i}h_{i} zu erhalten, die mit xH übereinstimmt.

Wenn in (b) weniger als \frac{1}{2}∥V ∥ Fehler aufgetreten sind, dann ist die minimale Anzahl der Summanden in der Darstellung xH = ∑ μ_{i}h_{i} kleiner als \frac{1}{2}∥V ∥. Wegen (4.3) sind die verwendeten h_{i} linear unabhängig. Wenn xH = ∑ λ_{j}h_{j} eine weitere Darstellung ist und die Anzahl der Summanden minimal, insbesondere also kleiner als \frac{1}{2}∥V ∥, ist, dann ist ∑ μ_{i}h_{i} − ∑ λ_{j}h_{j} = 0 mit weniger als ∥V ∥ Summanden. Die verwendeten h_{i} sind nach (4.3) linear unabhängig, also stimmen die λ_{i} mit den μ_{i} überein, d. h. die Darstellung xH = ∑ μ_{i}h_{i} mit weniger als \frac{1}{2}∥V ∥ Summanden ist eindeutig, und der Fehler ist x−v = ∑ λ_{i}e_{i}. Man beachte hier jedoch, daß der Fehler nur unter der Annahme t < \frac{1}{2}∥V ∥ korrigiert werden konnte.

Man kann die Minimalzahl von linear abhängigen Zeilenvektoren in H und damit das Hamming-Gewicht von V bestimmen, daher ist es sinnvoll eine beliebige Kontrollmatrix H zu konstruieren und dann aus ihr den Code V ⊆ K^{n} abzuleiten. Man kann dann H unmittelbar mit einem möglichst großen Minimum an linear abhängigen Vektoren konstruieren. Dann brauchen wir nur noch V = Ker(H) zu berechnen.

Beispiel 4.10. 1) Sei K = ℤ/11ℤ. Sei die Kontrollmatrix

H := ( \begin{matrix}2 & 1 & 0 \\ 1 & 2 & 0 \\ 2 & 0 & 1 \\ 1 & 0 & 2 \\ 0 & 2 & 1 \\ 0 & 1 & 2 \\ 1 & 2 & 1 \end{matrix} ) .

Dann kann man nachrechnen, daß die Minimalzahl von linear abhängigen Zeilenvektoren 4 ist. Eine erzeugende Matrix für den Code V ⊆ K^{7} gewinnt man aus der Basis des Kerns von H. Sie ist

B := ( \begin{matrix}9 & 1 & 2 & 10 & 0 & 0 & 0 \\ 9 & 2 & 1 & 0 & 10 & 0 & 0 \\ 8 & 2 & 2 & 0 & 0 & 10 & 0 \\ 7 & 5 & 3 & 0 & 0 & 0 & 8 \end{matrix} ) .

Diese Kodierung hat das Hamming-Gewicht 4, kann also 3 Fehler erkennen und einen Fehler korrigieren.

2) Sei K = ℤ/2ℤ. Sei die Kontrollmatrix

H := ( \begin{matrix}1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 1 \\ 1 & 1 & 1 \end{matrix} ) .

Dann kann man nachrechnen, daß die Minimalzahl von linear abhängigen Zeilenvektoren 3 ist. Eine erzeugende Matrix für den Code V ⊆ K^{7} ist

A := ( \begin{matrix}1 & 1 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 1 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 & 1 \end{matrix} ) .

Diese Kodierung hat das Hamming-Gewicht 3, kann also 2 Fehler erkennen und einen Fehler korrigieren.

5. Systematische Codes

Wir gehen zunächst davon aus, daß bei einer Kodierung B : K^{k} → K^{n} die Informationsbits v = (ν_{1}, …, ν_{k}) durch Anwendung von B auf das ganze Codewort xB ”verschmiert“ werden und daß in diesem Codewort die Fehlerkontrollbits ebenfalls enthalten sind. Daher sind Codes von spezieller Gestalt etwas einfacher zu behandeln. Wir werden jedoch sehen, daß jeder Code in einen Code der speziellen Gestalt umgewandelt werden kann.

Definition 5.1. Ein systematischer Code ist ein Code, der eine erzeugende Matrix, genannt systematische erzeugende Matrix, der Form

(I_{k}P) = ( \begin{matrix}1 & 0 & … & 0 & p_{11} & … & p_{1,n−k} \\ 0 & 1 & … & 0 & p_{21} & … & p_{2,n−k} \\ ⋮ & ⋮ & & ⋮ & ⋮ & & ⋮ \\ 0 & 0 & … & 1 & p_{k1} & … & p_{k,n−k} \end{matrix} )

hat.

Bemerkung 5.2. Eine systematische erzeugende Matrix

B = (b_{1}, …, b_{n}) = (I_{k}P) = (e_{1}, …, e_{k}, p_{1}, …, p_{n−k})

eines systematischen Codes induziert eine lineare Abbildung B : K^{k} → K^{n} mit xB = (ξ_{1}, …, ξ_{n})B = ∑ ξ_{i}b_{i} = (ξ_{1}, …, ξ_{k}, xp_{1}^{T} , …, xp_{n−k}^{T}). Das Klartextwort x ∈ K^{k} ist also der erste Teil des Codewortes xB. Es wird oft die Menge der Informationssymbole genannt. Der zweite Teil ist der Fehlerkorrektur vorbehalten und stellt verallgemeinerte Paritäts-Prüfsum-men xp_{i} oder Redundanzsymbole dar. Die Elemente von V haben die folgende Form: an den ersten k Stellen stehen beliebige Koeffizienten λ_{1}, …, λ_{k}. Die weiteren Stellen λ_{k+1}, …, λ_{n} berechnen sich daraus als

λ_{k+i} := (λ_{1}, …, λ_{k})p_{i} = ∑_{j=1}^{k} λ_{j}p_{ji}.

Satz 5.3. Sei B = (I_{k}P) eine erzeugenden Matrix eines systematischen Codes V. Dann ist

H = ( \begin{matrix}−P \\ I_{n−k} \end{matrix} ) eine Kontrollmatrix für V.

Beweis. Es ist BH = (I_{k}P) ( \begin{matrix}−P \\ I_{n−k} \end{matrix} ) = 0. Da Rang(B) = k und Rang(H) = n − k, ist

V, der von B erzeugte Unterraum der Dimension k, gleich dem Kern(H), der ja auch die Dimension k hat.

Beispiel 5.4. Die Matrix B = ( \begin{matrix}1 & 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 1 & 1 & 1 \end{matrix} ) ist eine systematische erzeugende Ma-

trix. Die zugehörige Kontrollmatrix ist H = ( \begin{matrix}0 & 1 \\ 1 & 0 \\ 1 & 1 \\ 1 & 0 \\ 0 & 1 \end{matrix} ) . Die Redundanzsymbole ergeben

sich als

\begin{matrix}λ_{4} = λ_{2} + λ_{3} \\ λ_{5} = λ_{1} + λ_{3} \end{matrix}

Der Code hat nach (4.3) das Hamming-Gewicht 2, ist also 1-fehlererkennend, kann aber keine Fehler korrigieren.

Bemerkung 5.5. Elementare Zeilenumformungen sind:

1. Die Addition eines Vielfachen einer Zeile zu einer anderen Zeile und

2. die Multiplikation einer Zeile mit einem Faktor α ≠ 0.

Wegen ( \begin{matrix}a \\ b \end{matrix} ) ↦ ( \begin{matrix}a + b \\ b \end{matrix} ) ↦ ( \begin{matrix}a + b \\ −a \end{matrix} ) ↦ ( \begin{matrix}b \\ −a \end{matrix} ) ↦ ( \begin{matrix}b \\ a \end{matrix} ) läßt sich auch das Vertau-

schen zweier Zeilen mit elementaren Zeilenoperationen erreichen. Jede elementare Zeilenumformung macht aus einer Basis von V eine neue Basis von V, weil die Zeilenumformungen nicht aus V herausführen und umkehrbar sind, also die Basis erhalten.

Das Gaußsche Eliminationsverfahren zeigt, daß man eine (k × n)-Matrix vom Rang k durch elementare Zeilenumformungen in eine Zeilenstufenform

( \begin{matrix}α & … & α & 1 & α & … & α & 0 & α & … & … & α & 0 & α & … & α \\ α & … & α & 0 & α & … & α & 1 & α & … & … & α & 0 & α & … & α \\ ⋮ & & ⋮ & ⋮ & ⋮ & & ⋮ & ⋮ & ⋮ & & & ⋮ & ⋮ & ⋮ & & ⋮ \\ α & … & α & 0 & α & … & α & 0 & α & … & … & α & 1 & α & … & α \end{matrix} )

umwandeln kann, wobei die α’s beliebige Koeffizienten sind. Man kann sogar von gewissen α’s annehmen, daß sie Null sind.

Durch Permutation der Spalten kann man daraus eine systematische erzeugende Matrix machen. Die Permutation von Spalten bedeutet eine Umschreibung der Zeilenvektoren in K^{k} durch Permutation ihrer Koeffizienten. Der dann erzielte Code heißt kombinatorisch äquivalent zum Ausgangscode. Wir haben damit

Satz 5.6. Jeder Code ist kombinatorisch äquivalent zu einem systematischen Code.

6. Standardtafeln und Dekodierung

Es bleibt weiterhin die Frage, wie man ein fehlerhaft übertragenes Codewort jedenfalls in Bezug auf die Informationsbits korrigieren kann, also die Frage der allgemeinen Dekodierung D : K^{n} → K^{k}. Wegen der Verwendung der Hamming-Metrik ist hier nicht mit einer linearen Abbildung zu rechnen.

Definition 6.1. Sei V ⊆ K^{n} ein Code. Eine Neben- oder Restklassen eines Elements x ∈ K^{n} bezüglich V ist die Menge

\overline{x} = x + V = \{x + v|v ∈ V \}.

Lemma 6.2. Für die Nebenklassen gilt

\begin{matrix}\overline{x} ∩ \overline{y} = ∅ , wenn \overline{x} ≠ \overline{y}; \\ ⋃_{xinK^{n}} \overline{x} = K^{n}. \end{matrix}

Beweis. Die zweite Gleichung ist klar, denn x = x + 0 ∈ x + V = \overline{x} ⊆ ⋃_{yinK^{n}} \overline{y}. Wenn zum Beweis der ersten Gleichung gilt, z ∈ \overline{x} ∩ \overline{y}, dann gibt es v_{1}, v_{2} ∈ V mit z = x + v_{1} = y + v_{2}. Also ist y = x + v_{1} − v_{2} ∈ x + V = \overline{x} und daher y + v = x + v_{1} − v_{2} + v ∈ \overline{x}, also \overline{y} ⊆ \overline{x}. Symmetrisch gilt \overline{x} ⊆ \overline{y} und damit \overline{x} = \overline{y}. Lemma 6.3. Je zwei Nebenklassen haben gleich viele Elemente Beweis. Die Abbildung ψ : \overline{x} ∋ z ↦ z + (y − x) ∈ \overline{y} ist bijektiv mit der Umkehrung \overline{y} ∋ z ↦ z + (x − y) ∈ \overline{x}. Tatsächlich ist ψ(z) = ψ(x + v) = x + v + (y − x) = y + v ∈ \overline{y}. Definition 6.4. Für einen (n, k)-Code V ⊆ K^{n} schreiben wir die Elements von K^{n} in eine Tafel. In der ersten Zeile stehen die Elemente von V. An erster Stelle der Tafel steht die 0 ∈ V. Aus jeder Nebenklasse \overline{x} ∈ K^{n}/V wählen wir ein Element u aus, einen Repräsentanten, und schreiben alle diese Repräsentanten R in die erste Spalte. In die übrigen Felder der Tafel schreiben wir die Summen der links und oben über dem Feld stehenden Elemente u + v mit u ∈ R und v ∈ V. Eine solche Tafel nennen wir Standardtafel. Sie besitzt q^{n} Elemente ausgeteilt in q^{k} Spalten und q^{n−k} Zeilen. Beispiel 6.5. Für unser Beispiel ist

(00000) (10011) (01010) (11001) (00101) (10110) (01111) (11100)
(10000) (00011) (11010) (01001) (10101) (00110) (11111) (01100)
(01000) (11011) (00010) (10001) (01101) (11110) (00111) (10100)
(00100) (10111) (01110) (11101) (00001) (10010) (01011) (11000)

eine Standardtafel. Bemerkung 6.6. Zur Dekodierung bezüglich des Codes V ⊆ K^{n} wähle man nun den empfangenen Vektor y = u + v aus der Tafel und dekodiere ihn zu dem in V gelegenen Vektor v. Das ist eine korrekte Dekodierung genau dann, wenn u, der Repräsentant der zugehörigen Nebenklasse, der Fehler bei der Übertragung war.

Man beachte, daß der Hamming-Abstand eines empfangenen Vektors y zu dem am Anfang der Spalte stehenden Vektor v ∈ V des Codes genau gleich dem Hamming-Gewicht des Differenzvektors ∥u∥ = ∥y −x∥ = d(y, x) ist. Daher wählt man als Repräsentanten Vektoren minimalen Hamming-Gewichtes in der entsprechenden Nebenklasse. Beispiel 6.7. In unserem Beispiel sehen wir, daß genau die Fehler (10000), (01000), (00100) korrigiert werden können.

Die dritte und vierte Zeile des oben gegebenen Beispiels zeigen, daß auch durch die Bedingung minimalen Hamming-Gewichts der Repräsentant noch nicht eindeutig bestimmt ist. Der gegebene Code hat das Hamming-Gewicht 2, kann also auch (global) keine Fehler korrigieren.

Wenn wir jedoch den dualen (5,2)-Code betrachten

V^{⊥} = {(0 0 0 0 0), (1 1 0 1 0), (1 0 1 0 1), (0 1 1 1 1)}

betrachten, dann hat dieser die Kontrollmatrix

( \begin{matrix}1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 1 & 0 \\ 1 & 0 & 1 \end{matrix} )

und damit das Hamming-Gewicht 3, kann also einen Fehler immer (!) korrigieren. Das zeigt auch die zugehörige Standardtafel

(00000) (11010) (10101) (01111)
(00001) (11011) (10100) (01110)
(00010) (11000) (10111) (01101)
(00100) (11110) (10001) (01011)
(01000) (10010) (11101) (00111)
(10000) (01010) (00101) (11111)
(01001) (10011) (11100) (00110)
(01100) (10110) (11001) (00011)

Man kann alle einzeln auftreten Fehler und die Doppelfehler (01001) und (01100) korrigieren.

Bemerkung 6.8. Das Problem bei dieser Dekodierung ist, daß die Tafel eines binären (50,30)-Codes mehr als 10^{15} Einträge hat, in denen man (unsystematisch) nach den empfangenen Wort suchen muß, um es zu dekodieren.

Definition 6.9. Sei V ⊆ K^{n} ein Code und H eine Kontrollmatrix. Sei x ∈ K^{n} ein beliebiger (empfangener) Vektor. Dann heißt

s = xH

das Syndrom, der Paritäts-Prüfungs-Vektor oder der Kontrollvektor von x.

Lemma 6.10. x ∈ K^{n} ist genau dann ein Codewort, wenn sein Syndrom Null ist.

Zwei Vektoren x_{1} und x_{2} sind genau dann in derselben Nebenklasse, wenn ihre Syndrome übereinstimmen.

Insbesondere ist daher das Syndrom einer Nebenklasse eindeutig bestimmt. Weiter haben zwei Nebenklassen dasselbe Syndrom genau dann, wenn sie gleich sind.

Beweis. Dieses ist in wesentlichen der Homomorphiesatz für lineare Abbildungen. Wir wissen schon V = Ker(H), also s = xH = 0 genau dann, wenn x ∈ V. x_{1} und x_{2} sind genau dann in derselben Nebenklasse, wenn x_{1} ∈ \overline{x_{2}} genau dann, wenn

x_{1} = x_{2} + v für ein v ∈ V genau dann, wenn (v =)x_{1} − x_{2} ∈ V genau dann, wenn (x_{1} − x_{2})H = 0 genau dann, wenn x_{1}H = x_{2}H genau dann, wenn die Syndrome von x_{1} und x_{2} übereinstimmen.

Damit ist klar, daß alle Elemente einer festen Nebenklasse dasselbe Syndrom haben und daß Elemente aus verschiedenen Nebenklassen verschiedene Syndrome haben. Also kann man vom Sydrom einer Nebenklasse sprechen. Die Abbildung, die jeder Nebenklasse ihr Syndrom zuordnet, ist injektiv.

Bemerkung 6.11. Syndrom-Dekodierung: Das Syndrom eines beliebigen Elements x ∈ K^{n} läßt sich leicht ausrechnen, als s = xH. Wenn man eine Tafel bildet, in der die ausgewählten Repräsentanten der Nebenklassen (mit minimalem Hamming-Gewicht) neben den Syndromen dieser Repräsentanten stehen, genannt Syndromtafel, wenn wir also die Abbildung φ : {Syndrome} → {Repräsentanten} kennen, dann können wir wie folgt dekodieren. Man nehme einen beliebigen (empfangenen) Vektor x ∈ K^{n}, bilde ihn auf sein Syndrom ab durch xH — dadurch ist die Nebenklasse von x schon bestimmt, bilde den zugehörigen Repräsentanten u := φ(xH) und berechne v := x − u. Dann hat man einen Vektor v ∈ V mit der Eigenschaft, daß der Hamming-Abstand d(x, v) = ∥x − v∥ = ∥u∥ minimal ist unter den Hamming-Abständen d(x, v′) für alle v′ ∈ V. Für ein beliebiges v′ ∈ V ist nämlich (x − v′)H = xH − v′H = xH, d. h. x und x − v′ liegen in derselben Nebenklasse und haben damit denselben Repräsentanten u. Damit ist d(x, v) = ∥x−v∥ = ∥u∥ ≤ ∥x−v′∥ = d(x, v′).

Zur Darstellung von φ : {Syndrome} → {Repräsentanten} benötigen wir für einen binären (50,30)-Code nur noch 2 Spalten mit je 10^{6} Elementen, eine wesentliche Verbesserung gegenüber der Standardtafel mit 10^{15} Einträgen. Darüber hinaus kann man die Syndromeinträge so ordnen, daß sie in lexikographisch aufsteigender Reihenfolge auftreten, wodurch die Suche nach dem entsprechenden Eintrag wesentlich verkürzt wird.

Die Standardtafeln unseres Beispiels für einen Code und seinen dualen Code verringern sich also auf

(00) (00000)
(11) (10000)
(10) (01000)
(01) (00100)

bzw.

(000) (00000)
(101) (00001)
(110) (00010)
(001) (00100)
(010) (01000)
(100) (10000)
(111) (01001)
(011) (01100)

Die hier diskutierte Methode der Syndromdekodierung ist eine der einfachsten Methoden, die für alle linearen Codes angewendet werden kann. Für große Codes ist jedoch die Sydromtafel immer noch unhandlich groß. Speziellere Codes gestatten elegantere Fehlerkorrektur und Dekodierung.

7. Hamming-Codes

Definition 7.1. Hamming-Codes Sei m ∈ ℕ eine natürliche Zahl. Wir bilden eine Matrix mit 2^{m} − 1 Zeilen und m Spalten. Die Zeilen mögen aus allen m-Tupeln aus K = 𝔽_{2} außer der Null bestehen, also aus allen Elementen aus 𝔽_{2}^{m} \{0}. Man beachte, daß jeder Vektor bei der Addition zu sich selbst invers ist, daß also die Summe zweier verschiedener Zeilen nicht die Nullzeile ist. Damit sind je zwei verschiedene Vektoren dieser Matrix linear unabhängig.

Wir betrachten diese Matrix als Kontrollmatrix für einen Code V = Ker(H). Die Codewörter haben die Länge 2^{m} − 1, das Hamming-Gewicht dieses Codes ist ∥V ∥ = 3 nach (4.3), V hat die Dimension 2^{m}−1−m und jedes Codewort hat m Kontrollbits. Damit haben wir einen (2^{m}−1, 2^{m}−1−m)-Code konstruiert, der 2-fehlererkennend und 1-fehlerkorrigiernd ist. Sei also n = 2^{m} − 1 und k = 2^{m} − 1 − m. Der (n, k)-Code hat nach (6.4) 2^{n−k} = 2^{m} Nebenklassen und damit 2^{m} − 1 korrigierbare Fehler, unter ihnen die Einzelfehler. Da die Länge der Codewörter ebenfalls 2^{m} − 1 ist, sind die Repräsentanten kleinsten Hamming-Gewichts genau die Einzelfehler für diesen Code. Dieser Code wird (n, k)-Hamming-Code genannt.

Es gilt also

Lemma 7.2. In einem Hamming-Code sind die Repräsentanten der Nebenklassen kleinsten Hamming-Gewichts genau die Einzelfehler für diesen Code.

Beispiel 7.3. Der in (2.1) beschriebene Code ist der Hamming-Code zu m = 3, n = 2^{3}−1 = 7 und k = n − m = 7 − 3 = 4. Die Kontrollmatrix ist

H = ( \begin{matrix}0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\ 1 & 1 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix} ) .

Sie gehört gemäß (5.3) zu einer systematischen erzeugenden Matrix

B = ( \begin{matrix}1 & 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 \end{matrix} ) .

Satz 7.4. Hamming-Dekodierung Wenn man bei dem Aufbau der Kontrollmatrix H in die i-te Zeile die Binärzahl für i schreibt, dann ergibt das Syndrom xH für einen Vektor x ∈ K^{n} den Binärwert für diejenige Stelle, an der der Einzelfehler aufgetreten ist.

Beweis. Wenn v ∈ V übertragen wird und der Einzelfehler bei der Übertragung e_{i} ist, d. h. an der i-ten Stelle ist, wenn also v + e_{i} empfangen wird, dann ist das Syndrom s = (v + e_{i})H = e_{i}H = h_{i} die i-te Zeile von H, also die binäre Darstellung der Zahl i und damit der Fehlerstelle.

Beispiel 7.5. Eine Kontrollmatrix für einen Code ist nicht eindeutig bestimmt. Wenn wir als Kontrollmatrix

H = ( \begin{matrix}0 & 0 & 1 \\ 0 & 1 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 0 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\ 1 & 1 & 1 \end{matrix} )

wählen, dann ist diese wegen BH = 0 Kontrollmatrix für dieselbe erzeugende Matrix B und den dadurch erzeugten Code. Diese Kontrollmatrix erlaubt eine Fehlerkorrektur wie im Beispiel (2.1) mit den Vektoren

a = (0001111),
b = (0110011),
c = (1010101).

Satz 7.6. Man erhält einen 1-fehlerkorrigierenden Code in K^{n}, indem man ein minimales m mit n ≤ 2^{m} − 1 wählt, eine Kontrollmatrix H wie in (7.4) zum (2^{m} − 1, 2^{m} − 1 − m)- Hamming-Code bildet und aus dieser Matrix lediglich die ersten n Zeilen verwendet. So erhält man einen (n, n − m)-Code, der oft ebenfalls Hamming-Code genannt wird.

Beweis. Die neue Kontrollmatrix H_{n} erfüllt immer noch die Eigenschaft, daß je zwei verschiedene Zeilen linear unabhängig sind. Weiter sind schon die ersten drei Zeilen linear abhängig. Damit hat der Code V das Hamming-Gewicht ∥V ∥ = 3.

Wegen der Bedingung 2^{m−1} ≤ n kommen alle Vektoren e_{1}, …, e_{m} in der Matrix H_{n} vor. Daher gilt Rang(H_{n}) = m = Spaltenzahl von H_{n}. Somit gilt dim(V) = dim(Ker(H_{n})) = n − Rang(H_{n}) = n − m.

8. Polynomringe und endliche Körper

Lemma 8.1. Sei K[x] der K-Vektorraum mit der abzählbar unendlichen Basis 1 := x^{0}, x := x^{1}, x^{2}, x^{3}, …, x^{n}, . . .. Dann ist K[x] ein Ring mit der Multiplikation

(∑_{i=0}^{m} α_{i}x^{i})(∑_{j=0}^{n} β_{j}x^{j}) := ∑_{i=0}^{m} ∑_{j=0}^{n} α_{i}β_{j}x^{i+j} = ∑_{k=0}^{m+n}(∑_{l=0}^{k} α_{l}β_{k−l})x^{k}.

Beweis. Jeder Vektor aus K[x] läßt sich daher in eindeutiger Weise (mit eindeutig bestimmten Koeffizienten) als ∑_{i=0}^{n} α_{i}x^{i} = α_{0} + α_{1}x + … + α_{n}x^{n} schreiben. Die oben angegebene Multiplikation ist die bekannte Multiplikation von Polynomen.

Die Addition des Vektorraumes K[x] verwenden wir als Addition des Ringes K[x]. Es bleibt die Multiplikation zu untersuchen. Die angegebene Multiplikationsregel reduziert sich auf den Basiselementen zu x^{i}x^{j} = x^{i+j}.

Die Multiplikation von links mit x_{i} ergibt auf den Basiselementen x^{i}x^{j} = x^{i+j} und läßt sich eindeutig zu einer linearen Abbildung x^{i} : K[x] → K[x] fortsetzen als x^{i}(∑_{j=0}^{n} β_{j}x^{j}) = ∑_{j=0}^{n} β_{j}x^{i+j}, also zu der oben definierten Multiplikation.

Die Multiplikation von rechts mit ∑_{j=0}^{n} β_{j}x^{j} ergibt auf den Basiselementen x^{i}(∑_{j=0}^{n} β_{j}x^{j}) = ∑_{j=0}^{n} β_{j}x^{i+j} und läßt sich eindeutig zu einer linearen Abbildung (∑_{j=0}^{m} β_{j}x^{j}) : K[x] → K[x] fortsetzen als (∑_{i=0}^{m} α_{i}x^{i})(∑_{j=0}^{n} β_{j}x^{j}) = ∑_{i=0}^{m} α_{i}(∑_{j=0}^{n} β_{j}x^{i+j}) = ∑_{i=0}^{m} ∑_{j=0}^{n} α_{i}β_{j}x^{i+j}, also zu der oben definierten Multiplikation. Damit ist die Multiplikation distributiv.

Das Element 1 := x^{0} ist das Einselement der Multiplikation.

Die Assoziativität ergibt sich aus

[(∑_{i=0}^{m} α_{i}x^{i})(∑_{j=0}^{n} β_{j}x^{j})](∑_{k=0}^{r} γ_{k}x^{k}) = [∑_{i=0}^{m} ∑_{j=0}^{n} α_{i}β_{j}x^{i+j}](∑_{k=0}^{r} γ_{k}x^{k})
= ∑_{i=0}^{m} ∑_{j=0}^{n} ∑_{k=0}^{r} α_{i}β_{j}γ_{k}x^{i+j+k}
= (∑_{i=0}^{m} α_{i}x^{i})[∑_{j=0}^{n} ∑_{k=0}^{r} β_{j}γ_{k}x^{j+k}]
= (∑_{i=0}^{m} α_{i}x^{i})[(∑_{j=0}^{n} β_{j}x^{j})(∑_{k=0}^{r} γ_{k}x^{k})]

Definition 8.2. Sei f(x) = ∑_{i=0}^{n} α_{i}x^{i} ≠ 0 ein Polynom. Die eindeutig bestimmte größte Zahl n mit α_{n} ≠ 0 heißt der Grad des Polynoms f(x). α_{n} heißt der höchste Koeffizient des Polynoms.

Man kann durch Betrachtung der höchsten Koeffizienten einsehen, daß K[x] ein nullteilerfreier Ring ist.

Lemma 8.3. Die Polynome in K[x] vom Grade höchstens n bilden einen Vektorraum P_{n} der Dimension n + 1.

Beweis. Diese Polynome werden von den linear unabhängigen Polynomen 1, x, x^{2}, x^{3}, …, x^{n} erzeugt.

Theorem 8.4. Im Polynomring K[x] gilt der euklidische Divisionsalgorithmus:

zu jedem Paar f, g ∈ K[x] von Polynomen mit g ≠ 0 gibt es ein eindeutig bestimmtes Paar von Polynomen q, r ∈ K[x] (Quotient und Rest), so daß gilt

f = q · g + r  und  Grad(r) < Grad(g).

Beweis. Wir zeigen zunächst die Eindeutigkeit der Zerlegung. Sei f = qg + r = q′g + r′ mit Grad(r) < Grad(g) und Grad(r′) < Grad(g). Dann ist (q − q′)g + (r − r′) = 0. Da auch Grad(r − r′) < Grad(g) gilt, ist (q − q′)g = 0. Insbesondere muß der höchste Koeffizient von (q − q′)g Null sein, was nur geht, wenn q − q′ = 0 gilt. Dann ist aber auch r − r′ = 0 und damit die Eindeutigkeit gezeigt.

Wenn der Grad von f kleiner ist, als der Grad von g, dann setzen wir q = 0 und r = f. Wenn Grad(f) = n + 1 ist und der Satz für Polynome vom Grad n schon bewiesen ist, dann sei γ := α_{n+1}/β_{k} der Quotient der höchsten Koeffizienten α_{n+1} von f und β_{k} von g. Dann ist f′ := f − γg ein Polynom vom Grad kleiner oder gleich n. Wir können also schreiben f′ = q′g + r mit Grad(r) < Grad(g). Also ist f = (α + q′)g + r mit Grad(r) < Grad(g).

Folgerung 8.5. Ein Polynom f(x) in K[x] vom Grad n hat höchstens n verschiedene Nullstellen in K.

Beweis. Seien α_{1}, …, α_{k} paarweise verschiedene Nullstellen von f(x), dann ist f(x) = (x − α_{1}) · (x − α_{2}) · . . . · (x − α_{k}) · g(x), also k ≤ n. Nach dem Divisionsalgorithmus ist nämlich f(x) = (x − α_{1}) · g_{1}(x) + β_{1}. Wenn man für x den Wert α_{1} einsetzt, dann erhält man 0 = β_{1}. Für jede weitere Nullstelle α_{i} von f(x) ist dann aber 0 = f(α_{i}) = (α_{i} − α_{1})g(α_{i}), also sind die α_{2}, …, α_{k} Nullstellen von g_{1}(x). Durch Induktion nach dem Grad erhält man die behauptete Aussage.

Definition 8.6. Vor Polynomen in K[x] können wir wie im reellen Fall Ableitungen bilden, hier formale Ableitungen genannt. Wir bilden nämlich die eindeutig bestimmte lineare Abbildung d/dx : K[x] → K[x], indem wir auf der Basis (x^{i}) vorschreiben d/dx(x^{i}) := ix^{i−1} (für i = 0 soll d/dx(x^{0}) = 0 gelten).

Lemma 8.7. Für die formale Ableitung von Polynomen gilt die Produktregel.

Beweis. Es ist d/dx(x^{i}x^{j}) = (i + j)x^{i+j−1} = ix^{i−1}x^{j} + jx^{i}x^{j−1} = d/dx(x^{i})x^{j} + x^{i}d/dx(x^{j}). Daraus leitet sich wegen der Linearität die Produktregel ab:

d/dx(fg) = d/dx(f)g + fd/dx(g).

Definition 8.8. Sei K ein Körper. Die kleinste Zahl p > 0, so daß 1 + … + 1 = 0 mit genau p Summanden in K gilt, heißt die Charakteristik von K. Wenn es keine solche Zahl gibt, so wird die Charakteristik als 0 definiert.

Lemma 8.9. Wenn K eine Charakteristik p > 0 hat, dann ist p eine Primzahl.

Beweis. Sei p = qr mit q < p und r < p, p, q, r ∈ ℕ. Dann ist (1 + … + 1)_{q mal} · (1 + … + 1)_{r mal} = (1 + … + 1)_{qr mal} = 0 in K. Daher ist einer der Faktoren Null, z.B. (1 + … + 1)_{q mal} = 0 in K im Widerspruch zu q < p. Es ist somit einer der Faktoren gleich p, der andere ist 1. Daher ist p eine Primzahl.

Lemma 8.10. Sei K ein Körper der Charakteristik p > 0.

1. Für α, β ∈ K gilt (α + β)^{p} = α^{p} + β^{p}.

2. Weiter ist (x − 1)^{p} = x^{p} − 1 in K[x].

Beweis. Nach der binomischen Formel ist (α + β)^{p} = ∑_{i=0}^{p} \binom{p}{i}α^{i}β^{p−i} = α^{p} + β^{p}, denn \binom{p}{i} = \frac{p·...·(p−i+1)}{1·...·i} ≡ 0 mod p, weil p als Primzahl in diesem Bruch nicht gekürzt werden kann. Der Beweis für (x − 1)^{p} = x^{p} − 1 verläuft analog mit denselben Binomialkoeffizienten.

Lemma 8.11. Sei K ein endlicher Körper. Dann hat K eine positive Charakteristik p > 0.

Beweis. Die Elemente 1, 1 + 1, 1 + 1 + 1, … in K sind nicht alle paarweise verschieden, weil K nur endlich viele Elemente hat. Sei also (1 + … + 1)_{r mal} = (1 + … + 1)_{s mal} mit r < s. Dann können r Summanden 1 gekürzt werden, also gilt (1 + … + 1)_{(s−r) mal} = 0. Es gibt also mindestens eine positive Zahl s − r mit dieser Eigenschaft. Die kleinste solche Zahl ist dann die positive Charakteristik.

Definition 8.12. Sei f ∈ K[x] ein Polynom vom Grad(f) > 0. Das Polynom f heißt irreduzibel, wenn für jede Zerlegung f = gh von f in ein Produkt von zwei Polynomen g und h eines der beiden Polynome vom Grad 0, d. h. eine Konstante, ist.

Satz 8.13. Sei K ein Körper und f ∈ K[x] ein irreduzibles Polynom. Dann ist die Menge der Nebenklassen K[x]/(f) ein Körper.

Wenn K q Elemente besitzt und f den Grad n hat, dann hat K[x]/(f) die Dimension n und damit q^{n} Elemente.

Beweis. Mit (f) bezeichnen wir den Unterraum {gf ∈ K[x]|g ∈ K[x]}. Dieser Unterraum ist ein Ideal, d. h. für jedes Element h ∈ K[x] und jedes Element gf ∈ (f) ist auch h(gf) = (hg)f ∈ (f). Ohne Einschränkung der Allgemeinheit können wir annehmen, daß f höchsten Koeffizienten 1 hat, indem wir das ursprüngliche f mit α_{n}^{−1} multiplizieren, also f durch α_{n}^{−1}f ersetzen. Dann ist (f) = (α_{n}^{−1}f).

Die Menge der Nebenklassen K[x]/(f) bildet eine additive Gruppe durch \overline{g} + \overline{h} := \overline{g + h} und sogar einen Ring durch \overline{g}\overline{h} := \overline{gh}. Die wichtigste Tatsache, die hierfür nachgewiesen werden muß, ist, daß diese Verknüpfungen von der Auswahl der Repräsentanten der Nebenklassen unabhängig sind.

Diesen Beweis und die Überprüfung der Ringeigenschaft überlassen wir dem Hörer (Leser). Um nun zu sehen, daß K[x]/(f) ein Körper ist, zeigen wir, daß jedes Element \overline{g} ≠ 0 ein

Inverses unter der Multiplikation besitzt. Dazu betrachten wir die Menge (g, f) = {p_{1}g + p_{2}f|p_{1}, p_{2} ∈ K[x]\}. Wir führen die Division g = qf + r durch. Dann ist \overline{g} = \overline{r} ≠ 0 und Grad(r) < Grad(f). Also gibt es in (g, f) ein Element r = 1g − qf ≠ 0 mit Grad(r) < Grad(f).

Sei s ∈ (g, f), s ≠ 0 von minimalem Grad. Eine Division mit Rest ergibt f = qs + t. Da t = f − qs ∈ (g, f) und Grad(t) < Grad(s) und s ≠ 0 von minimalem Grad, ist t = 0 und daher f = qs. Nun ist f irreduzibel und Grad(s) < Grad(f), also ist Grad(s) = 0 und s = α ∈ K \ {0}. Da s ∈ (g, f) und auch 1 = α^{−1}s ∈ (g, f), gibt es Polynome p_{1}, p_{2} mit 1 = p_{1}g +p_{2}f, also \overline{1} = \overline{p_{1}g} +\overline{p_{2}f} = \overline{p}_{1}\overline{g}. Damit ist \overline{p}_{1} Inverses zu \overline{g} und K[x]/(f) ein Körper.

Da jede Linearkombination ∑_{i=0}^{n−1} α_{i}x^{i} mit von Null verschiedenen Koeffizienten nicht in (f) liegt, denn Vielfache von f haben höheren Grad, ist \overline{∑_{i=0}^{n−1} α_{i}x^{i}} = ∑_{i=0}^{n−1} α_{i}\overline{x^{i}} ≠ \overline{0} in K[x]/(f), falls nicht alle Koeffizienten Null sind, d. h. die \overline{1}, \overline{x}, \overline{x^{2}}, …, \overline{x^{n−1}} sind linear unabhängig. Da aber höhere Potenzen x^{n+i} durch f mit Rest teilbar sind: x^{n+i} = qf +r und daher \overline{x^{n+i}} = \overline{r} = \overline{∑_{i=0}^{n−1} α_{i}x^{i}} für geeignete α_{i} gilt, bilden die \overline{1}, \overline{x}, \overline{x^{2}}, …, \overline{x^{n−1}} eine Basis für K[x]/(f). Damit ist dim(K[x]/(f)) = n = Grad(f).

Lemma 8.14. 1) Zu jeder Primzahlpotenz q = p^{n} gibt es (bis auf Isomorphie) genau einen Körper GK(q) mit q Elementen.

2) Jede endliche Untergruppe von der multiplikativen Gruppe K^{∗} eines Körpers K ist zyklisch.

3) Sei K ⊆ L eine Körpererweiterung, so daß dim_{K} L < ∞ gilt. Zu jedem Element α ∈ L gibt es genau ein irreduzibles Polynom p(x) ∈ K[x] von höchstem Koeffizienten 1 mit p(α) = 0, genannt Minimalpolynom für α.

Der Leser sollte die Beweise hierfür in guten Algebralehrbüchern nachlesen.

Lemma 8.15. Sei n ∈ ℕ. Dann gibt es ein irreduzibles Polynom p(x) ∈ 𝔽_{2}[x] vom Grad n mit Nullstelle α ∈ GF (2^{n}), so daß die Ordnung von α in GF (2^{n})^{∗} genau 2^{n} − 1 ist, also α^{2^{n}−1} = 1 gilt und 2^{n} − 1 die kleinste solche natürliche Zahl ist.

Beweis. Da GF (2^{n})^{∗} eine zyklische Gruppe ist, gibt es ein (erzeugendes) Element α ∈ GF (2^{n})^{∗} von der Ordnung 2^{n} − 1. Sei p(x) das Minimalpolynom für α. Da GF (2^{n}) = 𝔽_{2}(α), ist GF (2^{n}) ≅ 𝔽_{2}[x]/(p(x)) und Grad(p(x)) = n.

9. Zyklische Codes

Wir haben bisher fast ausschließlich Codes studiert, deren Hamming-Gewichte klein (z.B. 3 oder 4) waren. Sie sind höchstens 1-fehlerkorrigierend. Mit den zyklischen (Polynom-) Codes erhalten wir Codes mit höherem Hamming-Gewicht.

Bemerkung 9.1. Seien k und n mit k < n gegeben, und sei g ein Polynom vom Grad n−k. Dann definiert g die folgende lineare Abbildung g : P_{k−1} ∋ f ↦ gf ∈ P_{n−1}. Wir betrachten die entsprechende lineare Abbildung auf den Koordinatensystemen von Koeffizientenvektoren der Polynome ĝ: K^{k} → K^{n}. Wenn g = ∑_{i=0}^{n−k} γ_{i}x^{i} ist, dann ist die darstellende Matrix von g bezüglich der Basen 1, x, x^{2}, …, x^{k−1} bzw. 1, x, x^{2}, …, x^{n−1} gegeben durch

M = (\begin{matrix}γ_{0} & 0 & & … & 0 \\ γ_{1} & γ_{0} & 0 & … & 0 \\ ⋮ & ... & ... & & ⋮ \\ ⋮ & & ... & ... & ⋮ \\ ⋮ & & & γ_{1} & γ_{0} \\ ⋮ & & & & γ_{1} \\ γ_{n−k} & & & & ⋮ \\ 0 & γ_{n−k} & & & ⋮ \\ ⋮ & & ... & & ⋮ \\ ⋮ & & & ... & ⋮ \\ 0 & … & & 0 & γ_{n−k} \end{matrix}) ,

wie man sofort aus dem Polynomprodukt

gf = ∑_{i=0}^{n−k} γ_{i}x^{i} ∑_{j=0}^{k−1} β_{j}x^{j} = ∑_{t=0}^{n−1}(∑_{j=0}^{k−1} γ_{t−j}β_{j})x^{t}

abliest.

Definition 9.2. Ein Code V = Bi(ĝ), der von einem Polynom g in der Form ĝ: K^{k} → K^{n} mit Grad(g) ≤ n − k erzeugt wird, heißt ein Polynomcode.

Definition 9.3. Ein Code V ⊆ K^{n} heißt zyklisch, wenn für alle x = (ξ_{1}, …, ξ_{n}) ∈ V gilt (ξ_{n}, ξ_{1}, …, ξ_{n−1}) ∈ V. Also ist jede zyklische Vertauschung eines Codewortes wieder ein Codewort.

Theorem 9.4. Seien k und n mit k < n gegeben. Sei g ∈ P_{n−k} vom Grad n − k ein Teiler von x^{n} − 1 ∈ K[x]. Dann ist der durch g erzeugte Polynomcode ein zyklischer Code. g heißt dann ein Generatorpolynom für den zyklischen Code.

Beweis. Sei gg′ = x^{n}−1. Dann ist x^{n} = gg′+1. Sei gf = α_{0}+α_{1}x+…+α_{n−1}x^{n−1} Darstellung eines Codewortes (α_{0}, …, α_{n−1}). Wir multiplizieren diese Gleichung mit x und erhalten xgf = α_{0}x + α_{1}x^{2} + … + α_{n−1}x^{n} = α_{0}x + α_{1}x^{2} + … + α_{n−1}(gg′ + 1) = α_{n−1} + α_{0}x + α_{1}x^{2} + …+α_{n−1}gg′ und daraus α_{n−1}+α_{0}x+α_{1}x^{2}+…+α_{n−2}x^{n−1} = xgf −α_{n−1}gg′ = g(xf −α_{n−1}g′). Da Grad(xf − α_{n−1}g′) ≤ n − 1 − Grad(g) = k − 1 gilt, ist also auch (α_{n−1}, α_{0}, …, α_{n−2}) ein Codewort und der Polynomcode zyklisch.

Bemerkung 9.5. Es gilt auch die Umkehrung des Satzes. Sei V ⊆ K^{n} ein zyklischer Code. Dann gibt es ein Polynom g ∈ P_{n−k} mit g teilt x^{n} − 1, das diesen zyklischen Code erzeugt. Wir benötigen den Beweis hier nicht.

Theorem 9.6. Der durch g_{k} := (x − 1)^{p−k} über K = GF (q) generierte zyklische Code hat die Hamming-Norm p − k + 1.

Beweis. Für k = 1 ist ĝ_{1} : K^{1} → K^{p} gegeben durch ĝ_{1}(α) = α · (x − 1)^{p−1}. Nun ist (x−1)(x−1)^{p−1} = (x−1)^{p} = x^{p}−1 = (x−1)(x^{p−1}+x^{p−2}+…+x+1). Da K[x] nullteilerfrei ist, ist (x−1)^{p−1} = x^{p−1}+x^{p−2}+…+x+1. Damit erhalten wir g_{1}·α = α·(x^{p−1}+x^{p−2}+…+x+1), also ĝ_{1}(α) = (α, …, α). Offenbar hat diese Kodierung nach Definition die Hamming-Norm p.

Für k = p ist g_{p} = 1, also ĝ_{p} : K^{p} → K^{p} die identische Abbildung mit der Hamming-Norm 1.

Wir zeigen jetzt ∥ĝ_{k+1}∥ < ∥ĝ_{k}∥ für alle 0 ≤ k < p. Sei (α_{0}, …, α_{p−1}) ∈ Bi(ĝ_{k}) ein Codewort minimaler Norm, also mit einer minimalen Anzahl von Koeffizienten ungleich Null. Weil wir einen zyklischen Code haben, können wir α_{0} ≠ 0 annehmen. Für f ≠ 0 gilt Grad(g_{k}f) = Grad(g_{k}) + Grad(f) = (p − k) + Grad(f) ≥ p − k, also ist auch α_{i} ≠ 0 für ein i > 0. Dann ist das zugehörige Polynom α_{0} + α_{1}x + … + α_{p−1}x^{p−1} = g_{k}f = (x − 1)^{p−k}f. Wir bilden die formale Ableitung und erhalten α_{1} + 2α_{2}x + … + (p − 1)α_{p−1}x^{p−2} = (g_{k}f)′ = (p − k)(x − 1)^{p−k−1}f + (x − 1)^{p−k}f′ = (x − 1)^{p−(k+1)}((p − k)f + (x − 1)f′). Daher ist (α_{1}, 2α_{2}, …, (p−1)α_{p−1}, 0) ∈ Bi(ĝ_{k+1}) ein Element kleinerer Norm. Damit ist ∥ĝ_{k+1}∥ < ∥ĝ_{k}∥ und

1 = ∥ĝ_{p}∥ < ∥ĝ_{p−1}∥ < … < ∥ĝ_{1}∥ = p,

woraus ∥ĝ_{k}∥ = p − k + 1 folgt.

10. Beispiel eines BCH-Codes

Lemma 10.1. p_{1}(x) := x^{4}+x+1 ist irreduzibel mit Nullstelle α ∈ GF (2^{4}) mit der Ordnung 2^{4} − 1 = 15.

Beweis. p_{1}(x) hat keine Nullstelle in 𝔽_{2}. Weiter ist x^{2}+x+1 das einzige irreduzible Polynom vom Grad 2. Es ist x^{4} + x + 1 = (x^{2} + x)(x^{2} + x + 1) + 1. Also ist p_{1}(x) irreduzibel. Für eine Nullstelle α ∈ GF (2^{4}) = 𝔽_{2}[x] gilt sicher α^{15} = 1. Aber es gelten α^{3} ≠ 1, weil 1, α, α^{2}, α^{3} Basis für GF (2^{4}) bilden, und α^{5} = αα^{4} = α(α + 1) = α^{2} + α ≠ 1. Daher ist die Ordnung |α| = 15.

Lemma 10.2. p_{2}(x) := x^{4} + x^{3} + x^{2} + x + 1 ist irreduzibel mit Nullstelle α^{3}.

Beweis. p_{2}(x) hat keine Nullstelle in 𝔽_{2}. Es ist x^{4} +x^{3} +x^{2} +x+1 = x^{2}(x^{2} +x+1)+(x+1). Damit ist p_{2}(x) irreduzibel. Weiter ist α^{3} Nullstelle von p_{2}(x), denn es gilt α^{12}+α^{9}+α^{6}+α^{3}+ 1 = (α+1)^{3}+α(α+1)^{2}+α^{2}(α+1)+α^{3}+1 = α^{3}+α^{2}+α+1+α^{3}+α+α^{3}+α^{2}+α^{3}+1 = 0.

Lemma 10.3. m(x) := p_{1}(x)p_{2}(x) hat Nullstellen α, α^{2}, α^{3}, α^{4}.

Beweis. Da p_{1}(x)^{2} = p_{1}(x) gilt, hat p_{1}(x) Nullstellen α, α^{2}, α^{4}, α^{8}.

Beispiel 10.4. Ein B.C.H.-Code (R.C.Bose, D.K.Ray-Chaudhuri, A.Hocquenghem 1959/60)

Wir konstruieren Kodierung, Dekodierung und Fehlerkorrektur für einen (15,7)-Code mit Hilfe von α ∈ GF (16).

Betrachte f : 𝔽_{2}^{7} ∋ (α_{14}, …, α_{8}) ↦ α_{14}x^{14}+…+α_{8}x^{8} ∈ 𝔽_{2}[x]_{14} = P_{14}. Das ist eine lineare Abbildung. Sei a = (α_{14}, …, α_{8}) zunächst fix. Dann kann man das Polynom f(a) = p(x) schreiben als p(x) = q(x)m(x) + r(x). Wir bilden s(x) := p(x) − r(x). Es sei s(x) die Kodierung von a. Sie ist durch a, α und α^{3} eindeutig bestimmt, da p_{1}(x) das Minimalpolynom von α ist, p_{2}(x) das Minimalpolynom von α^{3} ist, dadurch m(x) eindeutig bestimmt ist, und da die Division mit Rest eindeutig bestimmte q(x) und r(x) ergibt.

Beachte, daß r(x) den Grad < 8 hat und daher die Koeffizienten α_{7}, …, α_{0} von s(x) bestimmt, während f(a) die Koeffizienten α_{14}, …, α_{8} von s(x) bestimmt. Weiter hängt s(x) linear von a ab.

Sei nun t(x) ∈ 𝔽_{2}[x]_{14} das empfangene gestörte Polynom und z(x) := t(x) − s(x) das Fehlerpolynom. Es gelten

z(α) = t(α), weil s(α) = 0,
z(α^{2}) = t(α^{2}), weil s(α^{2}) = 0,
z(α^{3}) = t(α^{3}), weil s(α^{3}) = 0,
z(α^{4}) = t(α^{4}), weil s(α^{4}) = 0.

Die Werte t(α^{i}) sind aber bekannt. Wir setzen

S = ( \begin{matrix}t(α) & t(α^{2}) \\ t(α^{2}) & t(α^{3}) \end{matrix} )

Dann betrachten wir folgende Fälle:

1. Es tritt kein Fehler auf. Dann ist z(x) = 0, also auch S = 0.

2. Es tritt ein Fehler auf. Dann ist z(x) = x^{i}. Dann ist S = ( \begin{matrix}α^{i} & α^{2i} \\ α^{2i} & α^{3i} \end{matrix} ) und es gilt S

hat den Rang 1. Dieses ist die Fehlererkennung. Wir kennen t(α) und alle α^{i}. Es gibt genau ein i mit t(α) = α^{i}. Dazu muß man die Struktur von GF (16) kennen. Dann ist der Fehler an der i-ten Stelle aufgetreten.

3. Es treten zwei Fehler auf. Das ist genau dann der Fall, wenn z(x) = x^{i} + x^{j} für i ≠ j. Dann ist

S = ( \begin{matrix}α^{i} + α^{j} & α^{2i} + α^{2j} \\ α^{2i} + α^{2j} & α^{3i} + α^{3j} \end{matrix} ) = ( \begin{matrix}1 & 1 \\ α^{i} & α^{j} \end{matrix} ) ( \begin{matrix}α^{i} & 0 \\ 0 & α^{j} \end{matrix} ) ( \begin{matrix}1 & α^{i} \\ 1 & α^{j} \end{matrix} )

Diese Matrix hat den Rang 2. Damit ist eine 2-Fehlererkennung gegeben.

Zur Fehlerkorrektur beachte, daß für k = 1, 2, 3, 4 bekannt sind t(α^{k}) = z(α^{k}). Daraus sind i und j zu bestimmen. i, j sind bekannt, wenn von dem Polynom (x − α^{i})(x − α^{j}) = x^{2} + τ_{1}x + τ_{2} die Koeffizienten τ_{1} = α^{i} + α^{j} und τ_{2} = α^{i}α^{j} bekannt sind. Denn dann kennt man die Nullstellen und damit die Exponenten.

Wir bestimmen die τ_{i} aus t(x) wie folgt. Wir kennen den Wert τ_{1} = α^{i} + α^{j} = t(α) aus der Matrix S. Weil α^{i} und α^{j} Nullstellen des Polynoms sind, gilt

\begin{matrix}α^{2i} + τ_{1}α^{i} + τ_{2} = 0, \\ α^{2j} + τ_{1}α^{j} + τ_{2} = 0. \end{matrix}

Multipliziert man die erste der Gleichungen mit α^{i} und die zweite der Gleichungen mit α^{j} und addiert die Gleichungen, so erhält man

t(α^{3}) + τ_{1}t(α^{2}) + τ_{2}t(α) = (α^{3i} + α^{3j}) + τ_{1}(α^{2i} + α^{2j}) + τ_{2}(α^{i} + α^{j}) = 0,

wobei die α-Koeffizienten bekannt sind. Diese Gleichung kann man nach τ_{2} auflösen und hat damit τ_{1}, τ_{2} bestimmt. Damit ist der gefundene Code 2-fehlerkorrigierend.

24 VORLESUNG VON B. PAREIGIS IM SS 1998

Beispiel 10.5. Über dem Körper GF (64) kann man mit Polynomen vom Grad ≤ 12 folgende weitere B.C.H.-Codes ((63,k)-Codes) bestimmen:

30 Bits Information, 6 Fehler korrigierbar,
24 Bits Information, 7 Fehler korrigierbar,
18 Bits Information, 10 Fehler korrigierbar,
16 Bits Information, 11 Fehler korrigierbar,
10 Bits Information, 13 Fehler korrigierbar,
7 Bits Information, 15 Fehler korrigierbar.