Codes

Irina Schröder

29. Januar 2001

Die Codierungstheorie ist eine ganz angewandte Wissenschaft, die auf den ersten Blick gar nichts mit linearer Algebra zu tun hat. In Wirklichkeit ist lineare Algebra ein unentbehrliches Mittel zur Analyse und Konstruktion von Codes.

Das Problem ist, dass bei der Übertragung von Nachrichten oder Speicherung von Daten mehr oder weniger zufällig Fehler auftreten (in der Regel aus physikalischen Gründen). Daher wird eine Nachricht mit einer bestimmten Redundanz codiert, so dass im Prozess der Decodierung die möglichen Fehler entdeckt und korrigiert werden; dies ist gerade die Aufgabe der Codierungstheorie.

Mathematisch gesehen ist eine Nachricht eine endliche Folge von Symbolen aus einem Alphabet, für welches wir einen endlichen Körper 𝔽_{q} mit q = p^{r} (p eine Primzahl) Elementen nehmen. In der Nachrichten- und Computertechnik verwendet man häufig aus naheliegenden Gründen den Körper 𝔽_{2}, d.h. die Buchstaben 0 und 1. Jeder dieser Buchstaben bezeichnet man als ”Bit“. Das Codieren betrachten wir als eine injektive Abbildung

f : 𝔽_{q}^{k} → 𝔽_{q}^{n}, n > k > 0.

Das Bild der Abbildung f, f(𝔽_{q}^{k}) =: C ⊂ 𝔽_{q}^{n}, heißt ein Code (der Länge n); es ist also eine nicht-leere Teilmenge des 𝔽_{q}^{n}. Ist |C| = 1, so heißt der Code trivial. Triviale Codes sind im folgenden ausgeschlossen. Ist q = 2, so heißt der Code binär, für q = 3 ternär, usw. Die Elemente von C heißen Code-Wörter, und n heißt Wort-Länge von C.

Stark vereinfacht stellen wir uns eine Nachrichten-Übermittlung in drei Schritte zerlegt vor:

a ∈ 𝔽_{q}^{k}  f(a) ∈ C  b  g(b) ∈ C

Eine Botschaft wird in einen Codierer eingegeben; dies können die in bestimmten Zeitabständen gemessene Daten eines akkustischen Signals, die Schwärzung der Punkte eines Rasters zur Erfassung eines Bildes (vielleicht durch die Kamera einer Raumsonde aufgenommen) oder für den Speicher eines Computers bestimmte (eventuell selbst berechnete) Daten sein. Die Botschaft verläßt den Codierer als ein Code-Wort f(a) eines Codes C; technisch zum Beispiel als Folge von Codewörtern verschiedener Stärke. Solch ein Code-Wort durchläuft nun einen ”Informationskanal“ und ist dabei einem ”Hintergrundrauschen“ ausgesetzt. ”Informatioskanal“ kann dabei ein elektromagnetisches Feld sein, es kann aber auch für den Prozess des Abspeicherns und anschließenden Wiederaufrufens eines Binärwortes in einem Computer stehen. Auch das Wort ”Hintergrundrauschen“ ist nicht wörtlich zu nehmen; es kann elektrische Interferenz, Staub oder Kratzer auf einer CD-Platte usw. bedeuten. Dieses ”Hintergrundrauschen“ bewirkt jedenfalls, dass ein Code-Wort möglicherweise verfälscht zum Decodierer gelangt.

Es ist natürlich wünschenswert, solche Verfälschungen, d.h. Fehler zu entdecken. Die Idee ist, den Code so zu wählen, dass die Code-Wörter sich möglichst stark voneinander unterscheiden. Die Decodiervorrichtung sucht dann zu einem empfangenen Wort das zu diesem Wort ähnlichste Code-Wort heraus. Die Fehlersuche ist also in gewissem Maße durch die Unterscheidung von Code-Wörtern und Nicht-Code-Wörtern gegeben. Zu bemerken ist, dass Fehler, die mittels der Codierungstheorie behandelt werden, keine durch Menschen gezielt verursachte Veränderungen von Zeichen sind; keine Fehler in diesem Sinne sind Verlust oder Hinzufügen von Zeichen.

