imported>Invisigoth67: form

2026-03-27T15:06:29Z

form

Neue Seite

[[Datei:Hadamard-Code.svg|mini|230px|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.]]
[[Datei:Variadic logical XOR.svg|mini|230px|Wahrheitstafel mit [[Kontravalenz|XOR]]<nowiki>-Verknüpfungen</nowiki><br />Hier stehen die weißen Felder für ''falsch'' (0)<br />und die roten für ''wahr'' (1)]]
Ein '''Hadamard-Code''' ist ein [[Dualsystem|binärer]] [[Blockcode]], der zur Fehlererkennung und Fehlerkorrektur verwendet wird. Er ist ein <math>[2^n,n+1,2^{n-1}]</math> [[linearer Code]]. Er wurde nach dem französischen Mathematiker [[Jacques Salomon Hadamard|Jacques Hadamard]] benannt.
Für große Blocklängen <math>n</math> haben die Hadamard-Codes eine schlechte [[Blockcode#Informationsrate von Blockcodes|Informationsrate]], können aber viele Fehler korrigieren.

== Konstruktion ==
Der Code basiert auf den [[Hadamard-Matrix|Hadamard-Matrizen]]. Ist <math>H</math> eine Hadamard-Matrix vom Rang <math>2^n</math>, dann werden die Codewörter konstruiert, indem die Zeilen von <math>H</math> und <math>\bar{H}</math> als Codewörter verwendet werden. Dabei ist <math>\bar{H}</math> das Komplement von <math>H</math>, d. h. <math>1</math> und <math>0</math> sind vertauscht. Auf diese Art werden <math>2^{n+1}</math> Codewörter der Länge <math>2^n</math> konstruiert. Da die Zeilen von <math>H</math> orthogonal sind, unterscheiden sich zwei verschiedenen Zeilen einer Hadamard-Matrix an <math>2^{n-1}</math> Stellen. Also ist der [[Hamming-Abstand#Hamming-Abstand eines Codes|Hammingabstand]] <math>2^{n-1}</math>. Es wurde somit ein <math>[2^n,n+1,2^{n-1}]</math>-Code konstruiert.

== Decodierung ==
Der Code hat einen minimalen Hammingabstand von <math>2^{n-1}</math> und kann somit höchstens <math>t=2^{n-2}-1</math> Fehler korrigieren.
Wird ein Wort <math>v</math> empfangen, wird es zuerst in einen <math>1/{-1}</math> Vektor umgewandelt, indem alle Nuller durch −1 ersetzt werden. Nun wird das [[Vektor-Matrix-Produkt]] <math>vH^T</math> 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 <math>H</math>, ist er negativ, dann stammt das Wort aus <math>-H</math>.

''Begründung:'' Traten keine Fehler auf, dann besteht das Produkt <math>v H^T</math> nur aus Nullen und einem Eintrag <math>\pm 2^n</math>. Gab es Fehler in <math>v</math>, 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 <math>0+2t=2^{n-1}-2</math> Nullen verändert werden. Das Maximum verringert sich höchstens auf <math>2^n-2t=2^n-2^{n-1}+2=2^{n-1}+2</math>. 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#Mariner 8 und 9|Mariner 9]] Mission zur Korrektur von Bildübertragungen vom Mars verwendet. Die Datenwerte in dieser Mission waren 6 Bit lang, sie repräsentierten 64 [[Grauwert]]e. Aufgrund der Beschränkungen der Transmitter war die größte verwendbare Datenlänge 30 Bit. Anstelle eines [[Wiederholungscode]]s wurde der <math>[32,6,16]</math> 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 <math>n \leq 6</math> sind die Hadamard-Codes [[Optimaler Code|optimal]].

== Literatur ==
* {{Literatur
|Autor = K. J. Horadam
|Titel = Hadamard Matrices and Their Applications
|Verlag = Princeton University Press | Jahr = 2006 | ISBN = 978-0-691-11921-2 }}

[[Kategorie:Kodierungstheorie]]
[[Kategorie:Binärcode]]

Hadamard-Code - Versionsgeschichte

imported>Invisigoth67: form