[{"@context":"http:\/\/schema.org\/","@type":"BlogPosting","@id":"https:\/\/wiki.edu.vn\/en\/wiki13\/locally-testable-code-wikipedia\/#BlogPosting","mainEntityOfPage":"https:\/\/wiki.edu.vn\/en\/wiki13\/locally-testable-code-wikipedia\/","headline":"Locally testable code – Wikipedia","name":"Locally testable code – Wikipedia","description":"before-content-x4 A locally testable code is a type of error-correcting code for which it can be determined if a string","datePublished":"2016-04-20","dateModified":"2016-04-20","author":{"@type":"Person","@id":"https:\/\/wiki.edu.vn\/en\/wiki13\/author\/lordneo\/#Person","name":"lordneo","url":"https:\/\/wiki.edu.vn\/en\/wiki13\/author\/lordneo\/","image":{"@type":"ImageObject","@id":"https:\/\/secure.gravatar.com\/avatar\/44a4cee54c4c053e967fe3e7d054edd4?s=96&d=mm&r=g","url":"https:\/\/secure.gravatar.com\/avatar\/44a4cee54c4c053e967fe3e7d054edd4?s=96&d=mm&r=g","height":96,"width":96}},"publisher":{"@type":"Organization","name":"Enzyklop\u00e4die","logo":{"@type":"ImageObject","@id":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","url":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","width":600,"height":60}},"image":{"@type":"ImageObject","@id":"https:\/\/wikimedia.org\/api\/rest_v1\/media\/math\/render\/svg\/e82ddbb2367033a1eacbd201fd49e8ea364c5a88","url":"https:\/\/wikimedia.org\/api\/rest_v1\/media\/math\/render\/svg\/e82ddbb2367033a1eacbd201fd49e8ea364c5a88","height":"","width":""},"url":"https:\/\/wiki.edu.vn\/en\/wiki13\/locally-testable-code-wikipedia\/","wordCount":9383,"articleBody":"     (adsbygoogle = window.adsbygoogle || []).push({});before-content-x4A locally testable code is a type of error-correcting code for which it can be determined if a string is a 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.       (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4In contrast, locally decodable codes use a small number of bits of the codeword to 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.[1]Clearly, any valid codeword should be accepted as a codeword, but strings that are not codewords could be only one bit off, which would require many (certainly more than a constant number) probes.  To account for this, testing failure is only defined if the string is off by at least a set fraction of its bits.  This implies words of the code must be longer than the input strings by adding some redundancy.       (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4Table of ContentsDefinition[edit]Connection with probabilistically checkable proofs[edit]Examples[edit]Hadamard code[edit]Long code[edit]See also[edit]References[edit]External links[edit]Definition[edit]To measure the distance between two strings, the Hamming distance is used\u0394(x,y)=|{i:xi\u2260yi}|{displaystyle Delta (x,y)=|{i:x_{i}neq y_{i}}|}The distance of a string        (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4w{displaystyle w} from a code C:{0,1}k\u2192{0,1}n{displaystyle C:{0,1}^{k}to {0,1}^{n}} is computed by\u0394(w,C)=minx{\u0394(w,C(x))}{displaystyle Delta (w,C)=min _{x}{Delta (w,C(x))}}Relative distances are computed as a fraction of the number of bits\u03b4(x,y)=\u0394(x,y)\/n\u00a0and\u00a0\u03b4(w,C)=\u0394(w,C)\/n{displaystyle delta (x,y)=Delta (x,y)\/n{text{ and }}delta (w,C)=Delta (w,C)\/n}A code C:{0,1}k\u2192{0,1}n{displaystyle C:{0,1}^{k}to {0,1}^{n}} is called q{displaystyle q}-local \u03b4{displaystyle delta }-testable if there exists a Turing machine M given random access to an input w{displaystyle w} that makes at most q{displaystyle q} non-adaptive queries of w{displaystyle w} and satisfies the following:[2]Also the rate of a code is the ratio between its message length and codeword lengthr=|x||C(x)|{displaystyle r={frac {|x|}{|C(x)|}}}It remains an open question whether there are any locally testable codes of linear size, but there are several constructions that are considered “nearly linear”:[3]Polynomial arbitrarily close to linear; for any "},{"@context":"http:\/\/schema.org\/","@type":"BreadcrumbList","itemListElement":[{"@type":"ListItem","position":1,"item":{"@id":"https:\/\/wiki.edu.vn\/en\/wiki13\/#breadcrumbitem","name":"Enzyklop\u00e4die"}},{"@type":"ListItem","position":2,"item":{"@id":"https:\/\/wiki.edu.vn\/en\/wiki13\/locally-testable-code-wikipedia\/#breadcrumbitem","name":"Locally testable code – Wikipedia"}}]}]