Hamming Code

Hamming Code

Der Hammingcode^*) ist ein selbstkorrigierender Code (ECC → Error Correcting Code, Fehlerkorrektur). Dazu verwendet er mehrere Paritätsbits. Die Information tragenden Nutzdatenbits werden in Gruppen unterteilt, wobei jede Gruppe durch die Paritätsbits ergänzt wird. Durch eine geschickte Wahl der Gruppierung, ist neben einer Fehlererkennung auch eine Fehlerkorrektur der übertragenen Datenbits möglich. 

Im folgenden wollen wir anhand eines Beispieles kennenlernen, wie der Hamming-Code eine zu übertragende Bitreihe bildet, wie bei Empfang der Bitreihe überprüft wird, ob diese Fehlerhaft oder korrekt ist und zuletzt, wie es der Hamming-Code schafft, eine Fehlerkorrektur durchzuführen.

^*) Benannt nach seinem Erfinder Richard Wesley Hamming von den Bell Labs.

Bildung der zu übertragende Bitreihe, sprich Hamming-Code

1. Zu übertragen ist die Bitreihe 1001010. Diese sieben Nutzdatenbits werden in die Tabelle unter Punkt 1 eintragen - dabei die Zellen 1,2,4 und 8 auslassen.
2. Die Position der Zellen 1..11, welche mit einer "1" (Nutzdatenbits Bitreihe) belegt sind, sind einer bestimmten Reihennummer zugeordnet. Deren Binärwerte  werden übertragslos addiert.
3. Die aus der Summe erhaltenen 4 Bits in die 4 Lücken der Tabelle.

Hier veranschaulicht mittels einer Grafik:

Hamming-Code Funktionsweise - Bildung Code mit Paritätsbits

Hamming-Code Funktionsweise - Überprüfung auf fehlerhafte Übertragung

Hamming-Code - Übertragungsfehler beschädigter Hamming-Code empfangen und korrigieren

1. Es wurden 11 Bit empfangen. Diese Bits wie gehabt in die zweizeilige Tabelle eintragen.
2. Die Position der Zellen 1 bis 11, in der eine "1" steht übertragslos addieren. Dazu die Zahlentabelle benützen. Als Ergebnis erhält man nicht 0000 sondern diesmal 0111.
3. Diese 0111₂ steht für die Zahl 7₁₀, d.h. deutet auf einen Fehler an der Stelle 7 hin. Eine Korrektur erfolgt durch Umkehrung dieses Bits.

Hamming-Code Funktionsweise - Übertragungsfehler beschädigter Hamming-Code empfangen und korrigieren