Bar product

From Wikipedia, the free encyclopedia
  (Redirected from Bar product (coding theory))
Jump to: navigation, search

In information theory, the bar product of two linear codes C2 ⊆ C1 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 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 (dr) 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[edit]

Rank[edit]

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

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

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

Proof[edit]

For all c_1 \in C_1,

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

which has weight 2w(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 have

w(C_1\mid 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{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) & = 2w(c_1) \\
& \geq 2w(C_1)
\end{align}

so

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

See also[edit]

References[edit]

  1. ^ F.J. MacWilliams; N.J.A. Sloane (1977). The Theory of Error-Correcting Codes. North-Holland. p. 76. ISBN 0-444-85193-3. 
  2. ^ J.H. van Lint (1992). Introduction to Coding Theory. GTM 86 (2nd ed ed.). Springer-Verlag. p. 47. ISBN 3-540-54894-7.