Long code (mathematics)

In theoretical computer science and coding theory, the long code is an error-correcting code that is locally decodable. Long codes have an extremely poor rate, but play a fundamental role in the theory of hardness of approximation.

Definition

Let $f_{1},\dots ,f_{2^{n}}:\{0,1\}^{k}\to \{0,1\}$ for $k=\log n$ be the list of all functions from $\{0,1\}^{k}\to \{0,1\}$. Then the long code encoding of a message $x\in \{0,1\}^{k}$ is the string $f_{1}(x)\circ f_{2}(x)\circ \dots \circ f_{2^{n}}(x)$ where $\circ$ denotes concatenation of strings. This string has length Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 2^{n}=2^{2^{k}}} .

The Walsh-Hadamard code is a subcode of the long code, and can be obtained by only using functions Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle f_{i}} that are linear functions when interpreted as functions Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \mathbb {F} _{2}^{k}\to \mathbb {F} _{2}} on the finite field with two elements. Since there are only $2^{k}$ such functions, the block length of the Walsh-Hadamard code is $2^{k}$.

An equivalent definition of the long code is as follows: The Long code encoding of Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle j\in [n]} is defined to be the truth table of the Boolean dictatorship function on the Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle j} th coordinate, i.e., the truth table of $f:\{0,1\}^{n}\to \{0,1\}$ with Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle f(x_{1},\dots ,x_{n})=x_{j}} . Thus, the Long code encodes a $(\log n)$-bit string as a Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 2^{n}} -bit string.

Properties

The long code does not contain repetitions, in the sense that the function Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle f_{i}} computing the $i$th bit of the output is different from any function Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle f_{j}} computing the Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle j} th bit of the output for $j\neq i$. Among all codes that do not contain repetitions, the long code has the longest possible output. Moreover, it contains all non-repeating codes as a subcode.

Source

http://wikipedia.org/

See Also on BitcoinWiki

• DECOIN
• Arcona
• CloudFish
• MCB
• CoinCasso