Content deleted Content added
Fix syntax error in infoboxes |
m General fixes and Typo fixing, typo(s) fixed: Therefore → Therefore, using AWB |
||
Line 58:
==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 Walsh–Hadamard codes.
There is a reason for this:
[[Jacques Hadamard]] did not invent the code himself, but he defined [[Hadamard matrix|Hadamard matrices]] around 1893, long before the first [[error-correcting code]], the [[Hamming code]], was developed in the 1940s.
The Hadamard code is based on Hadamard matrices, and while there are many different Hadamard matrices that could be used here, normally only [[Hadamard matrix#Sylvester's construction|Sylvester's construction of Hadamard matrices]] is used to obtain the codewords of the Hadamard code.
Line 68:
[[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 not undisputed and sometimes the code is called ''Walsh code'', honoring the American mathematician [[Joseph Leonard Walsh]].
A Hadamard code was used during the 1971 [[Mariner 9]] mission to correct for picture transmission errors. The data words 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. 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.
Line 77:
==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 [[Block code#The rate R|rate]] of the code to be as high as possible, even if this means that the construction becomes mathematically slightly less elegant.
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 151:
==Local decodability ==
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>, is <math>(q, \delta\geq 0, \epsilon\geq 0)</math>-locally decodable, if there exists a probabilistic decoder, <math>D:\{0,1\}^n \rightarrow \{0,1\}^k</math>, such that ''(Note: <math>\Delta(x,y)</math> represents the [[Hamming distance]] between vectors <math>x</math> and <math>y</math>)'':
Line 191:
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 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>
Line 199:
==See also==
* [[Zadoff–Chu sequence]] — improve over the Walsh–Hadamard codes
==Notes==
| |||