1.2 Untere Schranken: die Greedy-Konstruktion (Gilbert-Varshamov bound)

Wir wollen nun einfach mal unsere Fühler ausstrecken und ein Gefühl dafür bekommen, wie groß ein Code $C \subseteq {0, 1}^{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 {0, 1}^{n}

mit

Δ (C) \geq d + 1

Initialisiere $C := \emptyset$ und $S := {0, 1}^{n}$
while $S \neq \emptyset$
1. $x :=$ ein beliebiges Element aus $S$
2. $C := C \cup {x}$
3. $S := S ∖ {y \in S | d_{H} (x, y) \geq d}$
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{array}{r} B_{d} (x) := {y \in {0, 1}^{n} | d_{H} (x, y) \leq d} . \end{array}

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 = 0 = 00 \dots 0$ , dan ist $B_{d} (0)$ die Menge der Bit-Vektoren, mit bis zu $d$ Einsen. Die Anzahl der Bitvektoren mit genau $k$ Einsen ist $(\binom{n}{k})$ , und somit ist

\begin{array}{r} | B_{d} (x) | = (\binom{n}{0}) + (\binom{n}{1}) + (\binom{n}{2}) + \dots + (\binom{n}{d}) =: Φ (n, d) . \end{array}

Jede Iteration von GreedyCode $(n, d)$ entfernt also $Φ (n, d)$ Elemente aus $S$ . Nein, das ist falsch: bis zu $Φ (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 $Φ (n, d)$ Elemente und somit durchläuft der Algorithmus mindestens

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

Iterationen. Daher gilt:

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

\begin{array}{r} R (C) \geq \frac{\log_{2} (\frac{2^{n}}{Φ (n, d)})}{n} = 1 - \frac{\log_{2} Φ (n, d)}{n} . \end{array}

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