1.4 Das Kugelvolumen abschätzen

Wir können die Ergebnisse der letzten beiden Teilkapitel so zusammenfassen: sei $C^{*} \subseteq {0, 1}^{n}$ ein größtmöglicher Code mit Blocklänge $n$ und Abstand $Δ (C^{*}) \geq d + 1$ . Dann gilt

\begin{array}{r} \frac{2^{n}}{Φ (n, d)} \leq | C^{*} | \leq \frac{2^{n}}{Φ (n, ⌊ \frac{d}{2} ⌋)} \end{array}

oder, logarithmisch ausgedrückt:

\begin{array}{r} (1) & 1 - \frac{\log_{2} Φ (n, d)}{n} \leq R (C^{*}) \leq 1 - \frac{\log_{2} Φ (n, ⌊ d / 2 ⌋)}{n} \end{array}

Wir werden nun einigermaßen scharfe Schranken für $Φ (n, r)$ herleiten, insbesondere wenn der Radius $r = ρ n$ linear in $n$ ist, was ja oben der Fall ist. Hierfür brauchen wir die binäre Entropiefunktion $H (x)$ :

\begin{aligned} H : [0, 1] & \to [0, 1] \\ p & \mapsto p \log_{2} (\frac{1}{p}) + (1 - p) \log_{2} (\frac{1}{1 - p}) . \end{aligned}

Hier sehen die den Graphen der Funktion:

Wichtig ist auch die Funktion $2^{H (p)}$ :

\begin{aligned} 2^{H (p)} & = {(\frac{1}{p})}^{p} {(\frac{1}{1 - p})}^{1 - p}, \end{aligned}

deren Graph auch recht ähnlich aussieht, nur etwas spitzer und mit Werten zwischen 1 und 2:

Theorem 1.4.1 Sei $r \in {1, \dots, n}$ und $ρ := r / n$ . Falls $ρ \leq 1 / 2$ ist, gilt

\begin{array}{r} \frac{1}{n + 1} 2^{n H (ρ)} \leq Φ (n, r) \leq 2^{n H (ρ)} \end{array}

Falls $ρ \geq 1 / 2$ ist, gilt $\frac{2^{n}}{n + 1} \leq Φ (n, r) \leq 2^{n}$ .

Beweis. Wir beweisen zuerst die obere Schranke. Wenn $ρ \geq 1 / 2$ ist, dann gilt $Φ (n, r) \leq 2^{n}$ trivialerweise. Betrachten wir also den Fall $ρ \leq 1 / 2$ . Nehmen wir eine Münze, die auf der einen Seite mit 1 und auf der anderen mit 0 beschriftet ist, die aber nicht fair ist: sie soll mit Wahrscheinlichkeit $ρ$ eine $1$ anzeigen. Wir werfen die Münze $n$ mal. Die Wahrscheinlichkeit, dass genau $k$ mal eine $1$ geworfen wurde, ist

\begin{array}{r} (\binom{n}{k}) ρ^{k} (1 - ρ)^{n - k} \end{array}

Die Wahrscheinlichkeit, dass höchstens $r$ Einsen geworfen wurden, ist

\begin{array}{r} (2) & \sum_{k = 0}^{r} (\binom{n}{k}) ρ^{k} (1 - ρ)^{n - k} \end{array}

Nun schrumpft $ρ^{k} (1 - ρ)^{n - k}$ mit wachsendem $k$ (da $ρ \leq 1 / 2$ ist) und somit gilt

\begin{array}{r} \sum_{k = 0}^{r} (\binom{n}{k}) ρ^{k} (1 - ρ)^{n - k} \geq \sum_{k = 0}^{r} (\binom{n}{k}) ρ^{d} (1 - ρ)^{n - r} = ρ^{d} (1 - ρ)^{n - r} Φ (n, r) \end{array}

Auf der anderen Seite ist ( $2$ ) ja eine Wahrscheinlichkeit und ist somit höchstens $1$ . Es gilt daher $ρ^{r} (1 - ρ)^{n - r} Φ (n, r) \leq 1$ . Wenn wir das nach $Φ (n, r)$ auflösen, erhalten wir

\begin{array}{r} Φ (n, r) \leq {(\frac{1}{ρ})}^{ρ n} {(\frac{1}{1 - ρ})}^{n - ρ n} = {[{(\frac{1}{ρ})}^{ρ} {(\frac{1}{1 - ρ})}^{1 - ρ}]}^{n} = 2^{H (ρ) n} \end{array}

Untere Schranke. Wir zeigen etwas stärkeres, nämlich eine untere Schranke für $(\binom{n}{r})$ , also die äußerste "Schale" der Hammingkugel. Wir betrachten wieder das Münzenszenario

\begin{array}{r} (\binom{n}{r}) ρ^{r} (1 - ρ)^{n - r} . \end{array}

Dies ist die Wahrscheinlichkeit, dass wir genau $r$ Einsen bekommen, wenn jede Münze uns mit Wahrscheinlichkeit $r / n$ eine Eins gibt. Im Erwartungswert bekommen wir natürlich genau $r$ Einsen, also ist es vielleicht gar nicht so unwahrscheinlich, dass wir genau $r$ Einsen bekommen. Und in der Tat: $r$ ist von allen Zahlen die wahrscheinlichste. Formal:

