Bar product (coding theory)

In information theory, the bar product of two linear codes C₂ ⊆ C₁ is defined as

$C_1 | C_2 = \{ (c_1|c_1+c_2) : c_1 \in C_1, c_2 \in C_2 \}$,

where (a|b) denotes the concatenation of a and b. If the code words 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.

Properties

Rank

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

$\mbox{rank}(C_1|C_2) = \mbox{rank}(C_1) + \mbox{rank}(C_2)\,$

Proof

Let $\{ x_1, \ldots , x_k \}$ be a basis for $C_1$ and let $\{ y_1, \ldots , y_l \}$ be a basis for $C_2$. Then the set

$\{ (x_i|x_i) \mid 1\leq i \leq k \} \cup \{ (0|y_j) \mid 1\leq j \leq l \}$

is a basis for the bar product $C_1|C_2$.

Hamming weight

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

$w(C_1|C_2) = \min \{ 2w(C_1) , w(C_2) \}. \,$

Proof

For all $c_1 \in C_1$,

$(c_1|c_1 + 0 ) \in C_1|C_2$

which has weight $2w(c_1)$. Equally

$(0|c_2) \in C_1|C_2$

for all $c_2 \in C_2$ and has weight $w(c_2)$. So minimising over $c_1 \in C_1, c_2 \in C_2$ we have

$w(C_1|C_2) \leq \min \{ 2w(C_1) , w(C_2) \}$

Now let $c_1 \in C_1$ and $c_2 \in C_2$, not both zero. If $c_2\not=0$ then:

$\begin{matrix} w(c_1|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{matrix}$

If $c_2=0$ then

$\begin{matrix} w(c_1|c_1+c_2) &=& 2w(c_1) \\ &\geq& 2w(C_1) \end{matrix}$

so

$w(C_1|C_2) \geq \min \{ 2w(C_1) , w(C_2) \}$

See also

• Reed-Muller code