Bar product

In information theory, the bar product of two linear codes C₂ ⊆ C₁ is defined as

${\displaystyle C_{1}\mid C_{2}=\{(c_{1}\mid c_{1}+c_{2}):c_{1}\in C_{1},c_{2}\in 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₁ are of length n, then the code words in C₁ | C₂ 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]

The rank of the bar product is the sum of the two ranks:

${\displaystyle \operatorname {rank} (C_{1}\mid C_{2})=\operatorname {rank} (C_{1})+\operatorname {rank} (C_{2}),円}${\displaystyle \operatorname {rank} (C_{1}\mid C_{2})=\operatorname {rank} (C_{1})+\operatorname {rank} (C_{2}),円}

Let ${\displaystyle \{x_{1},\ldots ,x_{k}\}}${\displaystyle \{x_{1},\ldots ,x_{k}\}} be a basis for ${\displaystyle C_{1}}${\displaystyle C_{1}} and let ${\displaystyle \{y_{1},\ldots ,y_{l}\}}${\displaystyle \{y_{1},\ldots ,y_{l}\}} be a basis for ${\displaystyle C_{2}}${\displaystyle C_{2}}. Then the set

${\displaystyle \{(x_{i}\mid x_{i})\mid 1\leq i\leq k\}\cup \{(0\mid y_{j})\mid 1\leq j\leq 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 ${\displaystyle C_{1}\mid 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₁, and (b) the weight of C₂:

${\displaystyle w(C_{1}\mid C_{2})=\min\{2w(C_{1}),w(C_{2})\}.,円}${\displaystyle w(C_{1}\mid C_{2})=\min\{2w(C_{1}),w(C_{2})\}.,円}

For all ${\displaystyle c_{1}\in C_{1}}${\displaystyle c_{1}\in C_{1}},

${\displaystyle (c_{1}\mid c_{1}+0)\in C_{1}\mid C_{2}}${\displaystyle (c_{1}\mid c_{1}+0)\in C_{1}\mid C_{2}}

which has weight ${\displaystyle 2w(c_{1})}${\displaystyle 2w(c_{1})}. Equally

${\displaystyle (0\mid c_{2})\in C_{1}\mid C_{2}}${\displaystyle (0\mid c_{2})\in C_{1}\mid C_{2}}

for all ${\displaystyle c_{2}\in C_{2}}${\displaystyle c_{2}\in C_{2}} and has weight ${\displaystyle w(c_{2})}${\displaystyle w(c_{2})}. So minimising over ${\displaystyle c_{1}\in C_{1},c_{2}\in C_{2}}${\displaystyle c_{1}\in C_{1},c_{2}\in C_{2}} we have

${\displaystyle w(C_{1}\mid C_{2})\leq \min\{2w(C_{1}),w(C_{2})\}}${\displaystyle w(C_{1}\mid C_{2})\leq \min\{2w(C_{1}),w(C_{2})\}}

Now let ${\displaystyle c_{1}\in C_{1}}${\displaystyle c_{1}\in C_{1}} and ${\displaystyle c_{2}\in C_{2}}${\displaystyle c_{2}\in C_{2}}, not both zero. If ${\displaystyle c_{2}\not =0}${\displaystyle c_{2}\not =0} then:

${\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}}}${\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 ${\displaystyle c_{2}=0}${\displaystyle c_{2}=0} then

${\displaystyle {\begin{aligned}w(c_{1}\mid c_{1}+c_{2})&=2w(c_{1})\\&\geq 2w(C_{1})\end{aligned}}}${\displaystyle {\begin{aligned}w(c_{1}\mid c_{1}+c_{2})&=2w(c_{1})\\&\geq 2w(C_{1})\end{aligned}}}

so

${\displaystyle w(C_{1}\mid C_{2})\geq \min\{2w(C_{1}),w(C_{2})\}}${\displaystyle w(C_{1}\mid C_{2})\geq \min\{2w(C_{1}),w(C_{2})\}}

• Reed–Muller code

• Information theory
• Coding theory