In information theory

Information theory

Information theory is a branch of applied mathematics and electrical engineering involving the quantification of information. Information theory was developed by Claude E. Shannon to find fundamental limits on signal processing operations such as compressing data and on reliably storing and...

, the bar product of two linear code

Linear code

In coding theory, a linear code is an error-correcting code for which any linear combination of codewords is also a codeword. Linear codes are traditionally partitioned into block codes and convolutional codes, although Turbo codes can be seen as a hybrid of these two types. Linear codes allow for...

s C₂ ⊆ C₁ is defined as
,

where (a|b) denotes the concatenation of a and b. If the code word

Code word

In communication, a code word is an element of a standardized code or protocol. Each code word is assembled in accordance with the specific rules of the code and assigned a unique meaning...

s in C₁ are of length n, then the code words in C₁|C₂ are of length 2n.

The bar product is an especially convenient way of expressing the Reed-Muller RM (d, r) code in terms of the Reed-Muller codes RM (d − 1, r) and RM (d − 1, r − 1).

The bar product is also referred to as the |u|u+v| construction
or (u|u+v) construction.

Rank

The rank

Dimension (vector space)

In mathematics, the dimension of a vector space V is the cardinality of a basis of V. It is sometimes called Hamel dimension or algebraic dimension to distinguish it from other types of dimension...

 of the bar product is the sum of the two ranks:

Proof

Let be a basis for and let be a basis for . Then the set



is a basis for the bar product .

Hamming weight

The Hamming weight

Hamming weight

The Hamming weight of a string is the number of symbols that are different from the zero-symbol of the alphabet used. It is thus equivalent to the Hamming distance from the all-zero string of the same length. For the most typical case, a string of bits, this is the number of 1's in the string...

w of the bar product is the lesser of (a) twice the weight of C₁, and (b) the weight of C₂:

Proof

For all ,


which has weight . Equally


for all and has weight . So minimising over we have


Now let and , not both zero. If then:
If then

so