Fehlerkorrigierende Codes

(nach: Fehlererkennende Codes, 13. Algorithmus der Woche, http://www-i1.informatik.rwth-aachen.de/~algorithmus/algo13.php)

ISBN ist ein Beispiel eines fehlererkennenden Codes. Diese dienen dazu, wie der Name schon sagt, um zu erkennen, dass bei der Übertragung von Daten Fehler entstanden sind. Dazu wird der eigentlichen Information (Nutzdaten) zusätzliche, eigentlich überflüssige Information (Redundanz) hinzugefügt, die dem Empfänger zur Bestimmung von Fehlern und Fehlerpositionen dient.

Fehlerkorrigierende Codes arbeiten nach dem gleichen Prinzip wie fehlererkennende, aber sie gestatten es zusätzlich einige Fehler zu beheben. Die Ergänzung der zu übertragenden Daten allein um eine Prüfsumme genügt nicht, um Fehlerkorrektur zu ermöglichen. Dazu ist eine geschicktere Codierung nötig. Wir können uns die Funktionsweise an folgendem Beispiel verdeutlichen.
Angenommen wir wollen einen binären Text (über 0 und 1) übertragen, also z.B. folgende Zeichenkette: 0110. Anstelle im Klartext zu übertragen, codieren wir wie folgt:

Aus dem Klartext 0110 wird also 000111111000. Der Empfänger bildet dann gemäss folgender Tabelle aus dem (eventuell gestörten) empfangenen Code wieder einen Klartext. Dieser Schritt heißt Decodierung.

Diese Decodierungstabelle hat die Eigenschaft, dass der richtige Klartext bestimmt wird, obwohl eventuell einzelne Bits des Codes falsch übertragen wurden. Angenommen, bei der Übertragung einer codierten Null 000 wird ein einzelnes Bit falsch übertragen, also z.B. 001 anstelle 000. Gemäß obiger Decodiertabelle übersetzen wir 001 trotzdem zu einer 0. Mit diesem Verfahren erreichen wir also einen gewissen Schutz vor Übertragungsfehlern, aber erkaufen dies durch erhöhten Übertragungsaufwand; schliesslich übertragen wir die dreifache Anzahl Bits. Eine etwas geschicktere Codierung erzielen wir, wenn wir die Bits nicht einzeln codieren, sondern immer mehrere zu einer Gruppe zusammenfassen:

Als Decodiertabelle verwenden wir diese hier:

Auch diese Codierung hat die Eigenschaft, dass einzelne Bitfehler korrigiert werden können, aber das Verhältnis der Klartextlänge zur Codelänge ist 2/5 anstelle 1/3 wie bei der vorangegangenen Lösung. Dieses Verfahren ist damit (etwas) effizienter. Es ist natürlich wünschenswert, dass nicht nur einzelne Fehler erkannt und korrigiert werden können, sondern mehrere. Dies kann durch die Einführung zusätzlicher redundanter Bits und eine geschickte Codierung erreicht werden. Fehlerkorrigierende Codes begegnen uns übrigens im täglichen Leben. Beispielsweise wird ein solches Verfahren benutzt, um Fehler, die beim Lesen einer CD auftreten, zu korrigieren und so den Hörgenuss zu steigern. Dabei werden bei der Codierung, im Prinzip wie oben, aus dem laufenden Datenstrom jeweils 192 Bits zusammengefasst und mit 32 Fehlerkorrekturbits ausgestattet. Dieser Block wird noch geschickt weiter codiert, was wir aber hier nicht beschreiben wollen. Ein Kratzer auf der CD kann ohne weiteres die Bits eines halben Blocks beschädigen, aber durch die Codierung kann die verkratzte CD trotzdem fehlerfrei wiedergegeben werden.