Locally decodable code: Difference between revisions

Revision as of 20:19, 22 April 2013

Revision as of 21:22, 22 April 2013

Line 5:

== Examples ==

=== The Hadamard code ===

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.

IfThe a[[Hadamard received signalcode]] <math>y\in\mathrm{0,1\Had}^N</math> agreesis witha somesimple, codewordlocally <math>WH(x)</math>decodable forcode. someIt messagehas an optimal <math>x\in\{0,1\}^nq=2</math> onqueries at leastand a <math>1-\delta</math>best fractionpossible ofdecoding error. bitsHowever, thencodewords of <math>x_in</math>-bit canmessages behave recoveredexponential fromlength <math>yN=2^n</math>, withwhich probabilityis <math>1-2\delta</math>.<ref>Sectionwhy 11.5.2the ofHadamard {{Citecode bookhas a very inefficient rate.

If a received signal <math>y\in\{0,1\}^N</math> agrees with some codeword <math>\mathrm{Had}(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

| last2=Barak | first2=Boaz

Line 16 ⟶ 17:

| postscript=<!-- Bot inserted parameter. Either remove it; or change its value to "." for the cite to end in a ".", as necessary. -->{{inconsistent citations}}

}}</ref>

=== The Reed–Muller code ===

The [[Reed–Muller code]] is an error-correcting code that is locally decodable, and moreover, locally [[list-decodable]].

It is a multivariate generalization of the [[Reed–Solomon code]], which itself is not locally decodable.

== References ==

{{reflist}}