Content deleted Content added
cleanup |
|||
Line 25:
| notation = <math>[2^{k-1},k,2^{k-2}]_2</math>-code
}}
[[File:Hadamard-Code.svg|thumb|right|250 px|Matrix of the Hadamard code (32, 6, 16) for the [[
[[File:Multigrade operator XOR.svg|thumb|250px|[[Exclusive or|XOR]] operations<br>Here the white fields stand for 0<br>and the red fields for 1]]
Line 34:
The Hadamard code is an example of a [[linear code]] over a [[binary set|binary alphabet]] that maps messages of length <math>k</math> to codewords of length <math>2^k</math>.
It is unique in that each non-zero codeword has a [[Hamming weight]] of exactly <math>2^k/2</math>, which implies that the [[
In standard [[
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 '''punctured Hadamard code''' is a slightly improved version of the Hadamard code; it is a <math>[2^{k-1},k,2^{k-2}]_2</math>-code and thus has a slightly better [[
The punctured Hadamard code is the same as the first order [[Reed–Muller code]] over the binary alphabet.<ref>See, e.g., {{harvtxt|Guruswami|2009|p=3}}.</ref>
Line 54:
| id = {{citeseerx|10.1.1.154.2879}}
}}</ref>
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 Hadamard code is a [[locally decodable]] code, which provides a way to recover parts of the original message with high probability, while only looking at a small fraction of the received word. This gives rise to applications in [[computational complexity theory]] and
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 division multiple access]] (CDMA) communication, the Hadamard code is referred to as Walsh Code, and is used to define individual [[telecommunications|communication]] [[channel (communications)|channels]].
==History==
''Hadamard code'' is the name that is most commonly used for this code in the literature. However, in modern use these error correcting codes are referred to as
There is a reason for this:
Line 76:
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 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 Deep Space Network does not support this error correction scheme for its dishes that are greater than 26 m.
==Constructions==
While all Hadamard codes are based on Hadamard matrices, the constructions differ in subtle ways for different scientific fields, authors, and uses. Engineers, who use the codes for data transmission, and [[coding theory|coding theorists]], who analyse extremal properties of codes, typically want the [[
On the other hand, for many applications of Hadamard codes in [[theoretical computer science]] it is not so important to achieve the optimal rate, and hence simpler constructions of Hadamard codes are preferred since they can be analyzed more elegantly.
Line 150:
The fact that the latter value is exactly <math>1/2</math> is called the ''random subsum principle''. To see that it is true, assume without loss of generality that <math>x_1=1</math>.
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
The relative distance of the ''punctured'' Hadamard code is <math>1/2</math> as well, but it no longer has the property that every non-zero codeword has weight exactly <math>1/2</math> since the all <math>1</math>s vector <math>1^{2^{k-1}}</math> is a codeword of the punctured Hadamard code. This is because the vector <math>x=10^{k-1}</math> encodes to <math>\text{pHad}(10^{k-1}) = 1^{2^{k-1}}</math>. Furthermore, whenever <math>x</math> is non-zero and not the vector <math>10^{k-1}</math>, the random subsum principle applies again, and the relative weight of <math>\text{Had}(x)</math> is exactly <math>1/2</math>.
Line 157:
A [[locally decodable]] code is a code that allows a single bit of the original message to be recovered with high probability by only looking at a small portion of the received word.
A code is <math>q</math>-query [[locally decodable]] if a message bit, <math>x_i</math>, can be recovered by checking <math>q</math> bits of the received word. More formally, a code, <math>C: \{0,1\}^k \rightarrow \{0,1\}^n</math>,
<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>
Line 195:
For any message, <math>x</math>, and received word <math>y</math> such that <math>y</math> differs from <math>c = C(x)</math> on at most <math>\delta</math> fraction of bits, <math>x_i</math> can be decoded with probability at least <math>\frac{1}{2}+(1-2\delta)</math>.
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
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>
Line 210:
==References==
* {{Citation
| last1=Amadei
| last2=Manzoli | first2=U.
| last3=Merani
| 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
| year=2002
| pages=841–5
| |||