Bar Product (coding Theory)

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

:$C_1 \mid 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 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
or (''u'' ,  ''u'' + ''v'') construction.

Properties

Rank

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

:$\operatorname(C_1\mid C_2) = \operatorname(C_1) + \operatorname(C_2)\,$

Proof

Let $\$ be a basis for $C_1$ and let $\$ be a basis for $C_2$. Then the set

$\ \cup \$

is a basis for the bar product $C_1\mid C_2$.

Hamming weight

The Hamming weight ''w'' of the bar product is the lesser of (a) twice the weight of ''C''₁, and (b) the weight of ''C''₂:

:$w(C_1\mid C_2) = \min \. \,$

Proof

For all $c_1 \in C_1$,

:$(c_1\mid c_1 + 0 ) \in C_1\mid C_2$

which has weight $2w(c_1)$. Equally

:$(0\mid c_2) \in C_1\mid 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\mid C_2) \leq \min \$

Now let $c_1 \in C_1$ and $c_2 \in C_2$, not both zero. If $c_2\not=0$ then:

: $\begin 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$

If $c_2=0$ then

: $\begin w(c_1\mid c_1+c_2) & = 2w(c_1) \\ & \geq 2w(C_1) \end$

so

:$w(C_1\mid C_2) \geq \min \$

See also

* Reed–Muller code

References

{{DEFAULTSORT:Bar Product (Coding Theory)
Information theory
Coding theory