Bar product

In information theory, the bar product of two linear codes C2 ⊆ C1 is defined as

[math]\displaystyle{ C_1 \mid C_2 = \\{ (c_1\mid c_1+c_2) : c_1 \in C_1, c_2 \in C_2 \\}, }[/math]

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]

## Contents

* 1 Properties
* 1.1 Rank
* 1.1.1 Proof
* 1.2 Hamming weight
* 1.2.1 Proof
* 2 See also
* 3 References

## Properties

### Rank

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

[math]\displaystyle{ \operatorname{rank}(C_1\mid C_2) = \operatorname{rank}(C_1) + \operatorname{rank}(C_2)\, }[/math]

#### Proof

Let [math]\displaystyle{ \\{ x_1, \ldots , x_k \\} }[/math] be a basis for [math]\displaystyle{ C_1 }[/math] and let [math]\displaystyle{ \\{ y_1, \ldots , y_l \\} }[/math] be a basis for [math]\displaystyle{ C_2 }[/math]. Then the set

[math]\displaystyle{ \\{ (x_i\mid x_i) \mid 1\leq i \leq k \\} \cup \\{ (0\mid y_j) \mid 1\leq j \leq l \\} }[/math]

is a basis for the bar product [math]\displaystyle{ C_1\mid C_2 }[/math].

### 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:

[math]\displaystyle{ w(C_1\mid C_2) = \min \\{ 2w(C_1) , w(C_2) \\}. \, }[/math]

#### Proof

For all [math]\displaystyle{ c_1 \in C_1 }[/math],

[math]\displaystyle{ (c_1\mid c_1 + 0 ) \in C_1\mid C_2 }[/math]

which has weight [math]\displaystyle{ 2w(c_1) }[/math]. Equally

[math]\displaystyle{ (0\mid c_2) \in C_1\mid C_2 }[/math]

for all [math]\displaystyle{ c_2 \in C_2 }[/math] and has weight [math]\displaystyle{ w(c_2) }[/math]. So minimising over [math]\displaystyle{ c_1 \in C_1, c_2 \in C_2 }[/math] we have

[math]\displaystyle{ w(C_1\mid C_2) \leq \min \\{ 2w(C_1) , w(C_2) \\} }[/math]

Now let [math]\displaystyle{ c_1 \in C_1 }[/math] and [math]\displaystyle{ c_2 \in C_2 }[/math], not both zero. If [math]\displaystyle{ c_2\not=0 }[/math] then:

[math]\displaystyle{ \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} }[/math]

If [math]\displaystyle{ c_2=0 }[/math] then

[math]\displaystyle{ \begin{align} w(c_1\mid c_1+c_2) & = 2w(c_1) \\\ & \geq 2w(C_1) \end{align} }[/math]

[math]\displaystyle{ w(C_1\mid C_2) \geq \min \\{ 2w(C_1) , w(C_2) \\} }[/math]

## See also

* Reed–Muller code

## References

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

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Bar product. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Bar_product&oldid=3372562"