Gibbs' inequality

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

$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 or (u | u + v) construction.

Properties

Rank

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

$\mathrm{rank}(C_1\mid C_2)=\mathrm{rank}(C_1)+\mathrm{rank}(C_2)$

Proof

Let $\{x_1,\dots ,x_k\}$ be a basis for $C_1$ and let $\{y_1,\dots ,y_l\}$ be a basis for $C_2$. Then the set

$\{(x_i\mid x_i)\mid 1\le i\le k\}\cup \{(0\mid y_j)\mid 1\le j\le l\}$

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 \{2w(C_1),w(C_2)\}.$

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)\le \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=0$ then:

$\begin{array}{rl}w(c_1\mid c_1+c_2)& =w(c_1)+w(c_1+c_2)\\ & \ge w(c_1+c_1+c_2)\\ & =w(c_2)\\ & \ge w(C_2)\end{array}$

If $c_2=0$ then

$\begin{array}{rl}w(c_1\mid c_1+c_2)& =2w(c_1)\\ & \ge 2w(C_1)\end{array}$

so

$w(C_1\mid C_2)\ge \min \{2w(C_1),w(C_2)\}$

See also

• Reed–Muller code