Das vielleicht einfachste Beispiel für einen Code ist der sogenannte Repetition-Code der Länge 3: Hier ist q = 2, k = 1, n = 3, C = {(0, 0, 0), (1, 1, 1)} ⊂ 𝔽_{2}^{3}. Die zu übertragende Information ist ”Ja“ oder ”Nein“. ”Ja“ wird in (1, 1, 1) codiert, ”Nein“ in (0, 0, 0). Empfängt der Decodierer (0, 1, 0), so ist es vernünftig anzunehmen, dass ”Nein“ gesendet wurde, denn (0, 1, 0) unterscheidet sich nur an einer Stelle von (0, 0, 0) und an zwei von (1, 1, 1). Der Decodierer gibt also ”Nein“ als decodierte Botschaft aus. Man sieht, dass dieser Code nur einen Fehler korrigiert, d.h.: Tritt höchstens an einer Stelle ein Fehler auf, so wird er auf jeden Fall erkannt und korrigiert.

Um dieses Phänomen quantitativ zu erfassen, führen wir folgende Begriffe ein: Sei x = (x_{1}, …, x_{n}) ∈ 𝔽_{q}^{n}. Das Gewicht w(x) ist die Anzahl der x_{i} ≠ 0:

w(x) := #{i | x_{i} ≠ 0}.

Das Minimalgewicht w eines Codes C ist definiert als

w = w(C) = min{w(x) | x ∈ C, x ≠ 0}.

Der Hamming-Abstand zweier Wörter x ∈ 𝔽_{q}^{n}, y ∈ 𝔽_{q}^{n} ist definiert durch

d(x, y) := w(x − y);

es ist also die Anzahl der Koeffizienten, von denen sich x, y unterscheiden. Sei C ein nicht-trivialer Code. Der Minimalabstand d eines gegebenen Code-Wortes von C ist der kleinste Abstand d(x, y), der auftritt, wenn x und y die voneinander verschiedene Wörter von C durchlaufen:

d = d(C) = min{d(x, y) | x, y ∈ C, x ≠ y}.

Ein [n, M, d]-Code ist ein Code mit einer Wort-Länge n, M Code-Wörtern und dem Minimalabstand d. Der Repetition-Code der Länge 3 ist ein [3, 2, 3]-Code.

Man kann leicht sehen, dass ein Code mit dem Minimalabstand d höchstens t-Fehler korrigiert, wobei t durch d = 2t + 1 (für ungerades d) bzw. d = 2(t + 1) (für gerades d) definiert ist.

Um Nachrichten sicher zu übermitteln, ist man demnach an Codes mit möglichst großem Minimalabstand interessiert, d.h. mit sehr stark unterschiedlichen Code-Wörtern. Dies zieht aber nach sich, dass man ein großes Alphabet oder Wörter mit sehr vielen Stellen verwenden muss, also jedenfalls großer Aufwand. Um bei unserem Beispiel, dem Repetition-Code, zu bleiben: Es ist auch von Nachteil 3 Bits für eine Ein-Bit-Information zu senden. Anschaulich gesagt: Eine Raumsonde unterliegt Energie- und Zeitbeschränkungen, bei Computern ist kein Speicherplatz zu vergeuden.

Um diese Problematik quantitativ zu erfassen, führen wir neben dem Minimalabstand d noch die Informationsrate R eines Codes in 𝔽_{q}^{n} ein:

R = \frac{log_{q} |C|}{log_{q} |𝔽_{q}^{n}|}.

Hierbei steht |C| bzw. |𝔽_{q}^{n}| für die Anzahl der Code-wörter bzw. überhaupt möglichen Wörter. Ist C ein binärer Code, so ist die Zahl log_{2} |C| (und ähnlich log |𝔽_{2}^{n}|) als minimale Anzahl von Bits - etwa Ja-Nein-Entscheidungen - zu sehen, die man benötigt, um jedes beliebige Code-Wort aufzufinden. Der Repetition-Code hat z.B. eine Informationsrate von \frac{1}{3}.

Mit diesen Bezeichnungen läßt sich das Hauptproblem der Codierungstheorie etwas überspitzt wie folgt formulieren: Es sollen Codes gefunden werden, die die beiden inkompatiblen Ziele eines großen Minimalabstandes d und einer großen Informationsrate R erfüllen.

Der historisch wohl der erste der etwas subtileren und effizientesten Codes ist der Hammming-Code (benannt nach R. W. Hamming 1947), ein binärer Code der Länge 7. Er ist durch die Abbildung

