Content deleted Content added
m Added explanation of use of the term "concatenation" |
m Added link to bitwise XOR and Hadamard |
||
Line 71:
== Examples ==
=== The Hadamard code ===
The [[Hadamard]] (or Walsh-Hadamard) code is an example of a simple locally decodable code that maps a string of length <math>k</math> to a codeword of length <math>2^k</math>. The codeword for a string <math>x \in \{0, 1\}^k</math> is constructed as follows: for every <math>a_j\in\{0, 1\}^k</math>, the <math>j^{th}</math> bit of the codeword is equal to <math>x \odot a_j</math>, where <math>x \odot y = \sum\limits_{i=1}^{k} x_{i}y_i</math> (mod 2). It is easy to see that every codeword has a [[Hamming distance]] of <math>\frac{n}{2}</math> from every other codeword.
The local decoding algorithm has query complexity 2, and the entire original message can be decoded with good probability if the codeword is corrupted in less than <math>\frac{1}{4}</math> of its bits. For <math>\rho < \frac{1}{4}</math>, if the codeword is corrupted in a <math>\rho</math> fraction of places, a local decoding algorithm can recover the <math>i^{th}</math> bit of the original message with probability <math>1 - 2\rho</math>.
Line 77:
Proof: Given a codeword <math>H</math> and an index <math>i</math>, the algorithm to recover the <math>i^{th}</math> bit of the original message <math>x</math> works as follows:
Let <math>e^j</math> refer to the vector in <math>\{0, 1\}^k</math> that has 1 in the <math>j^{th}</math> position and 0s elsewhere. For <math>y \in \{0, 1\}^k</math>, <math>f(y)</math> denotes the single bit in <math>H</math> that corresponds to <math>x \odot y</math>. The algorithm chooses a random vector <math>y \in \{0, 1\}^k</math> and the vector <math>y' = y \otimes e^i</math> (where <math>\otimes</math> denotes [[bitwise XOR]]). The algorithm outputs <math>f(y) \otimes f(y')</math> (mod 2).
Correctness: By linearity,
| |||