1.3 Obere Schranken: die Volumenschranke (Hamming bound)

Wir zeigen nun eine obere Schranke für die Größe, die ein Code $C \subseteq {0, 1}^{n}$ mit gegebenem Radius überhaupt haben kann.

Theorem 1.3.1 (Hamming bound). Ein Code $C \subseteq {0, 1}^{n}$ mit Abstand $Δ (C) \geq d + 1$ hat höchstens

\begin{array}{r} \frac{2^{n}}{Φ (n, ⌊ d / 2 ⌋)} \end{array}

Elemente.

Beweis. Wir verwenden ein einfaches Abzählargument. Als erstes setzen wir $r := ⌊ \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{array}{r} d_{H} (x, z) \leq r und d_{H} (y, z) \end{array}

gelten. Daher würde auch $d_{H} (x, y) \leq 2 r \leq d$ gelten. Dies widerspricht der Annahme, dass $Δ (C) \geq d + 1$ . $◻$

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{array}{r} | ⋃_{x \in C} B_{r} (x) | = \sum_{x \in C} | B_{r} (x) | = | C | Φ (n, r) . \end{array}

Auf der anderen Seite ist jede Kugel eine Teilmenge von ${0, 1}^{n}$ und somit ist auch $⋃_{x \in C} B_{r} (x) \subseteq {0, 1}^{n}$ . Wir schließen also, dass

\begin{array}{r} | C | Φ (n, r) \leq 2^{n} \end{array}

und somit $| C | \leq \frac{2^{n}}{Φ (n, r)}$ gilt. $◻$

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ß $Φ (n, d)$ in Abhängigkeit von $n$ und $d$ ist.