Bar product explained

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

C _{1} \mid C _{2} = \{ (c _{1\mid} 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^[1] or (u | u + v) construction.^[2]

Properties

Rank

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

\operatorname{rank}(C _{1\mid} C _{2)} = \operatorname{rank}(C _{1)} + \operatorname{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\mid} x _{i)} \mid 1 \leq i \leq k \} \cup \{ ( 0 \mid y _{j)} \mid 1 \leq j \leq l \}

is a basis for the bar product

C _{1\mid} 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\mid} C _{2)} = min \{ 2 w(C _{1)} , w(C _{2)} \}.

Proof

For all

c _{1} \in C _{1} ,(c _{1\mid} c _{1} + 0 ) \in C _{1\mid} C _{2}

which has weight

2 w(c _{1)} . Equally( 0 \mid c _{2)} \in C _{1\mid} 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 havew(C _{1\mid} C _{2)} \leq min \{ 2 w(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{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

c _{2=0} then\begin{align} w(c _{1\mid} c _{1+c} _{2)} & = 2 w(c _{1)} \\ & \geq 2 w(C _{1) \end{align}}

so

w(C _{1\mid} C _{2)} \geq min \{ 2 w(C _{1)} , w(C _{2)} \}

See also

• Reed–Muller code

References

1. Book: Jessie MacWilliams

   . F.J. MacWilliams . Jessie MacWilliams . N.J.A. Sloane . The Theory of Error-Correcting Codes . registration . North-Holland . 1977 . 0-444-85193-3 . 76 .

2. Book: J.H. van Lint . Introduction to Coding Theory . 2nd . . . 86 . 1992 . 3-540-54894-7 . 47 .