𝔽_{2}^{4} → 𝔽_{2}^{7}
(x_{1}, …, x_{4}) ↦ (x_{1}, …, x_{7})

definiert. Dabei sind x_{1}, …, x_{4} beliebig gewählt und x_{5}, x_{6}, x_{7} sind durch die Summe dieser vier Elemente bestimmt (es sind sogenannte ”Prüfsummen“):

x_{5} = x_{1} + x_{3} + x_{4}, x_{6} = x_{1} + x_{2} + x_{4}, x_{7} = x_{1} + x_{2} + x_{3}.

Insgesamt gibt es 2^{4} = 16 Elemente in H, nämlich die Vektoren

0000 000 0001 110 0010 101 0011 011
0100 011 0101 101 0110 110 0111 000
1000 111 1001 001 1010 010 1011 100
1100 100 1101 010 1110 001 1111 111

Folgende Skizze veranschaulicht die Prüfsummen: in jedem der Kreise ist die Summe der Elemente gleich 0.

Dies ergibt 3 linear unabhängige Gleichungen in 𝔽_{7}^{2}; ihre Lösungsmenge, welche ein 4-dimensionaler linearer Unterraum von 𝔽_{7}^{2} ist, nennen wir H. H ist also die Lösungsmenge des homogenen Gleichungssystems mit Matrix

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

Der Hamming-Code ist daher ein linearer Code.

Ein Code C heißt linear, falls C ein linearer Unterraum von 𝔽_{q}^{n} ist.

Ist C ein linearer Code mit der Länge n, Dimension k und dem Minimalabstand d, so heißt C ein [n, k, d]-Code.

In einem linearen Code C ist der Minimalabstand d gleich dem Minimalgewicht w.

Betrachte die Vektoren von 𝔽_{q}^{n} als Spalten-Vektoren; dann ist ein linearer Code definiert durch eine exakte Sequenz:

0 ⟶ 𝔽_{q}^{k} ⟶^{A} 𝔽_{q}^{n} ⟶^{B} 𝔽_{q}^{n−k}⟶0,

wobei A und B lineare Abbildungen sind. Die Exaktheit der Sequenz ist äquivalent zu den drei Bedingungen: rang A = k, BA = 0 und rang B = n − k. Den Code C, der durch diese Sequenz definiert ist, erhält man auf zwei Wegen:

1. C = A(𝔽_{q}^{k}) ⊂ 𝔽_{q}^{n}. Die lineare Abbildung A ist durch eine (n × k)-Matrix A gegeben. Die Spalten von A bilden eine Basis von C. Gewöhnlich aber betrachtet man die transponierte Matrix G = ^{t}A von A; das ist eine (k × n)-Matrix G, deren Zeilen eine Basis von C bilden; sie heißt eine Generator-Matrix von C.

Da der Speicheraufwand für eine Generator-Matrix k Vektoren sind, bedeutet dies eine enorme Ersparnis im Vergleich zu den 2^{k} Vektoren, aus denen der Code besteht. Die Generator-Matrix des Hamming-Codes wäre die Matrix

G = ( \begin{matrix}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 & 1 & 1 & 0 \end{matrix} ) .

Die Zeilen dieser Matrix erzeugen also den Hamming-Code; hier ist es auch leicht einzusehen, dass der Hamming-Code ein 4-dimensionaler Unterraum von 𝔽_{2}^{7} ist.

2. C = ker B, und zwar genau dann, wenn für jedes x ∈ C Bx = 0 gilt. Die lineare Abbildung B ist durch eine (n − k) × n-Matrix B gegeben. Die Zeilen von B sind gerade die Gleichungen, die den Unterraum C (von 𝔽_{q}^{n}) definieren. Die Matrix B heißt die Kontroll-Matrix von C.

Um zu sehen, dass das Decodieren bei linearen Codes einfacher ist, als bei nicht-linearen Codes, ist der Begriff des ”Syndroms“ eines Vektors wichtig: Für jeden Vektor x ∈ 𝔽_{q}^{n} definieren wir sein Syndrom als Bx ∈ 𝔽_{q}^{n−k}. Ein Syndrom ist also ein binärer Vektor der Länge n − k.

Den Hamming-Code haben wir zum Beispiel durch das Syndrom gleich 0 bestimmt, d.h. bei der Multiplikation der Kontroll-Matrix B mit einem beliebigen Code-Wort erhielten wir jeweils ein 0-Tripel. Der Hamming-Code kann sogar einen Fehler t korrigieren; denn wegen d = 3 = 2t + 1 folgt, dass t = 1 ist.

