Hadamard code: Difference between revisions

Revision as of 14:15, 28 August 2023

Latest revision as of 18:53, 17 May 2025

(5 intermediate revisions by 4 users not shown)

Line 27:

[[File:Variadic logical XOR.svg|thumb|250px|[[Exclusive or|XOR]] operations<br/>Here the white fields stand for 0<br/>and the red fields for 1]]

The '''Hadamard code''' is an [[error-correcting code]] named after the French mathematician [[Jacques Hadamard]] that is used for [[error detection and correction]] when transmitting messages over very noisy or unreliable channels. In 1971, the code was used to transmit photos of Mars back to Earth from the NASA space probe [[Mariner 9]].<ref name="Malek_2006"/> Because of its unique mathematical properties, the Hadamard code is not only used by engineers, but also intensely studied in [[coding theory]], [[mathematics]], and [[theoretical computer science]].

The Hadamard code is also known under the names '''Walsh code''', '''Walsh family''',<ref name="Amadei-Manzoli-Merani_2002"/> and '''Walsh–Hadamard code'''<ref name="Arora-Barak_2009"/> in recognition of the American mathematician [[Joseph Leonard Walsh]].

Line 62:

[[James Joseph Sylvester]] developed his construction of Hadamard matrices in 1867, which actually predates Hadamard's work on Hadamard matrices. Hence the name ''Hadamard code'' is disputed and sometimes the code is called ''Walsh code'', honoring the American mathematician [[Joseph Leonard Walsh]].

An augmented Hadamard code was used during the 1971 [[Mariner 9]] mission to correct for picture transmission errors. The databinary wordsvalues used during this mission were 6 bits long, which represented 64 [[grayscale]] values.

Because of limitations of the quality of the alignment of the transmitter at the time (due to Doppler Tracking Loop issues) the maximum useful data length was about 30 bits (the encoded block). Instead of using a [[repetition code]], a [32, 6, 16] Hadamard code was used.

Errors of up to 7 bits per block32-bit word could be corrected using this scheme. Compared to a 5-[[repetition code]], the error correcting properties of this Hadamard code are much better, yet its rate is comparable. The efficient decoding algorithm was an important factor in the decision to use this code.

The circuitry used was called the "Green Machine". It employed the [[fast Fourier transform]] which can increase the decoding speed by a factor of three. Since the 1990s use of this code by space programs has more or less ceased, and the [[NASA Deep Space Network]] does not support this error correction scheme for its dishes that are greater than 26&nbsp;m.

Line 88:

===Construction using a generator matrix===

The Hadamard code is a linear code, and all linear codes can be generated by a [[generator matrix]] <math>G</math>. This is a matrix such that <math>\text{Had}(x)= x\cdot G</math> holds for all <math>x\in\{0,1\}^k</math>, where the message <math>x</math> is viewed as a row vector and the vector-matrix product is understood in the [[vector space]] over the [[finite field]] <math>\mathbb F_2</math>. In particular, an equivalent way to write the inner product definition for the Hadamard code arises by using the generator matrix whose columns consist of ''all'' strings <math>y</math> of length <math>k</math>, that is,

:<math>G =

Line 156:

===Proof of lemma 1===

----

Let <math>C(x) = c = (c_0,\dots,c_{2^n-1})</math> be the codeword in <math>C</math> corresponding to message <math>x</math>.

Line 169 ⟶ 168:

===Proof of theorem 1===

----

To prove theorem 1 we will construct a decoding algorithm and prove its correctness.

Line 197 ⟶ 195:

==References==

{{Reflist|refs=

<ref name="Malek_2006">{{cite book |title=Coding Theory |chapter=HadarmarkHadamard Codes |author-first=Massoud |author-last=Malek |date=2006 |url=http://www.mcs.csueastbay.edu/~malek/TeX/Hadamard.pdf |url-status=dead |archive-url=https://web.archive.org/web/20200109044013/http://www.mcs.csueastbay.edu/~malek/TeX/Hadamard.pdf |archive-date=2020-01-09}}</ref>

<ref name="Amadei-Manzoli-Merani_2002">{{Cite book |title=Global Telecommunications Conference, 2002. GLOBECOM'02. IEEE |volume=1 |author-last1=Amadei |author-first1=M. |author-last2=Manzoli |author-first2=Umberto |author-last3=Merani |author-first3=Maria Luisa |chapter=On the assignment of Walsh and quasi-orthogonal codes in a multicarrier DS-CDMA system with multiple classes of users |publisher=[[IEEE]] |isbn=0-7803-7632-3 |doi=10.1109/GLOCOM.2002.1188196 |date=2002-11-17 |pages=841–845}}</ref>

<ref name="Arora-Barak_2009">{{Cite book |title=Computational Complexity: A Modern Approach |chapter=Section 19.2.2 |author-last1=Arora |author-first1=Sanjeev |author-link1=Sanjeev Arora |author-last2=Barak |author-first2=Boaz |publisher=[[Cambridge University Press]] |date=2009 |isbn=978-0-521-42426-4 |url=http://www.cs.princeton.edu/theory/complexity/}}</ref>

Line 214 ⟶ 212:

[[Category:Coding theory]]

[[Category:Error detection and correction]]

[[de:Walsh-Code]]

[[ja:直交符号]]