Hadamard-Code
Ein Hadamard-Code ist ein binärer Blockcode, der zur Fehlererkennung und Fehlerkorrektur verwendet wird. Er ist ein linearer Code. Er wurde nach dem französischen Mathematiker Jacques Hadamard benannt. Für große Blocklängen haben die Hadamard-Codes eine schlechte Informationsrate, können aber viele Fehler korrigieren.
Konstruktion
Der Code basiert auf den Hadamard-Matrizen. Ist eine Hadamard-Matrix vom Rang , dann werden die Codewörter konstruiert, indem die Zeilen von und als Codewörter verwendet werden. Dabei werden die Einträge durch ersetzt. Auf diese Art werden Codewörter der Länge konstruiert. Da die Zeilen von orthogonal sind, unterscheiden sich zwei verschiedenen Zeilen einer Hadamard-Matrix an Stellen. Also ist der Hammingabstand . Es wurde somit ein -Code konstruiert.
Decodierung
Der Code hat einen minimalen Hammingabstand von und kann somit höchstens Fehler korrigieren. Wird ein Wort empfangen, wird es zuerst in einen Vektor umgewandelt, indem alle Nuller durch −1 ersetzt werden. Nun wird das Vektor-Matrix-Produkt 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 , ist er negativ, dann stammt das Wort aus .
Begründung: Traten keine Fehler auf, dann besteht das Produkt nur aus Nullen und einem Eintrag . Gab es Fehler in , 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 Nullen verändert werden. Das Maximum verringert sich höchstens auf . 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 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 sind die Hadamard-Codes optimal.
Literatur
- K. J. Horadam: Hadamard Matrices and Their Applications. Princeton University Press, 2006, ISBN 978-0-691-11921-2.
Auf dieser Seite verwendete Medien
Exclusive disjunctions of the arguments in the parentheses to the left of the matrix
This is a binary Walsh matrix. The rows are the first 16 binary Walsh functions.
Image set Variadic Boolean functions (16×16 tables) | |
---|---|
AND |
OR |
XAND |
XOR |