Hamming-Code

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. Im Allgemeinen gibt es einen Hamming-Code der Länge $2^r-1$ zu jedem $3 \le r \in \N$ , 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

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

Diskrete Mathematik | Informationstheorie | Zeichenkodierung Kodierungstheorie

Gourt Home::Gourt :: Hamming-Code

Generator- und Kontrollmatrizen

Erzeugung des (7,4) Hamming-Code

Beispiel: Erzeugung eines (7,4) Hamming-Codewortes

Ein-Bit-Fehler korrigieren

Weblinks