Behauptung. Sei $0 \leq k, r \leq n$ und $ρ = r / n$ . Dann gilt

\begin{array}{r} (\binom{n}{k}) ρ^{k} (1 - ρ)^{n - k} \leq (\binom{n}{r}) ρ^{r} (1 - ρ)^{n - r} . \end{array}

Beweis. Sei $T_{k} := (\binom{n}{k}) ρ^{k} (1 - ρ)^{n - k}$ . Wir vergleichen $T_{k}$ und $T_{k + 1}$ :

\begin{aligned} \frac{T_{k + 1}}{T_{k}} & = \frac{(\binom{n}{k + 1}) ρ^{k + 1} (1 - ρ)^{n - k - 1}}{(\binom{n}{k}) ρ^{k} (1 - ρ)^{n - k}} \\ = \frac{(\binom{n}{k + 1}) ρ}{(\binom{n}{k}) (1 - ρ)} \\ = \frac{n! ρ}{(k + 1)! (n - k - 1)!} \cdot \frac{k! (n - k)!}{n! (1 - ρ)} \\ = \frac{(n - k) ρ}{(k + 1) (1 - ρ)} \\ = \frac{(n - k) r}{(k + 1) (n - r)} \end{aligned}

Wenn nun also $k \geq r$ gilt dann ist $n - k \leq n - r$ und $k + 1 \geq r + 1$ und somit ist $\frac{T_{k + 1}}{T_{k}} < 1$ . Also $T_{r} > T_{r + 1} > T_{r + 2} > . . .$ . Ist nun aber $k \leq r - 1$ , dann gilt $n - k \geq n - r + 1$ und $k + 1 \leq r$ und somit ist $\frac{T_{k + 1}}{T_{k}} > 1$ . Daher: $T_{r} > T_{r - 1} > T_{r - 2} > \dots$ . Der Term $T_{r}$ ist also größer als jeder andere, und somit auch $T_{r} \geq T_{k}$ . $◻$

Da wir die Behauptung nun bewiesen haben, können wir folgern:

\begin{array}{r} \sum_{k = 0}^{n} (\binom{n}{k}) ρ^{k} (1 - ρ)^{n - k} = \sum_{k = 0}^{n} T_{k} \leq \sum_{k = 0}^{n} T_{r} = (n + 1) T_{r} . \end{array}

Auf der anderen Seite ist natürlich die linke Seite genau $1$ (das sehen Sie mit der binomischen Formel für $(ρ + (1 - ρ))^{n}$ oder einfach daran, dass es die Wahrscheinlichkeit ist, dass die Zahl der geworfenen Einsen zwischen $0$ und $n$ liegt), und somit gilt $1 \leq (n + 1) T_{r}$ , also

\begin{array}{r} (\binom{n}{r}) ρ^{r} (1 - ρ)^{n - r} = T_{r} \geq \frac{1}{n + 1} . \end{array}

Lösen wir nun nach $(\binom{n}{r})$ auf:

\begin{array}{r} (\binom{n}{r}) \geq \frac{1}{n + 1} {(\frac{1}{ρ})}^{r} {(\frac{1}{1 - ρ})}^{n - r} = \frac{1}{n + 1} 2^{H (ρ) n} . \end{array}

Da $Φ (n, r) \geq (\binom{n}{r})$ , haben wir die untere Schranke im Theorem bewiesen. $◻$

Da wir im Zusammenhang mit Codes und deren Rate (siehe ( $1$ )) interessiert sind, übersetzen wir das obige Theorem in seine logarithmische Variante:

Theorem (logarithmische Version) 1.4.2. Sei $r \leq n / 2$ und $ρ = r / n$ . Dann gilt

\begin{array}{r} H (ρ) - \frac{\log_{2} (n + 1)}{n} \leq \frac{\log_{2} Φ (n, r)}{n} \leq H (ρ) \end{array}

Wir haben nun also die relativ-logarithmische Größe von $Φ (n, r)$ bis auf einen $o (1)$ -Term festgenagelt. Fügen wir nun diese Schranke in ( $1$ ) ein:

Theorem 1.4.3 (Gilbert-Varshamov bound und Hamming bound, asymptotisch-logarithmische Version). Für $δ \in [0, 1]$ sei $C_{n}^{*} \subseteq {0, 1}^{n}$ ein größtmöglicher Code mit Blocklänge $n$ und Abstand $Δ (C_{n}^{*}) \geq δ n + 1$ . Dann gilt

\begin{array}{r} 1 - H (δ) \leq R (C^{*}) \leq 1 - H (\frac{δ}{2}) + o (1) \end{array}

Die Kurve, entlang der die Rate eines optimalen Codes verläuft, ist immer noch nicht bekannt. Allerdings werden wir im Verlauf des Seminars bessere Schranken kennenlernen und somit die "graue Zone" im obigen Bild verkleinern.