In information theory , the bar product of two linear codes C 2 ⊆ C 1 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 C 1 are of length n , then the code words in C 1 | C 2 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 [ 1] u u v [ 2]
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})\,}
Let
{
x
1
,
…
,
x
k
}
{\displaystyle \{x_{1},\ldots ,x_{k}\}}
C
1
{\displaystyle C_{1}}
{
y
1
,
…
,
y
l
}
{\displaystyle \{y_{1},\ldots ,y_{l}\}}
C
2
{\displaystyle C_{2}}
{
(
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}}
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
{
2
w
(
C
1
)
,
w
(
C
2
)
}
.
{\displaystyle w(C_{1}\mid C_{2})=\min\{2w(C_{1}),w(C_{2})\}.\,}
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})}
(
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}}
w
(
c
2
)
{\displaystyle w(c_{2})}
c
1
∈
C
1
,
c
2
∈
C
2
{\displaystyle c_{1}\in C_{1},c_{2}\in C_{2}}
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}}
c
2
∈
C
2
{\displaystyle c_{2}\in C_{2}}
c
2
≠
0
{\displaystyle c_{2}\not =0}
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}
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})\}}
