Long code (mathematics)

Definition

Let f 1 , … , f 2 n : { 0 , 1 } k → { 0 , 1 } for k = log ⁡ n be the list of all functions from { 0 , 1 } k → { 0 , 1 } . Then the long code encoding of a message x ∈ { 0 , 1 } k is the string f 1 ( x ) ∘ f 2 ( x ) ∘ ⋯ ∘ f 2 n ( x ) where ∘ denotes concatenation of strings. This string has length 2 n = 2 2 k .

The Walsh-Hadamard code is a subcode of the long code, and can be obtained by only using functions f i that are linear functions when interpreted as functions F 2 k → 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 j ∈ [ 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 } n → { 0 , 1 } with f ( x 1 , … , x n ) = x i . 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 j ≠ 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.