Hamming and Gilbert Bounds

Hamming and Gilbert Bounds

Theorem (Hamming bound). For an \((n,k,d)\)-code, \[2^{k}\cdot \operatorname{Vol}\left(\left\lfloor \frac{d-1}{2}\right\rfloor\right) \le 2^{n} \ .\]

Proof. Indeed, \(2^{k}\) disjoint balls of radius \(\lfloor \frac{d-1}{2}\rfloor\) would otherwise not fit into \(\{0,1\}^{n}\).◼

From the Hamming bound one can formally derive what we discussed informally above: to be able to correct one error, the message must be lengthened by at least \(\log_{2}n\) bits. Indeed, \(\operatorname{Vol}(1)=n+1\) (the ball contains its center and \(n\) words obtained by flipping one coordinate). Therefore \(2^{k} \cdot (n+1) \le 2^{n}\). Taking logarithms gives \(k \le n - \log_{2}(n+1)\). Soon we will see how to achieve equality in this bound. For now we give a bound from the other side.

Theorem (Gilbert bound). If \[(2^{k}-1)\cdot \operatorname{Vol}\left(d-1\right) < 2^{n}\ ,\] then there exists an \((n,k,d)\)-code.

Proof. We add words to the code arbitrarily, ensuring that any two words have distance at least \(d\). If at some step we cannot add a word, then the whole space is covered by balls of radius \(d-1\). The inequality above guarantees that we make at least \(2^{k}\) steps, i.e., construct the code.◼