Hamming-Code

Als Hamming-Code bezeichnet man in der Codierungstheorie einen von Richard Hamming entdeckten 1-Fehler-korrigierenden Code mit einem Mindest-Hammingabstand 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 3 Bits zur Fehlerkorrektur dienen. Im Allgemeinen gibt es einen Hamming-Code der Länge $2^{r}-1$ zu jedem $r\in \mathbb {N} ,r\geq 3$, davon sind $r$ Bits Korrekturbits 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 hat Hamming-Abstand 1 von einem Codewort des Codes.

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

Der (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 3 × 4 Matrix, die die Sicherungsinformationen erzeugt. Der zu übertragende Bitstring $u$ wird dann aus der Nutzinformation $v$ wie folgt berechnet:

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

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

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: GARZA STINKT

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

Hamming-Code-Tool