Locally decodable code: Difference between revisions

Revision as of 09:52, 6 November 2010

Revision as of 06:38, 30 July 2011

Line 5:

== Examples ==

The [[Walsh-HadamardWalsh–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-HadamardWalsh–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 {{Cite book

| last1=Arora | first1=Sanjeev | authorlink1=Sanjeev Arora