Hamming Code

Wie findet man Fehler in Daten? Kann man sie auch korrigieren? Eine einfache Parität zur Erkennung eines Fehlers ist ein Anfang. Aber da ist mehr möglich:

Richard Wesley Hamming hatte eine Idee, wie man eine Prüfung von binären Daten durch eine Parität noch verbessern kann, sodass damit nicht nur ein Fehler festgestellt, sondern sogar korrigiert werden kann. Es handelt sich hier um eine Vorwärtskorrektur oder englisch forward error correction FEC. Der Absender wartet dabei nicht auf Fehler, sondern sorgt schon vorher für die Möglichkeit einer Behandlung eines potenziellen Fehlers beim Empfänger. Das bedeutet, dass die Daten selbst schon die zur Korrektur eines Fehlers notwendigen Informationen enthalten. Dies wird durch eine sogenannte Redundanz erreicht. Hamming hatte auch eine Idee, wie man diese Redundanz messen kann:

Das ist heute als Hamming-Distanz bekannt. Diese Distanz beschreibt, wie sehr sich unterschiedliche Informationen unterscheiden. Ist die Distanz oder der Abstand klein, sind sich unterschiedliche Informationen sehr ähnlich. Es gibt wenig Redundanz und Fehler können nur schlecht erkannt und korrigiert werden. Wenn der Abstand dagegen groß ist, können Fehler leicht erkannt werden und bei geeigneter Definition der Kodierung auch korrigiert.

Wenn beispielsweise beim Wort Haus der erste Buchstabe fehlerhaft erkannt wurde, ist am Wort selber nicht mehr festzustellen ob nicht vielleicht Maus gemeint war. Die Hamming-Distanz ist also klein.

Schauen wir uns nun also den Hamming-Code am Beispiel eines Datenwortes mit 8 Bit an und zusätzlichen 4 Bit an Redundanz. Das resultierende Datenwort hat also 12 Bit, die wir von 1 bis 12 durchnummerieren. Jedes Bit, welches eine binäre Darstellung seiner Nummer mit nur einer 1 hat, wird als Paritätsbit benutzt, das sind also die 1, die 2, die 4 und die 8. Anders gesagt: Das sind genau die Zweierpotenzen. Die restlichen Bits werden vom Datenwort genutzt. Nun werden auch die Nummern der restlichen Bits binär dargestellt und den Paritätsbits zugeordnet. Das erste Bit, was vom Datenwort genutzt wird, ist Nummer 3. Die drei zerlegt sich binär in 1 und 2, das nächste ist die 5, welche sich in 1 und 4 zerlegt. So geht das weiter bis zum Bit mit der Nummer 12, welches sich in 4 und 8 zerlegt.

Nun nimmt man den Wert des Datenwortes und addiert jeweils die passenden Bits auf und setzt schließlich das eine darin enthaltene Paritätsbit, sodass die Summe immer gleich ist. Dieser Teil ist Konvention. Im Prinzip ist es beliebig, ob das Paritätsbit die Summe der Bits zu 0 oder zu 1 ergänzt. Aber es muss klar definiert sein. Man spricht von gerader oder ungerader Parität. So kodiert kann das Datenwort übertragen werden.

Das ist genau der interessante oder geniale Teil an dieser Kodierung, dass auf diese Weise 4 binäre Summen gebildet werden, die jeweils genau eines der Paritätsbits enthalten. Und auf der anderen Seite sind alle Datenbits 2 bis 3 Mal an Paritätsbits beteiligt.

Meist wird die gerade Parität bevorzugt. Das Paritätsbit ist dann genau die binäre Summe der entsprechenden Datenbits und auf der Empfangsseite ist die binäre Summe im Erfolgsfall Null, was meistens einfach zu prüfen ist. Der Aufwand auf der Prozessorebene ist also minimiert.

In dieser Tabelle steht links in Grün der Wert des Paritätbits, welcher auch gleichzeitig seine Nummer im vollständigen Datenwort ist. Oben in Blau steht die Nummer des Bits. Die x geben an, ob das Bit des Datenworts bei der Erzeugung des Bits der Parität berücksichtigt wird. Und unten in Gelb und Orange steht, ob es sich um ein Paritätsbit oder ein Datenbit handelt. Die lilafarbenen x werden also jeweils passend zum Ergebnis der Summe der anderen x in der Zeile gefüllt.

Beim Empfänger kommt das Datenwort an und er prüft die Bits ähnlich wie bei der Erzeugung. Er kann sich die Arbeit aber einfacher machen: Er bildet einfach die Summe einschliesslich des Paritätbits. Wenn alles gemäß der Konvention passt, war die Übertragung erfolgreich und die Arbeit erledigt. Wenn Paritätsbits falsch sind, lässt sich kombinieren, welches Bit den Fehler verursacht hat. Man schaut sich dazu an, welches Bit genau an den „falschen“ Paritätsbits beteiligt ist. Wenn mehrere Bits falsch waren, funktioniert die Ermittlung nicht zuverlässig. Dafür reicht die Hamming-Distanz in dieser Kodierung nicht aus.

Wenn beispielsweise das Bit 6 falsch übertragen wurde, werden Paritätsbit 2 und 4 falsch angezeigt. Umgekehrt sieht der Empfänger in der Tabelle, dass nur Bit 6 genau an diesen beiden Paritätsbits beteiligt ist und daraus den Schluss ziehen, dass er Bit 6 umkehren muss, um die richtigen Daten zu rekonstruieren. Ist die Übertragung dagegen so schlecht, dass Bit 6 und 7 falsch übertragen werden, werden die Paritätsbits 2 und 4 doppelt falsch und damit scheinbar wieder richtig ankommen und der Empfänger sieht nur Paritätsbit 1 als falsch. Daraus kann er nur den Schluss ziehen, dass nur das Paritätsbit 1 selbst falsch übertragen wurde. Das wird er einfach ignorieren und die Daten fälschlicherweise als korrekt annehmen. Wir haben also mit 2 fehlerhaften Bits die Möglichkeiten dieser Fehlerkorrektur überschritten.

Wenn es möglich ist, wird der Empfänger im Fehlerfall eine Rückwärts-Korrektur anfordern. Das heißt, die übertragenen Daten werden für ungültig erklärt und eine erneute Übertragung angefordert. Das geht natürlich nicht in allen Fällen. Daher ist die Vorwärtskorrektur in solchen Fällen besonders wichtig. Beispiele sind gespeicherte Daten oder Einweg-Übertragungen wie Rundfunk. Oder auch hohe Latenzzeiten, wie bei der Kommunikation durch die Weiten des Weltraums. Latenz ist auch beim Streaming wichtig. Da die Audio- und Videodaten zu einem bestimmten Zeitpunkt gehören, wäre eine spätere Korrektur sinnlos. Auch WSPR benutzt so eine Vorwärtskorrektur.

Dieses Beispiel für einen einfachen Hamming-Code ist natürlich nicht das Ende der Fahnenstange. Die Entwicklung ging weiter und heute gibt es eine Vielzahl von FEC-Systemen für unterschiedlichste Anforderungen.