Angenommen ein Code-Wort x ∈ H ethalte an der i-ten Stelle einen Fehler (das hieße dann, dass das Produkt Bx kein 0-Tripel sein könne). Um die Stelle, an der der Fehler aufgetreten ist, zu entdecken, sollte man bei der Decodierung wie folgt vorgehen: Die Spalten von B interpretieren wir als binäre Darstellung der Zahlen 1, …, 7 und ordnen die Spalten so an, dass die i-te Spalte s_{i} die Zahl i darstellt. Zum Beispiel ist die letzte Spalte diejenige, die nur aus Einsen besteht; Diese ”Permutationsmatrix“ nennen wir

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

Wird nun ein Wort x empfangen, das einen einzigen Fehler an der i-ten Stelle besitzt, so erhält man als Qσ(x) gerade die binäre Darstellung der Zahl σ(i), der Stelle also, an der der Fehler aufgetreten ist. Man beachte, dass die erhaltene Stelle σ(i) die Position im ”permutierten“ Code-Wort ist. Um aber die ”eigentliche“ Fehler-Stelle i ∈ x zu bekommen, identifiziere man den Tripel Qσ(x) als i-te Spalte (= i-te Stelle) von B.

Sei C ein linearer Code definiert durch eine exakte Sequenz wie auf der Seite zuvor. Aus der linearen Algebra ist uns bekannt, dass eine lineare Abbildung ϕ : V → W zwischen Vektorräumen V und W eine duale Abbildung ϕ^{∗} : V^{∗} → W^{∗} zwischen den entsprechenden dualen Vektorräumen V^{∗} und W^{∗} induziert. Sind V und W endlich dimensional, so können wir nach der Wahl der Basen sie mit ihren entsprechenden dualen Vektorräumen identifizieren. Daher induziert die vorhergehende Sequenz eine duale Sequenz

0 ⟶ 𝔽_{q}^{n−k} ⟶^{^{t}B} 𝔽_{q}^{n} ⟶^{^{t}A} 𝔽_{q}^{k}⟶0.

Die Bedingung BA = 0 ist äquvalent zu der Bedingung ^{t}A^{t}B = 0. Diese exakte Sequenz definiert den dualen Code C^{⊥}, d.h.

C^{⊥} := ^{t}B(𝔽_{q}^{n−k}).

Hat C die Dimension k, so hat C^{⊥} die Dimension n − k. Sei nun für alle x, y ∈ 𝔽_{q}^{n} ihr Skalar-Produkt definiert durch

⟨x, y⟩ = ∑_{i=1}^{n} x_{i}y_{i}.

Achtung: Das eben eingeführte Skalar-Produkt ist nicht mit dem Skalar-Produkt über dem Körper ℝ zu verwechseln! Hier arbeiten wir über dem Körper 𝔽_{2} und daher hat das Skalar-Produkt sehr merkwürdige Eigenschaften: C und C^{⊥} schneiden sich im allgemeinen keineswegs nur im Nullvektor; es ist sogar C ⊂ C^{⊥} erfüllt.

Lemma: C^{⊥} = {y ∈ 𝔽_{q}^{n} | ⟨x, y⟩ = 0 ∀ x ∈ C}.

Beweis: Nach Definition ist y ∈ C^{⊥} genau dann, wenn ^{t}Ay = 0. Zu zeigen: ^{t}Ay = 0 ⇔ ⟨^{t}Ay, z⟩ = 0 für alle z ∈ 𝔽_{q}^{n}. ”⇒“ Dies ist klar, denn ⟨0, z⟩ = 0 für alle z ∈ 𝔽_{q}^{n}. ”⇐“ Sei nun ⟨^{t}Ay, z⟩ = 0 für alle z ∈ 𝔽_{q}^{n}. Dieser Ausdruck läßt sich umformen: t(^{t}Ay) · z = ^{t}yAz = ^{t}y(Az) = ⟨y, Az⟩ = 0 für alle Az := x ∈ C. Daher ist y ∈ C^{⊥}, und zwar genau dann, wenn ⟨x, y⟩ = 0 für alle x ∈ C = A(𝔽_{k}^{n}).

□

