Bar product
In information theory, the bar product of two linear codes C2 ⊆ C1 is defined as
where (a | b) denotes the concatenation of a and b. If the code words in C1 are of length n, then the code words in C1 | C2 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[1] or (u | u + v) construction.[2]
Properties
Rank
The rank 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 w of the bar product is the lesser of (a) twice the weight of C1, and (b) the weight of C2:
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:
- Failed to parse (Missing <code>texvc</code> executable. Please see math/README to configure.): \begin{align} w(c_1\mid c_1+c_2) &= w(c_1) + w(c_1 + c_2) \\ & \geq w(c_1 + c_1 + c_2) \\ & = w(c_2) \\ & \geq w(C_2) \end{align}
If then
- Failed to parse (Missing <code>texvc</code> executable. Please see math/README to configure.): \begin{align} w(c_1\mid c_1+c_2) & = 2w(c_1) \\ & \geq 2w(C_1) \end{align}
so