Past exam of the mathematics course of the University of Cambridge / 2015 / ii / Paper 1 / 3G / Solution

For a block code, the minimum distance of a code is the minimum Hamming distance between distinct codewords, where Hamming distance counts positions in which two equal-length binary strings differ. We use equal-length codewords, so the fact that the codomain allows arbitrary finite strings creates no ambiguity. Minimum distance $\delta$ means every two distinct codewords differ in at least $\delta$ positions and some pair differs in exactly $\delta$.

Changing at most $\delta -1$ bits cannot turn a codeword into another codeword. Testing membership therefore detects every such nonzero error. For $t=\lfloor (\delta -1)/2\rfloor$, suppose a received word lies within distance $t$ of two codewords. The triangle inequality would put their mutual distance at most $2t<\delta$, a contradiction. Hence the radius-$t$ Hamming balls are disjoint and nearest-codeword decoding corrects all errors of weight at most $t$.

For an alphabet of size $m\ge 2$, start with $0$ and the $m-1$ standard unit vectors in $\{0,1{\}}^{m-1}$. Their minimum distance of a code is one. Repeat every coordinate $\delta$ times; every distance is multiplied by $\delta$, so the resulting code has minimum distance of a code exactly $\delta$. A one-letter alphabet has no pair of distinct codewords and therefore no finite minimum distance of a code under this definition; the construction concerns the usual nontrivial coding situation.