Past exam of the mathematics course of the University of Cambridge / 2010 / ii / Paper 3 / 4H / Solution

A linear code of length $n$ over ${\mathbb{F}}_q$ is a linear subspace $C\subseteq {\mathbb{F}}_q^n$. A parity-check matrix $P$ satisfies $C=\ker P$. Its minimum distance of a code is the least Hamming distance between distinct codewords, equivalently the least Hamming weight of a nonzero word, because differences remain in the code.

For the usual binary bar product of binary linear codes, take equal-length binary codes with $C_2\subseteq C_1$ and defineIt is linear, of length $2n$ and dimension $\dim C_1+\dim C_2$, since the parametrization is injective. If $v=0$ and the word is nonzero, its weight is $2\mathrm{wt}(u)\ge 2d(C_1)$. If $v\ne 0$, coordinatewise $\mathrm{wt}(u)+\mathrm{wt}(u+v)\ge \mathrm{wt}(v)\ge d(C_2)$. The words $(u,u)$ with $u$ of minimum nonzero weight and $(0,v)$ with $v$ of minimum weight achieve the two candidate bounds. ThusFor a word $(x,y)$, membership is equivalent to $P_{1}x=0$ and $P_2(x+y)=0$. Consequently a parity-check matrix of a bar product isThe same distance argument actually needs only equal block lengths and a common field, not nesting. Over a general field replace the second row block by $(-P_2,P_2)$, so it tests $y-x\in C_2$. The displayed binary construction uses the conventional nesting.