Hamming-Code

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.

Hier ist von Summe von Bits die Rede. Der Übertrag wird dabei ignoriert, sodass bei einem Bit gilt: 1+1=0. In Boole-Logik ist das ein Exklusives Oder XOR.
In anderer Literatur wird das auch so beschrieben, dass an der Summe beurteilt wird, ob sie gerade oder ungerade ist. Mathematisch ist es dasselbe, in der technischen Realisierung wird es üblicherweise so gemacht, wie es hier beschrieben wird.

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.

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.

Fehlererkennung

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.

Um einen Fehler zu erkennen und zu korrigieren berechnet man die Checksumme für jedes Paritätsbit. Wenn alle Checksummen gerade (bzw. ungerade) sind, dann ist das Codewort fehlerfrei.
Identifiziere alle Paritätsbits mit fehlerhaften Checksummen. Bilde die Schnittmenge aller von nicht korrekten Paritätsbits geprüften Bits. Eliminiere alle Bits, die auch von korrekten Paritätsbits geprüft werden. Das fehlerhafte Bit bleibt übrig.
Alternative Methode: Die Summe der Nummern der fehlerhaften Paritätsbits ergibt die Nummer des fehlerhaften Bits.
Beispiel: Finde und korrigiere einen eventuell vorhandenen Fehler in dem Codewort 1100 0110 0110.
Dieses 12-Bit Codewort hat vier Paritätsbits, Bits Nummer 1,2,4 und 8. Die Prüfsummen der Bits 1 und 2 sind falsch. Die Schnittmenge der Bitlisten sind die Bits 3, 7 und 11, also ist eins von diesen fehlerhaft. Bit 11 wird auch von Bit 8 geprüft, dessen Checksumme korrekt ist, also ist auch Bit 11 OK. Bit 7 wird auch von Bit 4 geprüft, dessen Checksumme korrekt ist, also ist auch Bit 7 OK. Bit 3 wird nur von den Bits 1 und 2 geprüft, also ist Bit 3 falsch.

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.

gesendetes Codewort    1110 0110 0110
empfangenes Codewort 1100 0110 0110

\[\begin{array}{*{20}{c}}{(1}&1&0&0&0&1&1&0&0&1&1&0\end{array})\left( {\begin{array}{*{20}{c}}0&0&0&1\\0&0&1&0\\0&0&1&1\\0&1&0&0\\0&1&0&1\\0&1&1&0\\0&1&1&1\\1&0&0&0\\1&0&0&1\\1&0&1&0\\1&0&1&1\\1&1&0&0\end{array}} \right) = \left( {\begin{array}{*{20}{c}}0&0&1&1\end{array}} \right)\]

\[\begin{array}{*{20}{c}}2&2&5&3\\g&g&u&u\\0&0&1&1\end{array}\]

Bit Nummer 3 ist fehlerhaft