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:
“There is the falsely mystical view of art that assumes a kind of supernatural inspiration, a possession by universal forces unrelated to questions of power and privilege or the artist’s relation to bread and blood. In this view, the channel of art can only become clogged and misdirected by the artist’s concern with merely temporary and local disturbances. The song is higher than the struggle.”
—Adrienne Rich (b. 1929)
“No testing has overtaken you that is not common to everyone. God is faithful, and he will not let you be tested beyond your strength, but with the testing he will also provide the way out so that you may be able to endure it.”
—Bible: New Testament, 1 Corinthians 10:13.
“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)