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:
“Savages cling to a local god of one tribe or town. The broad ethics of Jesus were quickly narrowed to village theologies, which preach an election or favoritism.”
—Ralph Waldo Emerson (1803–1882)
“Bourbon’s the only drink. You can take all that champagne stuff and pour it down the English Channel. Well, why wait 80 years before you can drink the stuff? Great vineyards, huge barrels aging forever, poor little old monks running around testing it, just so some woman in Tulsa, Oklahoma can say it tickles her nose.”
—John Michael Hayes (b.1919)
“I cannot help thinking that the menace of Hell makes as many devils as the severe penal codes of inhuman humanity make villains.”
—George Gordon Noel Byron (1788–1824)