Bar product (coding theory)
From Wikipedia, the free encyclopedia
In information theory, the bar product of two linear codes C2 ⊆ C1 is defined as
,
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:
[edit] Proof
Let 
be a basis for C1 and let 
be a basis for C2. Then the set
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:
[edit] Proof
For all 
,
which has weight 2w(c1). Equally
for all 
and has weight w(c2). So minimising over 
we have
Now let and , not both zero. If 
then:
If c2 = 0 then
so
