Hamming-Code
aus Wikipedia, der freien Enzyklopädie
Als Hamming-Code bezeichnet man in der Kodierungstheorie einen von Richard Hamming entdeckten Code mit einem Mindest-Hamming-Abstand von 3.
Der einfachste Hamming-Code ist ein (7,4) Code, er hat also eine Länge von 7 Bits, wovon 4 Bits Nutzinformationen sind und die restlichen (7 Bit Codewort Länge - 4 Bit Nutzinformationen) = 3 Bits zur Fehlerkorrektur dienen.
Es gibt einen Hamming-Code der Länge 2r − 1 zu jedem 
, davon sind r Bits Korrektur-Bits und die restlichen 2r − 1 − r Bits Informations-Bits.
Hamming-Codes sind perfekt, d.h. jedes mögliche Wort ist entweder ein Codewort oder hat Hamming-Abstand 1 von einem Codewort des Codes.
Inhaltsverzeichnis |
[Bearbeiten] Generator- und Kontrollmatrizen
Hamming-Codes sind lineare Codes und lassen sich somit durch eine Generatormatrix oder eine Kontrollmatrix darstellen.
[Bearbeiten] Erzeugung des (7,4) Hamming-Code
Ein (7,4) Hamming-Code wird durch die folgende Generatormatrix G erzeugt:
G setzt sich zusammen aus der Einheitsmatrix E und einer 4 × 3 Matrix, die die Sicherungsinformationen erzeugt. Die zu übertragende Bitsequenz u wird dann aus der Nutzinformation v wie folgt berechnet:
H ist die Kontrollmatrix des (7,4) Hamming-Codes. Ihre Spalten sind alle Bitvektoren der Länge 3 außer dem Nullvektor.
Ein Codewort u gehört genau dann zum Hamming-Code, falls Hu = 0 ist. Ist 
, heißt das, dass bei der Übertragung ein Bitfehler aufgetreten ist. Durch Vergleich von Hu mit den Spalten von H lässt sich (im Fall eines Ein-Bit-Fehlers, einem sogenannten Einzelfehler) zusätzlich ermitteln, welches Bit aus u verfälscht wurde. Für Bit 3 wäre das z.B. w = (1,0,1)T.
[Bearbeiten] Beispiel: Erzeugung eines (7,4) Hamming-Codewortes
| Nutzdaten | : | 1 | 0 | 0 | 1 | ||||
| Prüfbit 1 | : | 1 | 0 | 1 | => | 0 | |||
| Prüfbit 2 | : | 1 | 0 | 1 | => | 0 | |||
| Prüfbit 3 | : | 1 | 0 | 0 | => | 1 |
Die drei Prüfbits (dezimal 2, 2, 1) werden jeweils modulo 2 gerechnet, da eine Binärzahl benötigt wird. Das zu übermittelnde Wort lautet also 1 0 0 1 0 0 1
[Bearbeiten] Ein-Bit-Fehler korrigieren
Angenommen als übermitteltes Wort ist 1 0 1 1 0 0 1 angekommen; der Fehler steckt im dritten Bit. Zur Prüfung wird diese Rechnung dann umgekehrt durchgeführt:
| Nutzdaten | : | 1 | 0 | 1 | 1 | ||||||
| Prüfung 1 | 0 | = | 1 | 1 | 1 | => | Fehler | ||||
| Prüfung 2 | 0 | = | 1 | 0 | 1 | ||||||
| Prüfung 3 | 1 | = | 1 | 0 | 1 | => | Fehler |
Taucht ein Fehler nur in einer der drei Prüfungen auf steckt der Fehler in dem jeweiligen Prüfbit.
Taucht ein Fehler in Prüfung 1 und 2 auf ist der Fehler in Bit Nr. 4
Taucht ein Fehler in Prüfung 1 und 3 auf ist der Fehler in Bit Nr. 3
Taucht ein Fehler in Prüfung 2 und 3 auf ist der Fehler in Bit Nr. 2
Taucht ein Fehler in allen Prüfungen auf ist der Fehler in Bit Nr. 1
