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:
“Resorts advertised for waitresses, specifying that they “must appear in short clothes or no engagement.” Below a Gospel Guide column headed, “Where our Local Divines Will Hang Out Tomorrow,” was an account of spirited gun play at the Bon Ton. In Jeff Winney’s California Concert Hall, patrons “bucked the tiger” under the watchful eye of Kitty Crawhurst, popular “lady” gambler.”
—Administration in the State of Colo, U.S. public relief program (1935-1943)
“Is this testing whether I’m a replicant or a lesbian, Mr. Deckard?”
—David Webb Peoples, U.S. screenwriter, and Ridley Scott. Rachel, Blade Runner, being tested to determine if she is human or machine (1982)
“Thou hast a voice, great Mountain, to repeal
Large codes of fraud and woe; not understood
By all, but which the wise, and great, and good
Interpret, or make felt, or deeply feel.”
—Percy Bysshe Shelley (1792–1822)