Past exam of the mathematics course of the University of Cambridge / 2019 / ii / Paper 1 / 11G (Coding and Cryptography)

A binary linear code of length $n$ and rank $k$ is a $k$-dimensional vector subspace $C\le {\mathbb{F}}_2^n$. Its minimum distance $d$ is the least Hamming weight of a nonzero codeword, equivalently the least Hamming distance between distinct codewords.

Delete any $d-1$ coordinates. The resulting puncturing mapis injective: if $\pi (x)=\pi (y)$ for distinct codewords, then the nonzero codeword $x-y$ is supported on at most $d-1$ coordinates, contradicting the minimum distance. Thuswhich is the Singleton bound

Let $S$ be the support of the weight-$d$ codeword $x$, and let ${\pi }_S$ delete all coordinates in $S$. Its kernel consists of codewords supported in $S$. If $0\ne y\in \ker {\pi }_S$, then $\mathrm{wt}(y)\ge d$ but $|S|=d$, so $y$ is nonzero in every coordinate of $S$. Over ${\mathbb{F}}_2$ this forces $y=x$. Hencehas dimension one, and the punctured code $C^{\prime }={\pi }_S(C)$ has length $n-d$ and rank $k-1$ by the rank-nullity theorem.

To bound its minimum distance, take $y\in C$ whose puncture $y^{\prime }$ is nonzero. If $y$ has $r$ nonzero coordinates in $S$, then $y+x$ has $d-r$ there, while both words have the same $\mathrm{wt}(y^{\prime })$ nonzero coordinates outside $S$. Both $y$ and $y+x$ are nonzero codewords, soAdding gives $2\mathrm{wt}(y^{\prime })\ge d$, and therefore

Apply part (b) repeatedly. After the first puncturing, the code has rank $k-1$, length $n-d$, and minimum distance at least $\lceil d/2\rceil$. Repeating with a minimum-weight codeword at each stage givesbecause nested ceilings obeyThuswhich is the binary Griesmer bound.