Hamming-Code

Unter dem so genannten Hamming-Code versteht man einen Code zur Fehlerkorrektur, der dazu genutzt werden kann, Fehler bei der Übertragung oder Speicherung von Daten zu entdecken und zu korrigieren. Er wurde nach seinem Erfinder Richard Wesley Hamming von den Bell Labs benannt.

Wie auch anderer fehlerkorrigierender Code setzt der Hamming-Code auf das Paritätsprinzip und nutzt dazu Paritätsbits. Dabei handelt es sich um spezielle Bits, die an Daten angehängt werden, so dass ihre Gültigkeit überprüft werden kann, wenn sie gelesen oder übertragen werden. Durch den Einsatz von mehr als einem einzigen Paritätsbit kann der Code nicht nur einzelne Fehler in den Daten erkennen, er kann sogar den Ort des Fehlers genau lokalisieren.

Insbesondere bei der Übertragung von Daten können so mit Hilfe der so genannten Forward Error Correction (FEC) Fehler erkannt und behoben werden. Dadurch erhöht sich allerdings der Durchsatz einer Übertragung, wenn in einem Netzwerk bereits ein hohes Grundrauschen vorhanden ist. Um die Fehlerkorrektur zu ermöglichen, fügt eine der übertragenden Stationen zusätzliche Informationen zu den Daten hinzu. Sie werden Error Correction Bits genannt. Nicht in jedem Fall lassen sich so jedoch mehr Kosten sparen, als wenn die Daten einfach noch einmal übertragen werden würden. Durch seinen fehlerkorrigierenden Blockcode kann der Hamming-Code jedoch dabei helfen, die Kosten für Forward Error Correction zu senken.

Um die Parität zu berechnen, werden zunächst alle Einsen in einem Datensatz gezählt. Anschließend wird ein Paritätsbit angehängt, das entweder aus einer Null oder einer Eins besteht. Die Parität der gezählten Einsen ist entweder ungerade (englisch: odd) oder gerade (englisch: even). Ein Beispiel: 1001 ist ein vier Bit langer Datensatz, der zwei Einser-Bits enthält. Da dies eine gerade Zahl ist, wird eine Null an den Datensatz angehängt, um eine gerade Parität zu erhalten. Bei einer ungeraden Parität würde stattdessen eine Eins angehängt.

Um eine gerade Parität zu berechnen, wird dann der Operator XOR verwendet. Bei einer ungeraden Parität nutzt man dagegen den Operator XNOR. Einzelne Bit-Fehler lassen sich nach einer Übertragung erkennen, weil das Paritätsbit darauf hinweist, dass die Zahl der Einsen in einem Datensatz nicht korrekt ist. Dadurch wird klar, dass sich ein Datenbit durch zum Beispiel das Rauschen im Netzwerk verändert haben muss. Der Hamming-Code kann auch mehr als einen einzigen Bit-Fehler durch den Einsatz mehrerer Paritätsbits offenlegen. Jedes Paritätsbit bezieht sich dann auf unterschiedliche Kombinationen der Bits in den zu überprüfenden Daten. Die Zahl der für diese Überprüfungen benötigten Paritätsbits hängt von der gesamten Zahl der Bits in der Datenübertragung ab. Sie wird mit Hilfe der folgenden Hamming-Regel berechnet:

p

d + p + 1 < = 2 (1)

Der Wert “d” ist dabei die Zahl der Datenbits, während “p” die Zahl der Paritätsbits ist. Die beiden ergeben zusammen das so genannte Hamming-Codewort, das durch das Multiplizieren der Daten-Bits mit Hilfe einer speziellen Generatormatrix erstellt werden kann.