- Hadamard-Code
-
Wahrheitstafel mit XOR-Verknüpfungen
Hier stehen die weißen Felder für falsch (0)
und die roten für wahr (1)Ein Hadamard-Code ist ein binärer Blockcode, der zur Fehlererkennung und Fehlerkorrektur verwendet wird. Er ist ein [2n,n + 1,2n − 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.
Inhaltsverzeichnis
Konstruktion
Der Code basiert auf den Hadamard-Matrizen. Ist H eine Hadamard-Matrix vom Rang 2n, 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 2n + 1 Codewörter der Länge 2n konstruiert. Da die Zeilen von H orthogonal sind, unterscheiden sich zwei verschieden Zeilen einer Hadamard-Matrix an 2n − 1 Stellen. Also ist der Hammingabstand 2n − 1. Es wurde somit ein [2n,n + 1,2n − 1]-Code konstruiert.
Decodierung
Der Code hat einen minimalen Hammingabstand von 2n − 1 und kann somit höchstens t = 2n − 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 vHT 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 vHT nur aus Nullen und einem Eintrag
. Gab es Fehler in v, dann werden - in Absolutwerten - einige der Nullen größer und das Maximum wird kleiner. Jeder Fehler der auftritt kann ein Null durch eine 2 ersetzen. Also können höchstens 0 + 2t = 2n − 1 − 2 Nullen verändert werden. Das Maximum verringert sich höchstens auf 2n − 2t = 2n − 2n − 1 + 2 = 2n − 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 Datenwörter 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 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.
Wikimedia Foundation.