Content deleted Content added
m moved Locally decodable to Locally decodable code over redirect: Should be a noun. Consider also Locally testable code, Error-correcting code. |
Citation bot (talk | contribs) m Citations: [189] added: postscript. Unified citation types. Ylloh |
||
Line 6:
== Examples ==
The [[Walsh-Hadamard code]] <math>WH</math> is a simple, locally decodable code. It has an optimal <math>q=2</math> queries and a best possible decoding error. However, codewords of <math>n</math>-bit messages have exponential length <math>N=2^n</math>, which is why the Walsh-Hadamard code has a very inefficient rate.
If a received signal <math>y\in\{0,1\}^N</math> agrees with some codeword <math>WH(x)</math> for some message <math>x\in\{0,1\}^n</math> on at least a <math>1-\delta</math> fraction of bits, then <math>x_i</math> can be recovered from <math>y</math> with probability <math>1-2\delta</math>.<ref>Section 11.5.2 of {{
| last1=Arora | first1=Sanjeev | authorlink1=Sanjeev Arora
| last2=Barak | first2=Boaz
Line 14:
| year=2009
| isbn=978-0-521-42426-4
| postscript=<!-- Bot inserted parameter. Either remove it; or change its value to "." for the cite to end in a ".", as necessary. -->{{inconsistent citations}}
}}</ref>
== References ==
| |||