Content deleted Content added
better title of the section |
|||
Line 37:
=== Hadamard code ===
One of the most famous error-correcting codes, the [[Hadamard code]], is a locally testable code. A codeword x is encoded in the Hadamard code to be the linear function <math>f(y)={\sum_i {x_i y_i}}</math> (mod 2). This requires listing out the result of this function for every possible y, which requires exponentially more bits than its input. To test if a string w is a codeword of the Hadamard code, all we have to do is test if the function it encodes is linear. This means simply checking if <math>w(x)\oplus w(y)=w(x\oplus y)</math> for x and y [[Uniform distribution (discrete)|uniformly random]] vectors (where <math>\oplus</math> denotes [[bitwise XOR]]).
It is easy to see that for any valid encoding <math>w</math>, this equation is true, as that is the definition of a linear function. Somewhat harder, however, is showing that a string that is <math>\delta</math>-far from C will have an upper bound on its error in terms of <math>\delta</math>. One bound is found by the direct approach of approximating the chances of exactly one of the three probes yielding an incorrect result. Let A, B, and C be the events of <math>w(x)</math>, <math>w(y)</math>, and <math>w(x\oplus y)</math> being incorrect. Let E be the event of exactly one of these occurring. This comes out to
| |||