
Locally decodable
Encyclopedia
A locally decodable code is an error-correcting code that allows to decode a single bit of a message with high probability by only looking at a small number of bits of a possibly partially corrupted codeword.
The related locally testable code
s merely require that it can be locally detected whether a given message is close to a codeword, and in this sense locally decodable codes are a special case of locally testable codes.
More formally, a
-query locally decodable code encodes an
-bit message
by an
-bit codeword
such that any bit
of the message can be probabilistically recovered by querying only
bits of the codeword
, even if some constant fraction of the codeword has been corrupted.
is a simple, locally decodable code. It has an optimal
queries and a best possible decoding error. However, codewords of
-bit messages have exponential length
, which is why the Walsh–Hadamard code has a very inefficient rate.
If a received signal
agrees with some codeword
for some message
on at least a
fraction of bits, then
can be recovered from
with probability
.
The related locally testable code
Locally testable code
In theoretical computer science, a locally testable code is an error correcting code for which membership can be tested by a non-adaptive property testing algorithm. That is, locally testable codes have an efficient probabilistic algorithm that, based on its random bits, non-adaptively looks at few...
s merely require that it can be locally detected whether a given message is close to a codeword, and in this sense locally decodable codes are a special case of locally testable codes.
More formally, a








Examples
The Walsh–Hadamard code



If a received signal






