Wir zeigen nun eine obere Schranke für die Größe, die ein Code $C \subseteq \cube^n$ mit gegebenem Radius überhaupt haben kann.
Theorem (Hamming bound). Ein Code $C \subseteq \cube^n$ mit Abstand $\Delta(C) \geq d+1$ hat höchstens
\begin{align*} \frac{2^n}{\Phi\left(n, \floor{d/2}\right)} \end{align*}Elemente.
Beweis. Wir verwenden ein einfaches Abzählargument. Als erstes setzen wir $r := \floor{\frac{d}{2}}$ und betrachten die Hammingkugeln $B_r(\x)$ für $\x \in C$.
Behauptung. Die Kugeln $B_r(\x)$ für $\x \in C$ sind paarweise disjunkt, d.h. überschneiden sich nicht.
Beweis. Seien $\x, \y \in C$ zwei verschiedene Codewörter. Wenn nun $B_r(\x)$ und $B_r(\y)$ sich überschneiden würden, es also ein $\z \in B_r(\x) \cap B_r(\y)$ gäbe, dann würde
\begin{align*} d_H(\x, \z) \leq r \textnormal{ und } d_H(\y, \z) \end{align*}gelten. Daher würde auch $d_H(\x, \y) \leq 2r \leq d$ gelten. Dies widerspricht der Annahme, dass $\Delta(C) \geq d+1$. \(\square\)
Nun wissen wir also, dass sich die Kugeln nicht überschneiden. Daher können wir das Gesamtvolumen berechnen, indem wir das Volumen aller Kugeln addieren, also
\begin{align*} \left|\bigcup_{\x \in C} B_r(\x)\right| = \sum_{\x \in C} |B_r(\x)| = |C| \Phi(n,r) \ . \end{align*}Auf der anderen Seite ist jede Kugel eine Teilmenge von $\cube^n$ und somit ist auch $\bigcup_{\x \in C} B_r(\x) \subseteq \cube^n$. Wir schließen also, dass
\begin{align*} |C| \Phi(n,r) \leq 2^n \end{align*}und somit $|C| \leq \frac{2^n}{\Phi(n,r)}$ gilt. \(\square\)
Wir haben in diesem Kapitel und dem vorherigen also eine erste obere und eine untere Schranke gezeigt. Um diese zu vergleichen, müssen wir verstehen, wie groß $\Phi(n,d)$ in Abhängigkeit von $n$ und $d$ ist.