Content deleted Content added
No edit summary |
|||
| (3 intermediate revisions by 2 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 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=
<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>
| |||