Local Decoding and Testing of Codes
Sometimes it is only necessary to decode single bits of the message, or to check whether a given signal is a codeword, and do so without looking at the entire signal. This can make sense in a streaming setting, where codewords are too large to be classically decoded fast enough and where only a few bits of the message are of interest for now. Also such codes have become an important tool in computational complexity theory, e.g., for the design of probabilistically checkable proofs.
Locally decodable codes are error-correcting codes for which single bits of the message can be probabilistically recovered by only looking at a small (say constant) number of positions of a codeword, even after the codeword has been corrupted at some constant fraction of positions. Locally testable codes are error-correcting codes for which it can be checked probabilistically whether a signal is close to a codeword by only looking at a small number of positions of the signal.
Read more about this topic: Forward Error Correction
Famous quotes containing the words local, testing and/or codes:
“While it may not heighten our sympathy, wit widens our horizons by its flashes, revealing remote hidden affiliations and drawing laughter from far afield; humor, in contrast, strikes up fellow feeling, and though it does not leap so much across time and space, enriches our insight into the universal in familiar things, lending it a local habitation and a name.”
—Marie Collins Swabey. Comic Laughter, ch. 5, Yale University Press (1961)
“Now I see that going out into the testing ground of men it is the tongue and not the deed that wins the day.”
—Sophocles (497–406/5 B.C.)
“We must trust infinitely to the beneficent necessity which shines through all laws. Human nature expresses itself in them as characteristically as in statues, or songs, or railroads, and an abstract of the codes of nations would be an abstract of the common conscience.”
—Ralph Waldo Emerson (1803–1882)