- Bar product (coding theory)
In
information theory , the bar product of twolinear code s "C"2 ⊆ "C"1 is defined as:C_1 | C_2 = { (c_1|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 word s in "C"1 are of length "n", then the code words in "C"1|"C"2 are of length 2"n".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 [cite book | author=F.J. MacWilliams | authorlink=Jessie MacWilliams | coauthors=N.J.A. Sloane | title=The Theory of Error-Correcting Codes | publisher=North-Holland | date=1977 | isbn=0-444-85193-3 | page=76 ] or ("u"|"u"+"v") construction [cite book | author=J.H. van Lint | title=Introduction to Coding Theory | edition=2nd ed | publisher=
Springer-Verlag | series=GTM | volume=86 | date=1992 | isbn=3-540-54894-7 | page=47 ] .Properties
Rank
The rank of the bar product is the sum of the two ranks:
:mbox{rank}(C_1|C_2) = mbox{rank}(C_1) + mbox{rank}(C_2),
Proof
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|x_i) mid 1leq i leq k } cup { (0|y_j) mid 1leq j leq l }
is a basis for the bar product C_1|C_2.
Hamming weight
The
Hamming weight "w" of the bar product is the lesser of (a) twice the weight of "C"1, and (b) the weight of "C"2::w(C_1|C_2) = min { 2w(C_1) , w(C_2) }. ,
Proof
For all c_1 in C_1,
:c_1|c_1 + 0 ) in C_1|C_2
which has weight 2w(c_1). Equally
:0|c_2) in C_1|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|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 ot=0 then::egin{matrix} w(c_1|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{matrix} If c_2=0 then:egin{matrix} w(c_1|c_1+c_2) &=& 2w(c_1) \ &geq& 2w(C_1) end{matrix}
so
:w(C_1|C_2) geq min { 2w(C_1) , w(C_2) }
ee also
*
Reed-Muller code References
Wikimedia Foundation. 2010.