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

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 -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.

Examples

The Walsh–Hadamard code 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 .