Hadamard-Code


Hadamard-Code
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)

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 \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 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 n \leq 6 sind die Hadamard-Codes optimal.


Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Hadamard code — The Hadamard code, named after Jacques Hadamard, is a system used for signal error detection and correction. It is one of the family of [2 n , n + 1, 2 n − 1] codes. Especially for large n it has a poor rate but it is capable of correcting many… …   Wikipedia

  • Hadamard matrix — In mathematics, a Hadamard matrix is a square matrix whose entries are either +1 or −1 and whose rows are mutually orthogonal. This means that every two different rows in a Hadamard matrix represent two perpendicular vectors. Such matrices can… …   Wikipedia

  • Hadamard — Jacques Salomon Hadamard Jacques Salomon Hadamard (* 8. Dezember 1865 in Versailles; † 17. Oktober 1963 in Paris) war ein französischer Mathematiker. Inhaltsverzeichnis 1 …   Deutsch Wikipedia

  • Code — redirects here. CODE may also refer to Cultural Olympiad Digital Edition. Decoded redirects here. For the television show, see Brad Meltzer s Decoded. For code (computer programming), see source code. For other uses, see Code (disambiguation).… …   Wikipedia

  • Reed-Muller-Code — Die Reed Muller Codes sind eine Familie von linearen, fehlerkorrigierenden Codes, die im Bereich der Kanalcodierung zur gesicherten Datenübertragung und Datenspeicherung Verwendung finden. Diese Klasse von Codes wurden von Irving S. Reed und… …   Deutsch Wikipedia

  • Jacques Salomon Hadamard — (* 8. Dezember 1865 in Versailles; † 17. Oktober 1963 in Paris) war ein französischer Mathematiker. Inhaltsverzeichnis 1 …   Deutsch Wikipedia

  • Jacques Hadamard — Jacques Salomon Hadamard Jacques Hadamard (Jacques Salomon Hadamard; * 8. Dezember 1865 in Versailles; † 17. Oktober 1963 in Paris) war ein französischer Mathematiker. Inhaltsverzeichnis …   Deutsch Wikipedia

  • Binary Golay code — In mathematics and computer science, a binary Golay code is a type of error correcting code used in digital communications. The binary Golay code, along with the ternary Golay code, has a particularly deep and interesting connection to the theory …   Wikipedia

  • Linearer Code — Ein linearer Code ist in der Kodierungstheorie ein spezieller Blockcode, bei dem die Codewörter Elemente eines endlichdimensionalen Vektorraums über einem endlichen Körper sind. Ein Code ist genau dann ein linearer Code, falls er ein… …   Deutsch Wikipedia

  • Reed–Muller code — Reed Muller codes are a family of linear error correcting codes used in communications. They are named after their discoverers, Irving S. Reed and D. E. Muller. Muller discovered the codes, and Reed proposed the majority logic decoding for the… …   Wikipedia


We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.