Ein linearer Code heißt selbst-dual genau dann, wenn C = C^{⊥} gilt. Man nehme zur Kenntnis, dass bei dim C +dim C^{⊥} = n C = C^{⊥} ist. Dies impliziert, dass n gerade, dim C = \frac{n}{2} und C ⊂ C^{⊥} ist. Es gilt also: C ⊂ C^{⊥} ⇔ ⟨x, y⟩ = 0 für alle x, y ∈ C.

Ein binärer Code heißt doppelt gerade, wenn die Gewichte aller Code-Wörter durch 4 teilbar sind. Ein doppelt gerader Code C genügt C ⊂ C^{⊥} genau dann, wenn über ℤ gilt:

⟨x, y⟩ = \frac{1}{2}(⟨x + y, x + y⟩ − ⟨x, x⟩ − ⟨y, y⟩).

Nun zürück zum Hamming-Code: Man sieht leicht (siehe Tabelle S. 3), dass das Minimal-Gewicht des Hamming-Codes 4 ist; daher handelt es sich um einen [7, 4, 3]-Code. Er enthält ein Wort vom Gewicht 0, sieben vom Gewicht 3, sieben vom Gewicht 4 und ein Wort vom Gewicht 7.

Der zu H duale Code H^{⊥} ist von den Zeilen von B erzeugte Unterraum von 𝔽_{2}^{4}; die Zeilen der Matrix B bilden also die Basis des dualen CodesH^{⊥} von H. Der duale Code H^{⊥} besteht aus folgenden Code-Wörtern:

0000 000 1011 100 1101 010 1110 001 0110 110 0101 110 0011 011 1000 111

Die Informationsrate des Hamming-Codes ist R = \frac{4}{7}. Würde man den Repetition-Code zur Übermittlung von 4-Bit-Wörtern an Stelle des Hamming-Code verwenden, so müßte man jedes 4-Bit-Wort dreimal wiederholen, um auf einen Minimalabstand von 3 zu kommen, um einen Fehler korrigieren zu können. Die Informationsrate dieses Repetition-Codes wäre \frac{4}{12}. Die Informatiosrate des Hamming-Codes ist demnach \frac{12}{7} ≈ 1, 71-mal so groß wie die des Repetition-Codes; dies bedeutet, dass der Hamming-Abstand in der gleichen Zeit etwa 71 % mehr Information übermitteln kann als der Repetition-Code.

Der Hamming-Code ist nicht selbst-dual, er kann aber zu einem selbst-dualen Code der Länge 8 erweitert werden; einen erweiterten Code bekommen wir allgemein wie folgt: Sei C ⊂ 𝔽_{2}^{n}, ein binärer Code der Länge n. Betrachte die Abbildung

𝔽_{2}^{n} → 𝔽_{2}^{n+1}
(x_{1}, …, x_{n}) ↦ (x_{1}, …, x_{n+1}).

Der Code C̃ := I(C) heißt der erweiterte Code. Das bedeutet, dass wir zum Code C noch eine Kontroll-Stelle hinzugefügt haben.

Der erweiterte Code H̃ := I(H) heißt der erweiterte Hamming-Code. Wir erhalten folgende Code-Wörter für H̃:

0000 0000 0001 1101 0010 1011 0011 0110
0100 0111 0101 1010 0110 1100 0111 0001
1000 1110 1001 0011 1010 0101 1011 1000
1100 1001 1101 0100 1110 0010 1111 1111

Dies ist ein [8, 4, 4]-Code mit einem Code-Wort vom Gewicht 0, vierzehn vom Gewicht 4 und einem vom Gewicht 8. H̃ ist sowohl ein doppelt gerader, als auch ein selbst-dualer Code.

Literatur

[1] W. Ebeling. Lattices and Codes. A course partially based on lectures by F. Hirzebruch.Vieweg Verlag.

[2] A. Beutelspacher. Lineare Algebra. Eine Einführung in die Wissenschaft der Vektoren, Abbildungen und Matrizen 2., durchgesehene Auflage 1995

[3] F. Hirzebruch. Codierungstheorie und ihre Beziehung zu Geometrie und Zahlentheorie. In Vorträge Rheinisch-Westfälische Akademie der Wissenschaften, N 370, Opladen, 1989. Westdeutscher Verlag.

[4] C. M. Ringel. Leitfaden: Höhere Lineare Algebra (WS 2000/01).