5.2.1 Begriffe

Als Hamming-Abstand zweier Codewörter gleicher Länge bezeichnet man die Anzahl der Stellen, an denen sich die Wörter unterscheiden. Der Hammingabstand eines Codewortes vom Null-Wort heißt Hamming-Gewicht.

Zur Fehlererkennung und zur Fehlerkorrektur ist eine Kodierung der Information erforderlich, die Redundanz enthält, also mehr Bits zur Repräsentation verwendet als zur reinen Speicherung erforderlich. Dadurch gelingt es, die zulässigen Codewörter so zu definieren, dass sie paarweise wenigstens den Hamming-Abstand D haben. D heißt Minimalabstand des Codes. Bei Benutzung eines Codes mit dem Minimalabstand D kann man ein empfangenes Wort mit bis zu D-1 fehlerhaften Stellen als unbrauchbar erkennen oder ein Wort mit bis zu floor((D-1)/2) fehlerhaften Stellen korrigieren. Entscheidet man sich zur Korrektur, so ist die Fehlererkennung eingeschränkt oder ganz verloren.

Die Benutzung einer Kanalkodierung, um fehlerhafte Zeichen am Empfangsort korrigieren zu können, bezeichnet man als Vorwärts-Korrektur (Forward Error Correction, FEC). Wird dagegen der Code zur Fehlererkennung benutzt, um eine Wiederholung der Übertragung anzufordern, so bezeichnet man dies als ARQ (Automated Repeat Request). Häufig werden beide Verfahren kombiniert. ARQ ist jedoch nicht einsetzbar bei großen Entfernungen (inteplanetare Raumsonden) und problematisch bei Datenübertragung in Realzeit (z.B.Video).

Es gibt eine Reihe von Verfahren zur Konstruktion von Codes zur Fehlererkennung und -Korrektur, jedoch keine einheitliche Theorie, aus der sich alle guten Codes ergeben. Gute Codes muss man finden. Zur Suche benutzt man heute den Computer.

Zunächst wollen wir eine Klassifikation von Codes vornehmen:

(1) Block-Code vs. Faltungscode
Man unterscheidet Block-Codes gegenüber Faltungscodes. Bei Block-Codes werden jeweils k Informationsbits in ein Codewort von n Bits kodiert. Im Falle von FaltungsCodes wird dagegen ein kontinuierlicher Bitstrom in einen Codebitstrom höherer Bitrate kodiert.

(2) Lineare , modifizierte und nichtlineare Codes Ein linearer (n,k)-Block-Code über GF(q) ist ein k-dimensionaler Unterraum des GF(q)ⁿ . GF(q) ist der endliche Körper mit q Elementen. q ist p^m , wo p Primzahl ist und m eine natürliche Zahl.
Beispiel: p = 2 ; m = 1 ; n = 3 ; k = 1 .
Der Code ist ein eindimensionaler Unterraum des GF(2)³ . Er enthält die Codewörter [0 0 0] und [1 1 1] . Alle anderen Elemente von GF(2)³ sind Nicht-Codewörter. Wenn man eine oder mehrere Stellen des Codewortes systematisch verändert, im Falle des GF(2) also invertiert, so ist der Code kein linearer Raum mehr, obwohl er alle seine Eigenschaften hat. Man nennt dies einen modifizierten Code. Er hat den Vorteil, dass Nullvektor und Einsvektor nicht mehr zum Code gehören und damit die relativ häufigen Fehler, dass nur Nullen oder nur Einsen gesendet werden, sofort als Fehler erkennbar sind.
Ist der Code weder linear noch ein modifizierter linearer, so ist er nichtlinear. Faltungscodes sind im Prinzip linear, passen jedoch wegen der unendlichen Dimensionen nicht in die obige Beschreibung.

(3) Systematischer Code
Ein Code heißt systematisch, wenn sich die zu kodierende Information direkt im Codewort wiederfindet.

(4) Zyklischer Code
Ein Block-Code heißt zyklisch, wenn mit jedem Codewort auch sämtliche zyklischen Verschiebungen (Rotationen) des Codewortes zum Code gehören. Lineare zyklische Codes sind bei serieller Übertragung von Vorteil, weil sie Fehlerbündel besser erkennen bzw. korrigieren können.

(5) Codes zur Erkennung und Korrektur von Fehlerbündeln Ein Fehlerbündel (Burst) ist eine Sequenz von b Bits, in der gehäuft Fehler auftreten (erstes und letztes sowie möglicherweise dazwischen liegende Bits sind fehlerhaft). Es gibt Codes, die speziell auf diesen Fall zugeschnitten sind.