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 ∈ C 1 , c 2 ∈ C 2 } , {\displaystyle 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(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 or (u | u + v) construction.
Properties
Rank The rank of the bar product is the sum of the two ranks:
rank ( C 1 ∣ C 2 ) = rank ( C 1 ) + rank ( C 2 ) {\displaystyle \operatorname {rank} (C_{1}\mid C_{2})=\operatorname {rank} (C_{1})+\operatorname {rank} (C_{2})\,}
Proof Let { x 1 , … , x k } {\displaystyle \{x_{1},\ldots ,x_{k}\}} be a basis for C 1 {\displaystyle C_{1}} and let { y 1 , … , y l } {\displaystyle \{y_{1},\ldots ,y_{l}\}} be a basis for C 2 {\displaystyle C_{2}} . Then the set
{ ( x i ∣ x i ) ∣ 1 ≤ i ≤ k } ∪ { ( 0 ∣ y j ) ∣ 1 ≤ j ≤ l } {\displaystyle \{(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 ∣ C 2 {\displaystyle C_{1}\mid C_{2}} .
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 { 2 w ( C 1 ) , w ( C 2 ) } . {\displaystyle w(C_{1}\mid C_{2})=\min\{2w(C_{1}),w(C_{2})\}.\,}
Proof For all c 1 ∈ C 1 {\displaystyle c_{1}\in C_{1}} ,
( c 1 ∣ c 1 + 0 ) ∈ C 1 ∣ C 2 {\displaystyle (c_{1}\mid c_{1}+0)\in C_{1}\mid C_{2}}
which has weight 2 w ( c 1 ) {\displaystyle 2w(c_{1})} . Equally
( 0 ∣ c 2 ) ∈ C 1 ∣ C 2 {\displaystyle (0\mid c_{2})\in C_{1}\mid C_{2}}
for all c 2 ∈ C 2 {\displaystyle c_{2}\in C_{2}} and has weight w ( c 2 ) {\displaystyle w(c_{2})} . So minimising over c 1 ∈ C 1 , c 2 ∈ C 2 {\displaystyle c_{1}\in C_{1},c_{2}\in C_{2}} we have
w ( C 1 ∣ C 2 ) ≤ min { 2 w ( C 1 ) , w ( C 2 ) } {\displaystyle w(C_{1}\mid C_{2})\leq \min\{2w(C_{1}),w(C_{2})\}}
Now let c 1 ∈ C 1 {\displaystyle c_{1}\in C_{1}} and c 2 ∈ C 2 {\displaystyle c_{2}\in C_{2}} , not both zero. If c 2 ≠ 0 {\displaystyle c_{2}\not =0} then:
w ( c 1 ∣ c 1 + c 2 ) = w ( c 1 ) + w ( c 1 + c 2 ) ≥ w ( c 1 + c 1 + c 2 ) = w ( c 2 ) ≥ w ( C 2 ) {\displaystyle {\begin{aligned}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{aligned}}}
If c 2 = 0 {\displaystyle c_{2}=0} then
w ( c 1 ∣ c 1 + c 2 ) = 2 w ( c 1 ) ≥ 2 w ( C 1 ) {\displaystyle {\begin{aligned}w(c_{1}\mid c_{1}+c_{2})&=2w(c_{1})\\&\geq 2w(C_{1})\end{aligned}}}
so
w ( C 1 ∣ C 2 ) ≥ min { 2 w ( C 1 ) , w ( C 2 ) } {\displaystyle w(C_{1}\mid C_{2})\geq \min\{2w(C_{1}),w(C_{2})\}}
See also Reed–Muller code
References