Content deleted Content added
Citation bot (talk | contribs) Removed parameters. | Use this bot. Report bugs. | #UCB_CommandLine |
m Disambiguating links to Code word (link changed to Code word (communication)) using DisamAssist. |
||
Line 1:
A '''locally testable code''' is a type of [[error-correcting code]] for which it can be determined if a [[String (computer science)|string]] is a [[Code word (communication)|word]] in that code by looking at a small (frequently constant) number of bits of the string. In some situations, it is useful to know if the data is corrupted without decoding all of it so that appropriate action can be taken in response. For example, in communication, if the receiver encounters a corrupted code, it can request the data be re-sent, which could increase the accuracy of said data. Similarly, in data storage, these codes can allow for damaged data to be recovered and rewritten properly.
In contrast, [[locally decodable code]]s use a small number of bits of the codeword to [[Probabilistic Turing Machine|probabilistically]] recover the original information. The fraction of errors determines how likely it is that the decoder correctly recovers the original bit; however, not all locally decodable codes are locally testable.<ref name=decNotTest>{{cite web|url=http://eccc.hpi-web.de/report/2010/130/revision/1/download/|title=Locally Testable vs. Locally Decodable Codes|first1=Tali|last1=Kaufman|first2=Michael|last2=Viderman}}</ref>
| |||