Admin: Created page with "In theoretical computer science and coding theory, the '''long code''' is an error-correcting code that is locally decodable code|..."

2019-06-11T04:56:31Z

Created page with "In theoretical computer science and coding theory, the '''long code''' is an error-correcting code that is locally decodable code|..."

New page

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

==Definition==
Let <math>f_1,\dots,f_{2^n} : \{0,1\}^k\to \{0,1\}</math> for <math>k=\log n</math> be the list of ''all'' functions from <math>\{0,1\}^k\to\{0,1\}</math>.
Then the long code encoding of a message <math>x\in\{0,1\}^k</math> is the string <math>f_1(x)\circ f_2(x)\circ\dots\circ f_{2^n}(x)</math> where <math>\circ</math> denotes concatenation of strings.
This string has length <math>2^n=2^{2^k}</math>.

The [[Walsh-Hadamard code]] is a subcode of the long code, and can be obtained by only using functions <math>f_i</math> that are [[linear function]]s when interpreted as functions <math>\mathbb F_2^k\to\mathbb F_2</math> on the [[finite field]] with two elements. Since there are only <math>2^k</math> such functions, the block length of the Walsh-Hadamard code is <math>2^k</math>.

An equivalent definition of the long code is as follows:
The Long code encoding of <math>j\in[n]</math> is defined to be the truth table of the Boolean dictatorship function on the <math>j</math>th coordinate, i.e., the truth table of <math>f:\{0,1\}^n\to\{0,1\}</math> with <math>f(x_1,\dots,x_n)=x_j</math>.
Thus, the Long code encodes a <math>(\log n)</math>-bit string as a <math>2^n</math>-bit string.

==Properties==
The long code does not contain repetitions, in the sense that the function <math>f_i</math> computing the <math>i</math>th bit of the output is different from any function <math>f_j</math> computing the <math>j</math>th bit of the output for <math>j\neq i</math>.
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/ http://wikipedia.org/]

[[Category:Error-correcting codes]]
==See Also on BitcoinWiki==
* [[DECOIN]]
* [[Arcona]]
* [[CloudFish]]
* [[MCB]]
* [[CoinCasso]]

Long code (mathematics) - Revision history

Admin: Created page with "In theoretical computer science and coding theory, the '''long code''' is an error-correcting code that is locally decodable code|..."