Bar product

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

C1∣C2={(c1∣c1+c2):c1∈C1,c2∈C2},

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:

rank⁡(C1∣C2)=rank⁡(C1)+rank⁡(C2)

#### Proof

Let {x1,…,xk} be a basis for C1 and let {y1,…,yl} be a basis for C2. Then the set

{(xi∣xi)∣1≤i≤k}∪{(0∣yj)∣1≤j≤l}

is a basis for the bar product C1∣C2.

### 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(C1∣C2)=min⁡{2w(C1),w(C2)}.

#### Proof

For all c1∈C1,

(c1∣c1+0)∈C1∣C2

which has weight 2w(c1). Equally

(0∣c2)∈C1∣C2

for all c2∈C2 and has weight w(c2). So minimising over c1∈C1,c2∈C2 we have

w(C1∣C2)≤min⁡{2w(C1),w(C2)}

Now let c1∈C1 and c2∈C2, not both zero. If c2=0 then:

w(c1∣c1+c2)=w(c1)+w(c1+c2)≥w(c1+c1+c2)=w(c2)≥w(C2)

If c2=0 then

w(c1∣c1+c2)=2w(c1)≥2w(C1)

w(C1∣C2)≥min⁡{2w(C1),w(C2)}

## 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=32458"