Fehlererkennung und Fehlerkorrektur

1. Die Fehlererkennung prüft lediglich, ob ein Übertragungsfehler aufgetreten ist. Ist dies der Fall, so wird eine Fehlermeldung ausgegeben.
2. Die Fehlerkorrektur geht noch einen Schritt weiter. Sie versucht, nachdem ein Fehler festgestellt worden ist, diesen zu beheben.

Das gesamte Kommunikationssystem

Sei p die Wahrscheinlichkeit, dass ein Bit falsch übertragen wird. Man kann im allgemeinen annehmen, dass gilt: 0 <= p < 0,5. Die Wahrscheinlichkeit, dass bei der Übertragung eines Wortes der Länge 5 kein Fehler vorkommt, ist Prob{e=00000}=(1-p)⁵. Wird das zweite Bit falsch übertragen, so gilt Prob{e=01000}=p*(1-p)⁴. Werden das erste und vierte Bit falsch übertragen, so gilt Prob{e=10010}=p²*(1-p)³. Im Allgemeinen also bei einem Fehlervektor v des Gewichts a: Prob{e=v}=p^a*(1-p)^n-a. Unter der realistischen Annahme p < 0,5 gelangt man zu der Beziehung

(1-p)⁵ > p*(1-p)⁴ > p²*(1-p)³ > ... > p⁵.

Aus diesen Ungleichungen kann man folgern, dass ein bestimmter Fehlervektor vom Gewicht 1 wahrscheinlicher ist als ein bestimmter Fehlervektor vom Gewicht 2 und so weiter. Das bedeutet speziell für den Dekoder, dass er sich das Codewort heraussucht, welches möglichst nahe zu dem fehlerhaften empfangenen Wort bezüglich des Hamming-Abstandes ist, oder anders ausgedrückt, er sucht sich jenen Fehlervektor mit minimalem Gewicht.

Die Frage ist nun, wieviele Fehler der Dekoder korrigieren kann. Diese Anzahl ist abhängig von der minimalen Distanz der Codewörter eines Codes: Ein Code mit dem Minimalabstand d kann maximal immer [(d-1)/2] Fehler simultan korrigieren. Ist d gerade, so kann er maximal immer d/2 Fehler erkennen. Dies kann man sich durch folgendes Modell gut veranschaulichen.

Code mit Mimimalabstand 3

Code mit Minimalabstand 4

Die ganze Zeit haben wir angenommen, dass der Dekoder immer versucht, zu einem empfangenen Wort das am nächsten gelegene Codewort zu finden. Diese Dekodierungsart ist sinnvoll bei Nachrichten, die einmalig empfangen werden, wie z.B. Aufzeichnungen vom Mars etc. Man möchte eben so viel wie möglich aus einer empfangenen Nachricht herausholen. In vielen Fällen ist es jedoch sinnvoll, sich auf eine gewisse Anzahl c an Fehlern zu beschränken, welche auch korrigiert werden, und bei allen Fehler, deren Gewicht >c ist, die Nachricht abzuweisen bzw. um erneutes Übertragen zu bitten. Diese Dekodierungsart nennt man unvollständiges Dekodieren. Eine extreme Form hiervon ist die Fehlererkennung, welche gar keine Fehler korrigiert sondern nur erkennt, d.h. c=0.