5 Hamming Bound
5.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 \),
\[ |C| \; \cdot \; \mathrm{Vol}(n,\lfloor (d-1)/2\rfloor ) \; \le \; q^n, \]
where \(\mathrm{Vol}(n,t) = \sum _{i=0}^{t}\binom {n}{i}(q-1)^i\).
5.2 Volume formula
For any center \(c\) and radius \(l\),
\[ |B_l(c)| \; =\; \sum _{i=0}^{l} \binom {n}{i}\, (|\alpha |-1)^i. \]
5.3 Disjointness of decoding balls
If \(C\) has minimum distance \(d\gt 0\), then for distinct \(c_1,c_2\in C\),
\[ B_{\lfloor (d-1)/2\rfloor }(c_1) \; \cap \; B_{\lfloor (d-1)/2\rfloor }(c_2) \; =\; \varnothing . \]
Reformulation of the previous lemma as .
5.4 Hamming bound
Let \(q=|\alpha |\gt 1\). If \(C\subseteq \alpha ^n\) has minimum distance \(d\gt 0\), then
\[ |C| \; \le \; \frac{q^n}{\displaystyle \sum _{i=0}^{\lfloor (d-1)/2\rfloor }\binom {n}{i}(q-1)^i}. \]