Long code (mathematics)

In 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 .

1 Definition
2 Properties
3 Source
4 See Also on BitcoinWiki

Definition

Let $f_1,dots,f_{2^n} : {0,1}^kto {0,1}$ for $k=log n$ be the list of all functions from ${0,1}^kto{0,1}$ . Then the long code encoding of a message $xin{0,1}^k$ is the string $f_1(x)circ f_2(x)circdotscirc f_{2^n}(x)$ where $circ$ denotes concatenation of strings. This string has length $2^n=2^{2^k}$ .

The is a subcode of the long code, and can be obtained by only using functions $f_i$ that are when interpreted as functions $mathbb F_2^ktomathbb F_2$ on the 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 $jin[n]$ is defined to be the truth table of the Boolean dictatorship function on the $j$ th coordinate, i.e., the truth table of $f:{0,1}^nto{0,1}$ with $f(x_1,dots,x_n)=x_j$ . Thus, the Long code encodes a $(log n)$ -bit string as a $2^n$ -bit string.

Properties

The long code does not contain repetitions, in the sense that the function $f_i$ computing the $i$ th bit of the output is different from any function $f_j$ computing the $j$ th bit of the output for $jneq 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/

Long code (mathematics)

Contents

Definition

Properties

Source

See Also on BitcoinWiki