Hadamard-Code

Ein Hadamard-Code ist ein binärer Blockcode, der zur Fehlererkennung und Fehlerkorrektur verwendet wird. Er ist ein $[2^{n},n+1,2^{n-1}]$ linearer Code. Er wurde nach dem französischen Mathematiker Jacques Hadamard benannt. Für große Blocklängen $n$ haben die Hadamard-Codes eine schlechte Informationsrate, können aber viele Fehler korrigieren.

Matrix des [32,6,16] Hadamard-Codes der NASA Raumsonde Mariner 9 (1971/1972). Die Farbe Schwarz kodiert die Binärziffer 1, und die Farbe Weiß kodiert die Binärziffer 0.

Wahrheitstafel mit XOR-Verknüpfungen
Hier stehen die weißen Felder für falsch (0)
und die roten für wahr (1)

Konstruktion

Der Code basiert auf den Hadamard-Matrizen. Ist $H$ eine Hadamard-Matrix vom Rang $2^{n}$, dann werden die Codewörter konstruiert, indem die Zeilen von $H$ und $-H$ als Codewörter verwendet werden. Dabei werden die Einträge $-1$ durch $0$ ersetzt. Auf diese Art werden $2^{n+1}$ Codewörter der Länge $2^{n}$ konstruiert. Da die Zeilen von $H$ orthogonal sind, unterscheiden sich zwei verschiedenen Zeilen einer Hadamard-Matrix an $2^{n-1}$ Stellen. Also ist der Hammingabstand $2^{n-1}$. Es wurde somit ein $[2^{n},n+1,2^{n-1}]$-Code konstruiert.

Decodierung

Der Code hat einen minimalen Hammingabstand von $2^{n-1}$ und kann somit höchstens $t=2^{n-2}-1$ Fehler korrigieren. Wird ein Wort $v$ empfangen, wird es zuerst in einen $1/{-1}$ Vektor umgewandelt, indem alle Nuller durch −1 ersetzt werden. Nun wird das Vektor-Matrix-Produkt $vH^{T}$ berechnet. Der Eintrag mit dem höchsten Absolutwert korrespondiert mit der Zeile, die als Codewort verwendet wurde. Ist dieser Wert positiv, dann stammt das Wort aus $H$, ist er negativ, dann stammt das Wort aus $-H$.

Begründung: Traten keine Fehler auf, dann besteht das Produkt $vH^{T}$ nur aus Nullen und einem Eintrag $\pm 2^{n}$. Gab es Fehler in $v$, dann werden – in Absolutwerten – einige der Nullen größer und das Maximum wird kleiner. Jeder Fehler der auftritt kann eine Null durch eine 2 ersetzen. Also können höchstens $0+2t=2^{n-1}-2$ Nullen verändert werden. Das Maximum verringert sich höchstens auf $2^{n}-2t=2^{n}-2^{n-1}+2=2^{n-1}+2$. Also ist das Maximum, das auf die richtige Zeile zeigt, immer absolut größer als alle anderen Werte in der Zeile.

Geschichte

Ein Hadamard-Code wurde 1971 in der Mariner 9 Mission zur Korrektur von Bildübertragungen vom Mars verwendet. Die Datenwerte in dieser Mission waren 6 Bit lang, sie repräsentierten 64 Grauwerte. Aufgrund der Beschränkungen der Transmitter war die größte verwendbare Datenlänge 30 Bit. Anstelle eines Wiederholungscodes wurde der $[32,6,16]$ Hadamard-Code verwendet. Es konnten also 7 Bit pro 32-Bit-Wort korrigiert werden, 8 Bit Fehler wurden noch erkannt. Dieser Hadamard-Code hat verglichen mit einem 5-Wiederholungscode eine ähnliche Informationsrate, er besitzt allerdings eine bessere Korrekturrate. Ein wichtiger Grund für die Verwendung dieses Codes war dessen effizienter Decodierungsalgorithmus. Die Entschlüsselungsmaschine wurde „Green Machine“ genannt. Diese führte eine Schnelle Fourier-Transformation durch, die die Entschlüsselung um den Faktor 3 beschleunigte.

Optimalität

Für $n\leq 6$ sind die Hadamard-Codes optimal.

Literatur

• K. J. Horadam: Hadamard Matrices and Their Applications. Princeton University Press, 2006, ISBN 978-0-691-11921-2.