Direkt zur Hauptnavigation springen Direkt zum Inhalt springen Jump to sub navigation

Fehlerkorrigierende Codes

Fehlerkorrigierende Codes

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:

KlartextCodierung
0000
1111


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.

Empfangener CodeKlartext
000, 001, 010, 100  0
111, 110, 101, 011   1


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:

KlartextCodierung
0000000
0100111
1011100
1111011


Als Decodiertabelle verwenden wir diese hier:

    

Empfangener CodeKlartext
00000, 10000, 01000, 00100, 00010, 0000100
00111, 10111, 01111, 00011, 00101, 00110 01
11100, 01100, 10100, 11000, 11110, 1110110
11011, 01011, 10011, 11111, 11001, 1101011


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.

 

Redaktionell verantwortlich: