Bar product (coding theory)

From Wikipedia, the free encyclopedia

In information theory, the bar product of two linear codes C2 ⊆ C1 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 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).

Contents

[edit] Properties

[edit] 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)\,

[edit] Proof

Let \{ x_1, \ldots , x_k \} be a basis for C1 and let \{ y_1, \ldots , y_l \} be a basis for C2. 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 C1 | C2.

[edit] 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:

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

[edit] Proof

For all c_1 \in C_1,

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

which has weight 2w(c1). Equally

(0|c_2) \in C_1|C_2

for all c_2 \in C_2 and has weight w(c2). 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 c2 = 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) \}

[edit] See also