6 Hamming Bound
6.1 Overview
This chapter establishes the Hamming (sphere-packing) bound: for a code \(C\) of block-length \(n\) and minimum distance \(d\) over a \(q\)-ary alphabet \(\alpha \),
where \(\mathrm{Vol}(n,t) = \sum _{i=0}^{t}\binom {n}{i}(q-1)^i\).
6.2 Volume formula
Let \(\alpha \) be a finite alphabet, and regard a codeword of length \(n\) as a function \(\mathrm{Fin}\, n \to \alpha \), with the Hamming distance \(d(x,y)\) counting the coordinates in which two codewords differ. For every radius \(l\) and every center codeword \(c\), the Hamming ball \(B_l(c) = \{ c' : d(c',c) \le l\} \) has cardinality
where \(\left\lvert \alpha \right\rvert \) is the number of symbols in the alphabet.
6.3 Disjointness of decoding balls
Let \(C\) be a code of length \(n\) over a finite alphabet \(\alpha \) whose minimum Hamming distance is \(d\), with \(d \gt 0\); that is, some two distinct codewords of \(C\) lie at Hamming distance exactly \(d\), and no two distinct codewords lie at distance less than \(d\). Then for any two distinct codewords \(c_1, c_2 \in C\), the Hamming balls of radius \(\lfloor (d-1)/2 \rfloor \) centered at \(c_1\) and \(c_2\) are disjoint: no codeword \(c'\) satisfies both \(d(c', c_1) \le \lfloor (d-1)/2 \rfloor \) and \(d(c', c_2) \le \lfloor (d-1)/2 \rfloor \).
Let \(C\) be a code of length \(n\) over an alphabet \(\alpha \) whose minimum Hamming distance is \(d\), and suppose \(d \gt 0\). Write \(t = \left\lfloor \frac{d-1}{2} \right\rfloor \). Then for any two distinct codewords \(c_1, c_2 \in C\), the Hamming balls \(B_t(c_1)\) and \(B_t(c_2)\) of radius \(t\) centered at \(c_1\) and \(c_2\) are disjoint.
6.4 Hamming bound
Let \(\alpha \) be a finite alphabet with \(q = \left\lvert \alpha \right\rvert \gt 1\) symbols, and let \(C \subseteq \alpha ^n\) be a code (a finite set of length-\(n\) codewords) whose minimum Hamming distance is \(d\), with \(d \gt 0\). Then