Content deleted Content added
| (27 intermediate revisions by 19 users not shown) | |||
Line 1:
{{Short description|Error-correcting code}}
{{Lead too long|date=May 2020}}
{{use dmy dates|date=June 2021|cs1-dates=y}}
{{infobox code
| name = Hadamard code
Line 11 ⟶ 14:
}}
{{infobox code
| name =
| namesake = [[Jacques Hadamard]]
| type = [[Linear code|Linear]] [[block code]]
Line 21 ⟶ 24:
| notation = <math>[2^k,k+1,2^{k-1}]_2</math>-code
}}
[[File:Hadamard-Code.svg|thumb|250 px|Matrix of the
[[File:
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
▲It is also known under the names '''Walsh code''', '''Walsh family''',<ref>See, e.g., {{Harvtxt|Amadei|Manzoli|Merani|2002}}</ref> and '''Walsh–Hadamard code'''<ref>See, e.g., {{Harvtxt|Arora|Barak|2009|loc=Section 19.2.2}}.</ref> in recognition of the American mathematician [[Joseph Leonard Walsh]].
The Hadamard code is an example of a [[linear code]]
In this article, the first case is called the '''Hadamard code''' while the second is called the '''augmented Hadamard code'''.
The Hadamard code is unique in that each non-zero codeword has a [[Hamming weight]] of exactly <math>2^{k-1}</math>, which implies that the [[Block code#The distance d|distance]] of the code is also <math>2^{k-1}</math>.
In standard [[Block code#Popular notation|coding theory notation]] for [[block code]]s, the Hadamard code is a <math>[2^k,k,2^{k-1}]_2</math>-code, that is, it is a [[linear code]] over a [[binary set|binary alphabet]], has [[Block code#The block length n|block length]] <math>2^k</math>, [[Block code#The message length k|message length]] (or dimension) <math>k</math>, and [[Block code#The distance d|minimum distance]] <math>2^k/2</math>.
The block length is very large compared to the message length, but on the other hand, errors can be corrected even in extremely noisy conditions.
The
Normally, Hadamard codes are based on [[Hadamard matrix#Sylvester's construction|Sylvester's construction of Hadamard matrices]], but the term “Hadamard code” is also used to refer to codes constructed from arbitrary [[Hadamard matrix|Hadamard matrices]], which are not necessarily of Sylvester type.
In general, such a code is not linear.
Such codes were first constructed by [[
If ''n'' is the size of the Hadamard matrix, the code has parameters <math>(n,2n,n/2)_2</math>, meaning it is a not-necessarily-linear binary code with 2''n'' codewords of block length ''n'' and minimal distance ''n''/2. The construction and decoding scheme described below apply for general ''n'', but the property of linearity and the identification with Reed–Muller codes require that ''n'' be a power of 2 and that the Hadamard matrix be equivalent to the matrix constructed by Sylvester's method.
Line 54 ⟶ 49:
Since the relative distance of the Hadamard code is 1/2, normally one can only hope to recover from at most a 1/4 fraction of error. Using [[list decoding]], however, it is possible to compute a short list of possible candidate messages as long as fewer than <math>\frac{1}{2}-\epsilon</math> of the bits in the received word have been corrupted.
In [[code
==History==
Line 67 ⟶ 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]].
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. Instead of using a [[repetition code]], a [32, 6, 16] Hadamard code was used.
Errors of up to 7 bits per 32-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 m.
==Constructions==
Line 81 ⟶ 76:
===Construction using inner products===
When given a binary message <math>x\in\{0,1\}^k</math> of length <math>k</math>, the Hadamard code encodes the message into a codeword <math>\text{Had}(x)</math> using an encoding function <math>\text{Had} : \{0,1\}^k\to\{0,1\}^{2^k}.</math>
This function makes use of the [[inner product]] <math>\langle x , y \rangle</math> of two vectors <math>x,y\in\{0,1\}^k</math>, which is defined as follows:
:<math>\langle x , y \rangle = \sum_{i=1}^{k} x_i y_i\ \bmod\ 2\,.</math>
Line 87 ⟶ 82:
:<math>\text{Had}(x) = \Big(\langle x , y \rangle\Big)_{y\in\{0,1\}^k}</math>
As mentioned above, the ''
This is because, if the first bit of <math>y</math> is zero, <math>y_1=0</math>, then the inner product contains no information whatsoever about <math>x_1</math>, and hence, it is impossible to fully decode <math>x</math> from those positions of the codeword alone.
On the other hand, when the codeword is restricted to the positions where <math>y_1=1</math>, it is still possible to fully decode <math>x</math>.
Hence it makes sense to restrict the Hadamard code to these positions, which gives rise to the ''
===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 116 ⟶ 111:
The matrix <math>G</math> is a <math>(k\times 2^k)</math>-matrix and gives rise to the [[linear operator]] <math>\text{Had}:\{0,1\}^k\to\{0,1\}^{2^k}</math>.
The generator matrix of the ''
For example, the generator matrix for the
:<math>
Line 129 ⟶ 124:
Then <math>\text{pHad}:\{0,1\}^k\to\{0,1\}^{2^{k-1}}</math> is a linear mapping with <math>\text{pHad}(x)= x \cdot G'</math>.
For general <math>k</math>, the generator matrix of the
Hence an alternative way to define the Hadamard code is in terms of its parity-check matrix: the parity-check matrix of the Hadamard code is equal to the generator matrix of the Hamming code.
===Construction using general Hadamard matrices===
To get the
==Distance==
Line 147 ⟶ 142:
Then, when conditioned on the values of <math>y_2,\dots,y_k</math>, the event is equivalent to <math>y_1 \cdot x_1 = b</math> for some <math>b\in\{0,1\}</math> depending on <math>x_2,\dots,x_k</math> and <math>y_2,\dots,y_k</math>. The probability that <math>y_1=b</math> happens is exactly <math>1/2</math>. Thus, in fact, ''all'' non-zero codewords of the Hadamard code have relative Hamming weight <math>1/2</math>, and thus, its relative distance is <math>1/2</math>.
The relative distance of the ''
==Local decodability ==
Line 156 ⟶ 151:
<math>\forall x \in \{0,1\}^k, \forall y \in \{0,1\}^n</math>, <math>\Delta(y, C(x)) \leq \delta n</math> implies that <math>Pr[D(y)_i = x_i] \geq \frac{1}{2} + \epsilon, \forall i \in [k]</math>
'''Theorem 1:''' The Walsh–Hadamard code is <math>(2, \delta, \frac{1}{2}-2\delta)</math>-locally decodable for all <math>0\leq \delta \leq \frac{1}{4}</math>.
'''Lemma 1:''' For all codewords, <math>c</math> in a Walsh–Hadamard code, <math>C</math>, <math>c_i+c_j=c_{i+j}</math>, where <math>c_i, c_j</math> represent the bits in <math>c</math> in positions <math>i</math> and <math>j</math> respectively, and <math>c_{i+j}</math> represents the bit at position <math>(i+j)</math>.
===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 174 ⟶ 168:
===Proof of theorem 1===
To prove theorem 1 we will construct a decoding algorithm and prove its correctness.
Line 181 ⟶ 174:
For each <math>i \in \{1, \dots, n\}</math>:
# Pick <math>j \in \{0, \dots, 2^n-1\}</math> uniformly at random.
# Pick <math>k \in \{0, \dots, 2^n-1\}</math> such that <math>j+k = e_i</math>, where <math>e_i</math> is the <math>i</math>-th [[standard basis|standard basis vector]] and <math>j+k</math> is the bitwise ''xor'' of <math>j</math> and <math>k</math>.
# <math>x_i \gets y_j+y_k</math>.
'''Output:''' Message <math>x = (x_1, \dots, x_n)</math>
Line 192 ⟶ 185:
By lemma 1, <math>c_j+c_k = c_{j+k} = x\cdot g_{j+k} = x\cdot e_i = x_i</math>. Since <math>j</math> and <math>k</math> are picked uniformly, the probability that <math>y_j \not = c_j</math> is at most <math>\delta</math>. Similarly, the probability that <math>y_k \not = c_k</math> is at most <math>\delta</math>. By the [[union bound]], the probability that either <math>y_j</math> or <math>y_k</math> do not match the corresponding bits in <math>c</math> is at most <math>2\delta</math>. If both <math>y_j</math> and <math>y_k</math> correspond to <math>c</math>, then lemma 1 will apply, and therefore, the proper value of <math>x_i</math> will be computed. Therefore, the probability <math>x_i</math> is decoded properly is at least <math>1-2\delta</math>. Therefore, <math>\epsilon = \frac{1}{2} - 2\delta</math> and for <math>\epsilon</math> to be positive, <math>0 \leq \delta \leq \frac{1}{4}</math>.
Therefore, the Walsh–Hadamard code is <math>(2, \delta, \frac{1}{2}-2\delta)</math> locally decodable for <math>0\leq \delta \leq \frac{1}{4}</math>.
==Optimality==
For ''k'' ≤ 7 the linear Hadamard codes have been proven optimal in the sense of minimum distance.<ref
==See also==
* [[Zadoff–Chu sequence]] — improve over the Walsh–Hadamard codes
{{Reflist}}▼
==References==
<ref name="Malek_2006">{{cite book |title=Coding Theory |chapter=Hadamard 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>
<ref name="Guruswami_2009">{{Cite book |title=List decoding of binary codes |author-last1=Guruswami |author-first1=Venkatesan |date=2009 |page=3 |url=https://www.cs.cmu.edu/~venkatg/pubs/papers/ld-binary-ms.pdf}}</ref>
<ref name="Bose-Shrikhande_1959">{{cite journal |title=A note on a result in the theory of code construction |author-last1=Bose |author-first1=Raj Chandra |author-link1=Raj Chandra Bose |author-last2=Shrikhande |author-first2=Sharadchandra Shankar |author-link2=Sharadchandra Shankar Shrikhande |journal=[[Information and Control]] |volume=2 |issue=2 |date=June 1959 |doi=10.1016/S0019-9958(59)90376-6 |citeseerx=10.1.1.154.2879 |pages=183–194}}</ref>
<ref name="Langton_2002">{{cite web |title=CDMA Tutorial: Intuitive Guide to Principles of Communications |author-first=Charan |author-last=Langton |author-link=:d:Q61476932|date=2002 |url=http://complextoreal.com/wp-content/uploads/2013/01/CDMA.pdf |publisher=Complex to Real |access-date=2017-11-10 |url-status=live |archive-url=https://web.archive.org/web/20110720084646/http://www.complextoreal.com/CDMA.pdf |archive-date=2011-07-20}}</ref>
<ref name="Jaffe-Bouyukliev_2007">{{cite web |title=Optimal binary linear codes of dimension at most seven |author-first=David B. |author-last=Jaffe |author-first2=Iliya |author-last2=Bouyukliev |url=http://www.math.unl.edu/~djaffe2/papers/sevens.html |access-date=2007-08-21 |url-status=dead |archive-url=https://web.archive.org/web/20070808235329/http://www.math.unl.edu/~djaffe2/papers/sevens.html |archive-date=2007-08-08}}</ref>
}}
==Further reading==
* {{
* {{cite book |title=Modulationsverfahren |chapter=46.4. Hadamard– oder Walsh–Codes |language=de |author-first1=Dietmar |author-last1=Rudolph |author-first2=Matthias |author-last2=Rudolph |date=2011-04-12 |publisher=[[Brandenburg University of Technology]] (BTU) |publication-place=Cottbus, Germany |page=214 |url=http://www.diru-beze.de/modulationen/skripte/Modulationsverfahren.pdf |access-date=2021-06-14 |url-status=live |archive-url=https://web.archive.org/web/20210616042506/http://www.diru-beze.de/modulationen/skripte/Modulationsverfahren.pdf |archive-date=2021-06-16}} (xiv+225 pages)
▲*{{citation |first=Atri |last=Rudra |title=Hamming code and Hamming bound |format=PDF |url=http://www.cse.buffalo.edu/faculty/atri/courses/coding-theory/lectures/lect4.pdf |work=Lecture notes }}
{{CCSDS}}
Line 239 ⟶ 212:
[[Category:Coding theory]]
[[Category:Error detection and correction]]
| |||