Codes

Die folgenden Grundbegriffe sind der Darstellung in Ebeling [Eb] entnommen. (Verwiesen sei dabei aber auch auf die Bücher [Wi] und [LG].) Dabei wird angeknüpft an die in 2.1 eingeführten endlichen Körper , deren Elemente jetzt der Einfachheit halber ohne die früher gebrauchten Querstriche geschrieben werden, also

Ein (linearer) Kode der Länge n ist dann einfach ein linearer Unterraum C von . Für p=2 heißt der Kode binär, für p=3 ternär usw. Ein Element von C wird Kodewort genannt. Der Kodierungsprozeß ist eine lineare Abbildung

Ein Buchstabe oder allgemeiner ein Teil des Klartextes der Nachricht a wird also zunächst in ein k-tupel v aus Elementen von übertragen (durch eine bijektive Vorschrift) und dann durch f injektiv auf ein n-tupel in C. Ein einfaches Beispiel ist hier die Abbildung

Falls nun etwa bei der Übermittelung zu wird, kann der Empfänger vernünftigerweise vermuten, daß die übertragene Botschaft sein sollte. Daß dies hier auf eine Verdreifachung der ursprünglichen Nachricht hinausläuft und damit zu einer unangenehm großen Verteuerung, ist offenbar und wird durch folgende Begriffsbildungen quantifiziert und (zum Teil) behoben:

Es bezeichne für einen linearen Unterraum

, ein ,,Codewort``

w(x):= die Anzahl der Komponenten , das ,,Gewicht`` von x

d(x,y):=w(x-y) den ``Hamming-Abstand'' von , den ``Minimalabstand'',

die Anzahl der Elemente von C und R=k/n die ``Informationsrate''. C heißt dann ein [n,k,d]-Code.

Beispiel: Der oben angegebene Code ist ein [3,1,3]-Code mit Informationsrate R=1/3. Bei diesem Beispiel kann schon mal die allgemeine Aussage nachgeprüft werden, daß ein Code mit Minimalabstand d t Fehler korrigieren kann mit t fixiert durch

Daraus entsteht nun leicht die Aufgabe, Codes mit möglichst großem Minimalabstand d aber (aus Kostengründen) möglichst kleiner Wortlänge zu suchen, also genauer mit möglichst großer Informationsrate R.

Nach seinem Initiator heißt nun der folgende binäre [7,4,3]-Code Hamming-Code . Es sei

wobei zu vorgegebenen die Elemente so zu bestimmen sind, daß die Summe der Elemente in jedem Kreis gleich 0 ist.

hat dann die Informationsrate R=4/7. Die zur Konstruktion von verwandte Bedingung kann auch mit Hilfe der Inzidenzmatrix des gedeutet werden (s.[Eb] S.10).

wird zu dem ``erweiterten Hamming-Code'' ausgedehnt mit Hilfe der Abbildung

Dies ist dann ein [8,4,4]-Code.