Hamming-Code

Als Hamming-Code bezeichnet man in der Kodierungstheorie einen von Richard Hamming entdeckten Code mit einem Mindest-Hamming-Abstand von 3.

Der bekannteste Hamming-Code ist der (7,4)-Code, er hat also eine Länge von 7 Bits, wovon 4 Bits Nutzinformationen sind und die restlichen 3 Bits der Fehlerkorrektur dienen.

Es gibt einen Hamming-Code der Länge $2^{r}-1$ zu jedem $3\leq r\in \mathbb {N}$ , davon sind $r$ Bits Korrektur-Bits und die restlichen $2^{r}-1-r$ Bits Informations-Bits.

Hamming-Codes sind perfekt, d.h. jedes mögliche Wort ist entweder ein Codewort oder es hat Hamming-Abstand 1 von einem Codewort des Codes, was bedeutet, dass dieses Wort z.B. durch einen Übertragungsfehler in einem Bit verändert wurde. Dieser Fehler kann nun korrigiert werden.

Generator- und Kontrollmatrizen

Hamming-Codes sind lineare Codes und lassen sich somit durch eine Generatormatrix oder eine Kontrollmatrix darstellen.

Erzeugung des (7,4) Hamming-Code

Ein (7,4)-Hamming-Code wird durch die folgende Generatormatrix $G$ erzeugt:

$G={\begin{pmatrix}1&0&0&0&|&1&1&1\\0&1&0&0&|&0&1&1\\0&0&1&0&|&1&0&1\\0&0&0&1&|&1&1&0\end{pmatrix}}$

$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:

$u^{T}=v^{T}\cdot G$

$H$ ist die Kontrollmatrix des (7,4) Hamming-Codes. Ihre Spalten sind alle Bitvektoren der Länge 3 außer dem Nullvektor.

$H={\begin{pmatrix}1&0&1&1&|&1&0&0\\1&1&0&1&|&0&1&0\\1&1&1&0&|&0&0&1\\\end{pmatrix}}$

Ein Codewort $u$ gehört genau dann zum Hamming-Code, falls $Hu=0$ ist. Ist $Hu\neq 0$ , 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}$ .

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

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

Weblinks