Wir wollen nun einfach mal unsere Fühler ausstrecken und ein Gefühl dafür bekommen, wie groß ein Code $C \subseteq \cube^n$ mit gegebenem Abstand denn werden kann. Dazu definieren wir einen "Algorithmus" GreedyCode, die wie folgt vorgeht: er wählt wiederholt ein Element $x$ aus und fügt es dem Code hinzu, markiert dann aber alles in einem Umkreis von $d$ um $x$ herum als gelöscht. So stellt er sicher, dass keine zwei Elemente Abstand $d$ oder kleiner haben. Der resultierende Code hat also Abstand mindestens $d+1$.

def GreedyCode$(n,d)$: // erzeugt einen Code $C \subseteq \cube^n$ mit $\Delta(C) \geq d+1$
  1. Initialisiere $C := \emptyset$ und $S := \cube^n$
  2. while $S \ne \emptyset$
    1. $x := $ ein beliebiges Element aus $S$
    2. $C := C \cup \{x\}$
    3. $S := S \setminus \{y \in S \ | \ d_H(x,y) \geq d\}$
  3. return $C$

Hier sehen Sie eine Klick-Animation, die versucht, diesen Prozess aus dem $n$-dimensionalen Hyperwürfel im zweidimensionalen Raum darzustellen:

Die Menge der Elemente im Umkreis $d$ um einen Punkt $\x$ nennt man die Hammingkugel (englsich: Hamming ball) vom Radius $d$ um $\x$.

\begin{align*} B_d(\x) := \{\y \in \cube^n \ | \ d_H(x,y) \leq d\} \ . \end{align*}

Das "Volumen" einer Hammingkugel ist offensichtlich unabhängig von der Lage des "Mittelpunktes" $\x$ und allein durch die Dimension $n$ und den Radius $d$ bestimmt. Nehmen wir also $\x = \mathbf{0} = 00\dots0$, dan ist $B_d(\mathbf{0})$ die Menge der Bit-Vektoren, mit bis zu $d$ Einsen. Die Anzahl der Bitvektoren mit genau $k$ Einsen ist ${n \choose k}$, und somit ist

\begin{align*} |B_d(\x)| = {n \choose 0} + {n \choose 1} + {n \choose 2} + \cdots + {n \choose d} =: \Phi(n,d) \ . \end{align*}

Jede Iteration von GreedyCode$(n,d)$ entfernt also $\Phi(n,d)$ Elemente aus $S$. Nein, das ist falsch: bis zu $\Phi(n,d)$ Elemente, denn manche sind ja vielleicht bereits zuvor entfernt worden. In jedem Fall schrumpft die Menge $S$ in jeder Iteration um höchstens $\Phi(n,d)$ Elemente und somit durchläuft der Algorithmus mindestens

\begin{align*} \frac{2^n}{\Phi(n,d)} \end{align*}

Iterationen. Daher gilt:

Theorem (Gilbert-Varshamov bound). Der Algorithmus GreedyCode$(n,d)$ erzeugt einen Code $C$ mit $\Delta(C) \geq d+1$ und $|C| \geq \frac{2^n}{\Phi(n,d)}$. Die Rate ist also mindestnes

\begin{align*} R(C) \geq \frac{\log_2 \pfrac{2^n}{\Phi(n,d)}}{n} = 1 - \frac{\log_2 \Phi(n,d)}{n} \ . \end{align*}

Um zu verstehen, ob das jetzt gut ist oder nicht, müssen wir untersuchen, wie groß $\Phi(n,d)$ ist - das heißt, wir brauchen eine Näherungsformel für $\Phi(n,d)$.