Direkt zum Inhalt

Lexikon der Mathematik: Hamming-Code

von Richard Hamming eingeführter linearer, 1-fehlerkorrigierender Code (fehlerkorrigierender Code) \begin{eqnarray}\kappa:\{0,1\}^{m}\rightarrow \{0,1\}^{m+r},\end{eqnarray} wobei r ∈ ℕ minimal unter der Bedingung m + r + 1 ≤ 2r gewählt ist.

Die Bitstellen 20, 21, …,2r-1 des Codewortes dienen als Parity Bits. Die Bits der zu codierenden Nachricht aus {0, 1}m werden auf die m restlichen Bitstellen des Codewortes abgebildet. Das Parity Bit an der Bitstelle 2i überprüft alle die Bitstellen des Codewortes, deren Adressen, (d. h. deren binäre Adressendarstellungen) an der iten Bitstelle eine i haben. Die Numerierung der Bitstellen des Codewortes beginnt dabei mit i. Wird nun eine so codierte Nachricht über einen Kanal übertragen (Informationstheorie), und ist beim Empfang die Belegung der Parity Bits \({{2}^{{{j}_{1}}}},\ldots,{{2}^{{{j}_{k}}}}\) falsch, so folgt hieraus, daß die \(\left( \underset{i=1}{\overset{k}{\mathop \sum }}\,{{2}^{{{j}_{i}}}} \right)\)-te Bitstelle des Codewortes bei der Übertragung gekippt ist, geht man von der Annahme aus, daß höchstens eine Bitstelle des Codewortes während der Übertragung gestört werden kann.

Hamming-Codes können auch in äquivalenter Weise als (n, k)-Codes über einem beliebigen Körper K definiert werden. Die Kontrollmatrix H besteht dabei aus allen von Null verschiedenen und paarweise linear unabhängigen (nk)-dimensionalen Spaltenvektoren über K.

Ein binärer Hamming-Code ist damit ein (2r − 1, 2rr − 1)-Code (mit r = nk). Die Kontrollmatrix < ?PageNum _365für r = 3 hat zum Beispiel die Form \begin{eqnarray}H=\begin{pmatrix}0 & 0 & 0 & 1 & 1 & 1 & 1\\ 0 & 1 & 1 & 0 & 0 & 1 & 1\\ 1 & 0 & 1 & 0 & 1 & 0 & 1 \end{pmatrix}.\end{eqnarray} Der Code besteht aus allen Vektoren (c1, …, c7) mit c5 = c2 + c3 + c4, c6 = c1 + c3 + c4 und c7 = c1 + c2 + c4. Ist c* = c + ei ein Wort, bei dem ein einziger Fehler aufgetreten ist, dann kann aus dem Spaltenvektor \(H\cdot c_{*}^{\top}\) eindeutig die Stelle i, an der der Bitfehler auftrat, rekonstruiert werden. So ist \(c_{*}=1010110^{\top}\) kein Codewort, denn \begin{eqnarray}H\cdot c^{\top}_{*}=(0,0,1)^{\top}\neq 0.\end{eqnarray} Ein einfacher Bitfehler muß dann an der ersten Stelle aufgetreten sein, das korrigierte Codewort ist (0010110).

Über beliebigen Körpern mit q Elementen sind die Hamming-Codes ((qk − 1)/(q − 1), (qk − 1)/ (q − 1) − r − 1)-Codierungen.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos