12.1 Einführung und Definitionen
In diesem Abschnitt erklären wir einige grundlegende Konzepte der Kodierungstheorie, um zu illustrieren, wie der Begriff des endlichen Körpers und speziell Methoden der linearen Algebra über endlichen Körpern dabei helfen, ein »real world problem« einer mathematischen Behandlung zugänglich zu machen.
Das Grundproblem der Kodierungstheorie ist, eine Nachricht effizient über einen Kommunikationskanal (ein Netzwerkkabel, eine WLAN-Verbindung, Speichern und Auslesen von Daten auf einer Festplatte, CD etc.) zu übermitteln, der die übertragenen Nachrichten mit einer gewissen Wahrscheinlichkeit verfälscht. Mit anderen Worten: Auch wenn ein Kratzer auf der CD ist, soll es möglich sein, die gewünschten Informationen zu extrahieren. Eine naive Möglichkeit wäre, zum Beispiel die Zahl \(321\, 654\, 987\) in der Form
zu speichern, d.h. die Information wird dreimal wiederholt. Wenn eine dieser \(27\) Ziffern geändert wird, kann man durch Vergleich der drei Kopien immer noch herausfinden, was die ursprüngliche Zahl war. Allerdings braucht man mit dieser Methode erheblich mehr Speicherkapazität (oder: eine Übertragung der Nachricht würde entsprechend länger dauern), nämlich dreimal soviel, wie für die eigentliche Nachricht.
In der Kodierungstheorie werden Möglichkeiten gesucht (und gefunden und untersucht), dasselbe Ziel zu erreichen und die Ursprungsnachricht möglichst wenig zu verlängern. Dieses Ziel ist nicht zu verwechseln mit der Verschlüsselungstheorie oder Kryptographie, in der man versucht, Nachrichten so umzuschreiben (zu verschlüsseln), dass sie einem Außenstehenden nicht verständlich sind, aber vom Adressaten wieder lesbar gemacht (entschlüsselt) werden können. Auch dabei gibt es interessante mathematische Fragen, die jedoch hier nicht das Thema sind; siehe aber Abschnitt 12.5 für eine Verbindung zwischen diesen beiden Themen.
Wir machen zwei Grundannahmen: Erstens: Alle Codewörter werden mit der gleichen Wahrscheinlichkeit als Nachricht verschickt. (Sonst wäre es vielleicht besser, den Code auf die häufiger verschickten Nachrichten hin zu optimieren.) Zweitens setzen wir voraus, dass für jedes gesendete Zeichen auch genau ein Zeichen beim Empfänger ankommt (möglicherweise jedoch ein anderes) und dass es für \(m {\lt} n\) wahrscheinlicher ist, dass \(m\) (also weniger) Fehler bei der Übertragung passieren, als dass \(n\) Fehler auftreten. (Es wären auch Kommunikationskanäle denkbar, die immer direkt mehrere Zeichen verändern, wo aber nur sehr selten einzelne Fehler auftreten.) In sehr vielen Praxisanwendungen sind das realistische Voraussetzungen. Man kann die Theorie erweitern auf Situationen, wo diese Annahmen verletzt sind, das wollen wir aber an dieser Stelle nicht tun.
Ein einfaches Beispiel, das das grundlegende Prinzip illustriert, ist die Verwendung eines Paritätsbits: Die zu sendende Nachricht wird in Pakete von »Wörtern« einer festen Länge (zum Beispiel sieben Zeichen), die jeweils \(0\) oder \(1\) sein können (man spricht von \(7\) Bits). Zusätzlich wird immer ein weiteres Zeichen hinzugefügt, und zwar eine \(0\) oder \(1\), so dass von den acht Bits eine gerade Anzahl gleich \(1\) ist.
Wenn bei der Übertragung genau ein Bit falsch übertragen wird, hat das empfangene Wort eine ungerade Anzahl von Einsen. Die Empfänger∗in kann den Übertragungsfehler also feststellen (allerdings nicht herausfinden, was die ursprüngliche Nachricht war).
Wenn über den Kommunikationskanal die Symbole \(0\) oder \(1\) übertragen werden können, und die Wahrscheinlichkeit der korrekten Übertragung für jedes Zeichen durch dieselbe Zahl \(p\), \(0 \le p \le 1\) gegeben ist (zum Beispiel bedeutet \(p=0,85\), dass in \(85\% \) der Fälle das gesendete Zeichen richtig übertragen wird), dann gilt der Satz von Shannon ( [ vL ] Theorem 2.2.3), der umgangssprachlich ausgedrückt Folgendes besagt (die präzise Formulierung dort beinhaltet auch eine Aussage zur Übertragungsrate):
Sei \(p\ne \frac12\). Für jede vorgegebene positive (kleine) Wahrscheinlichkeit \(\varepsilon \) gibt es Codes, bei denen die Wahrscheinlichkeit, ein gesendetes Codewort falsch zu dekodieren, kleiner als \(\varepsilon \) ist. (Wichtig ist dabei, dass man sich erlaubt, ausreichend lange Codewörter zu benutzen. Je kleiner \(\varepsilon \) ist, desto längere Codewörter wird man in der Regel benötigen.)
Nachrichten zu betrachen, die als eine Folge von Nullen und Einsen geschrieben werden, ist oft naheliegend. Unter anderem, weil auch ein Computer seine Daten so abspeichert. Natürliche Zahlen haben die Binärdarstellung, die aus Nullen und Einsen besteht; Buchstaben können in Zahlen umgeschrieben und dann ebenso in Binärdarstellung geschrieben werden, usw. Zerlegt man die Nachricht in Abschnitte der Länge \(m\), so kann man jeden solchen Abschnitt als ein Element von \(\mathbb F_2^m\) betrachten.
Vom mathematischen Aufwand können wir aber an dieser Stelle statt \(\mathbb F_2\) irgendeinen endlichen Körper betrachten und wollen das dementsprechend tun. (Sie können aber das Kapital auch einfach mit \(q=2\) weiterlesen.)
Sei \(K\) ein endlicher Körper, und sei \(q\) die Anzahl der Elemente von \(K\). Man kann zeigen (Ergänzung 6.57), dass \(q\) eine Primzahlpotenz sein muss, etwa \(q=p^d\) mit einer Primzahl \(p\). Dann ist \(p\) die Charakteristik von \(K\), also die kleinste positive Zahl, so dass \(1 + \cdots + 1 = 0\) (mit \(p\) Summanden auf der linken Seite), vergleiche Abschnitt 4.2.2. Wir setzen wie oben voraus, dass alle Nachrichten in Abschnitte von \(k\)-Tupeln in \(K\) zerteilt werden, also als eine Folge von Vektoren in \(K^k\). Sei \(N\subseteq K^k\) die Menge aller »Wörter«, also aller Elemente von \(K^k\), die tatsächlich als Nachrichten(-teile) verwendet werden sollen.
Das Grundprinzip der Kodierungstheorie ist nun, die Nachrichtenwörter vor der Übertragung durch andere Wörter zu ersetzen und damit auf geschickte Weise eine Redundanz hinuzufügen, die es der Empfänger∗in ermöglicht, Übertragungsfehler festzustellen und bestenfalls automatisch zu korrigieren. Dazu suchen wir eine injektive Abbildung \(c\colon N\to K^n\) von der Menge aller Nachrichtenwörter nach \(K^n\) (für ein geeignetes \(n\), das in der Regel größer sein wird als \(m\)). Statt einer Nachricht \(v\in K^k\) wird dann \(c(v)\) übertragen. Entscheidend ist dabei, eine geeignete Wahl für die Abbildung \(c\) zu treffen, d.h. zu entscheiden, welche der \(q^n\) Elemente von \(K^n\) in ihrem Bild liegen und daher tatsächlich verwendet werden, damit man auch bei (wenigen) Fehlern in der Übertragung noch auf den gesendeten Vektor zurückschließen kann. Das Bild der Abbildung \(c\) nennt man den verwendeten Code; \(c\) ist die Kodierungsfunktion. Für unsere weiteren Betrachtungen werden \(N\) und \(c\) keine große Rolle spielen. Wir konzentrieren uns auf das Bild der Abbildung \(c\) und machen die folgende Definition:
Wie in der Kodierungstheorie üblich, wollen wir in diesem Kapitel die Elemente von \(K^n\) als Zeilenvektoren verstehen, wir identifizieren also \(K^n = M_{1\times n}(K)\).
Um der Empfänger∗in einer Nachricht ein Verfahren an die Hand zu geben, um Übertragungsfehler festzustellen und sie gegebenenfalls korrigieren zu können, definiert man
Seien \(K\) ein endlicher Körper und \(C\) ein Code der Länge \(n\) über \(K\).
Für \(v = (v_1,\dots , v_n), w=(w_1, \dots , w_n)\in K^n\) ist die Hamming-Distanz zwischen \(v\) und \(w\) definiert als
\[ d(v, w) = \# \{ i;\ v_i\ne w_i \} , \]also die Anzahl der Einträge der Vektoren \(v\) und \(w\), die sich unterscheiden.
Die (minimale) Hamming-Distanz von \(C\) ist
\[ d(C) = \min \{ d(v, w);\ v, w\in C,\ v\ne w\} . \]
Es ist klar, dass man keine vernünftigen Aussagen treffen kann, wenn der Kommunikationskanal zu viele Einträge der gesendeten Nachricht verfälscht. Der Begriff der Hamming-Distanz ermöglicht uns eine präzise Aussage (Satz 12.5), mit wie vielen Fehler in einer Nachricht es noch möglich ist festzustellen, dass ein Übertragungsfehler aufgetreten sein muss, und bei wie vielen Fehlern sogar die ursprüngliche Nachricht gefunden werden kann.
Der Code aus Beispiel 12.1 hat die minimale Hamming-Distanz \(2\): Es gibt zwar Codewörter, die sich an nur zwei Stellen unterscheiden. Die Paritätsbedingung, dass die Anzahl der Einsen in jedem Codewort gerade sein muss, bewirkt aber, dass es keine zwei Codewörter mit Hamming-Distanz \(1\) geben kann.
Der folgende Code \(C\subset \mathbb F_2^7\) hat Hamming-Distanz \(3\), wie man leicht überprüft. Wir schreiben die Zeilenvektoren hier ohne Kommata, um es etwas übersichtlicher zu machen.
Wenn bei der Übertragung eines der Wörter aus \(C\) ein oder zwei Einträge falsch übertragen werden, kommt bei der Empfänger∗in ein Wort an, das kein Element von \(C\) ist. Dieser Übertragungsfehler lässt sich also erkennen. Wenn genau ein Eintrag falsch übertragen wird, dann lässt sich durch Vergleich mit den Elementen von \(C\) auch feststellen, welches Wort übertragen wurde. Der Code kann also \(1\) Fehler »korrigieren«. Siehe Satz 12.5.
Es gibt Teilmengen \(C^\prime \subset \mathbb F_2^7\), die \(C\) als echte Teilmenge enthalten, und auch Hamming-Distanz \(3\) haben (und daher »bessere« Codes sind). Versuchen Sie, ein möglichst großes \(C^\prime \) zu finden! Siehe auch Abschnitt 12.4.
Die Funktion \(d\colon K^n\times K^n\to \mathbb Z_{\ge 0}\) hat die Eigenschaften einer Metrik (oder Distanzfunktion), d.h.
Es gilt \(d(v, w)= 0\) genau dann, wenn \(v=w\),
Es gilt \(d(v, w) = d(w, v)\) für alle \(v, w\in K^n\),
Es gilt die Dreiecksungleichung
\[ d(u, v) + d(v, w) \ge d(u, w)\qquad \text{für alle}\ u, v, w\in K^n. \]
Alle drei Eigenschaften sind leicht einzusehen.
Im folgenden Satz bezeichnet \(\lceil - \rceil \) die Aufrundungsfunktion, manchmal auch die obere Gaußklammer genannt: Für eine reelle Zahl \(x\) ist \(\lceil x\rceil \) die kleinste ganze Zahl, die \(\ge x\) ist. Zum Beispiel ist \(\lceil x\rceil = x\) für alle \(x\in \mathbb Z\) und \(\lceil \frac12\rceil = 1\). Wie man leicht sieht, gilt \(2\lceil \frac d2\rceil \le d+1\) für jede ganze Zahl \(d\). Das werden wir im Beweis benutzen.
Sei \(C\) ein Code der Länge \(n\) über \(K\). Wir betrachten das Szenario, dass die Absender∗in eine Nachricht \(v\in K^n\) verschickt. Den Vektor, den die Empfänger∗in erhält, nennen wir \(w\).
Wenn bei der Übertragung höchstens \(d(C)-1\) Einträge des Vektors \(v\) falsch übertragen werden, dann gilt: Ist \(w\in C\), so ist \(w = v\). Ist \(w\not \in C\), so muss es Übertragungsfehler gegeben haben. Wir sagen, dass der Code \(C\) bis zu \(d(C)-1\) Übertragungsfehler erkennen kann.
Wenn bei der Übertragung höchstens \(\lceil d(C)/2\rceil - 1\) Einträge des Vektors \(v\) falsch übertragen werden, dann ist \(v\) das eindeutig bestimmte Element von \(C\) mit \(d(v, w) \le \rceil d(C)/2\rceil - 1\). Wir können also die Originalnachricht aus \(w\) rekonstruieren. Wir sagen, dass der Code \(C\) bis zu \(\lceil d(C)/2\rceil -1\) Übertragungsfehler erkennen kann.
zu (1). Da höchstens \(d(C)-1\) Einträge falsch übertragen wurden, gilt \(d(v, w) {\lt} d(C)\). Ist \(w\in C\), so folgt daraus \(v=w\) nach Definition von \(d(C)\) als Minimum der Distanzen von verschiedenen Elementen aus \(C\).
Ist \(w\not \in C\), dann müssen natürlich Übertragungsfehler aufgetreten sein, da alle Nachrichten Elemente aus \(C\) sind.
zu (2). Es ist klar, dass die Voraussetzung \(d(v, w) \le \lceil d(C)/2\rceil - 1\) impliziert. Es ist nur noch zu zeigen, dass es kein Element \(v^\prime \in C\), \(v\ne v^\prime \), geben kann mit \(d(v^\prime , w) \le \lceil d(C)/2\rceil - 1\). In diesem Fall wäre aber
ein Widerspruch. Hier haben wir benutzt, dass die Hamming-Distanz die Dreiecksungleichung erfüllt und symmetrisch ist.
Bei der Wahl eines Codes würden wir also prinzipiell \(C\) gerne so wählen, dass \(\# C\) groß, \(d(C)\) groß und \(n\) klein sind. Außerdem ist es für die praktische Anwendung wichtig, dass die Funktionen Kodieren einer Nachricht und Dekodieren einer Nachricht möglichst einfach sind. Zum Beispiel wäre es praktisch, das De-/Kodieren einer Nachricht durch eine einfache Rechnung durchzuführen (im Vergleich dazu, dass man ein riesiges »Wörterbuch« speichern müsste, in dem jede Übersetzung nachgeschlagen werden muss).