Rechnernetze

Fehlerkorrigierende Codes

Wenn der Empfänger aus den empfangenen Daten, trotz möglicher Verfälschung, auf die originale Nachricht schließen kann, so sprechen wir von fehlerkorrigierenden Codes. Da grundsätzlich jede Nachricht beliebig verfälscht sein könnte, kann nur mit einer gewissen Wahrscheinlichkeit eine (richtige) Korrektur durchgeführt werden, d.h. die vermeintliche Korrektur kann mit einer gewissen Chance zu einem weiteren Fehler führen. Diese Wahrscheinlichkeit hängt natürlich auch von der Wahrscheinlichkeit des Auftretens bestimmter Fehlerarten ab.

Wir fassen für die folgenden Betrachtungen noch einmal die bereits früher eingeführte Terminologie zusammen. Soll Information (information) von einem Sender zu einem Empfänger übertragen werden, so wird dazu eine Nachricht (message) geschickt; unterschiedliche Information wird in der Regel durch verschiedene Nachrichten beschrieben. Die Darstellung einer Nachricht wird auch als Kodierung (coding) der Nachricht bezeichnet. Die Form, in der wir eine Nachricht schreiben, wird daher auch als Codewort bezeichnet.

Die Darstellung eines Codeworts wird als Zeichenwert bezeichnet. Die physikalischen Größen, in denen die Zeichenwerte auf dem Übertragungskanal dargestellt werden, nennen wir Signalwerte. In den folgenden Untersuchungen gehen wir davon aus, dass die Codewörter einer Nachricht als Zeichenwerte vorliegen; die physikalische Darstellung soll hier nicht berücksichtigt werden. Trifft die Nachricht (bzw. die Codewörter) unverfälscht beim Empfänger ein, so kann dieser daraus die übermittelte Nachricht wieder herleiten.

Die Menge der Codewörter (die in einer bestimmten Anwendung vorkommen) wird als Alphabet bezeichnet. Die Zuordnung zwischen Nachricht und Codewörtern wird in einer Codetabelle vorgenommen. Codetabellen sind z.B. die internationalen Alphabete Nr. 2 (Telex) oder Nr. 5 (ASCII).

Ein Code kann außer der Nachricht, welche die Information repräsentiert, auch noch weitere Information tragen. Diese Information wird als Redundanz (redundancy) bezeichnet. Wir nennen im folgenden die zusätzliche Information, die zur Fehlererkennung dient, Prüfinformation (auch Prüfdaten, Prüfbytes usw.). Da die Prüfdaten stets über den gleichen Kanal geschickt werden müssen wie die Nutzdaten, können auch diese verfälscht beim Empfänger ankommen. Die Wahrscheinlichkeit eines Fehlers in einem Block errechnet sich stets aus der Wahrscheinlichkeit eines Fehlers entweder in den Nutzdaten oder in der Prüfinformation oder in beiden. Dieses wurde in den Beispielen im letzten Abschnitt in der Regel nicht berücksichtigt, da es die dort errechneten Wahrscheinlichkeiten kaum verändert hätte!