In Kapitel 1.2 haben wir einen Code $C \in \cube^n$ mit Abstand $\Delta(C) \geq d+1$ und Größe $2^n / \Phi(n,d)$ konstruiert, indem wir "greedily" ein Codewort nach dem anderen hinzugefügt haben und in jedem Schritt alle "zu nahen" Wörter $\y \in \cube^n$ gelöscht haben. Der Nachteil dieser Konstruktion war ihre algorithmische Ineffizienz: die Laufzeit stand in Zusammenhang mit $2^n$, der Zahl aller möglichen Wörter. Wir wollen aber, dass die Zeit zum codieren polynomiell in der Blocklänge $n$ ist.
In diesem Teilkapitel zeigen wir die überraschende Tatsache, dass wir die untere Schranke von $2^n / \Phi(n,d)$ mit linearen Codes fast erreichen können. Und müssen uns dabei nicht einmal besonders anstrengen. Es reicht, die Matrix $G$ zufällig zu wählen.
Theorem Sei $\epsilon \gt 0$ und $n \in \N$. Sei
\begin{align*} k := \floor{\left(1 - \frac{\log_2 \Phi(n,d)}{n} - \epsilon\right) n} \end{align*}Wir bilden eine Matrix $G \in \F_2^{n \times k}$, indem wir jeden Eintrag zufällig aus $\{0,1\}$ wählen. Dann gilt
\begin{align*} \Pr[\Delta(G) \geq d+1] \geq 1 - 2^{-\epsilon n} \ . \end{align*}Falls $\Delta(G) \geq d+1$ gilt, dann ist $G$ (präziser: die durch $G$ definierte lineare Abbildung) injektiv und somit $|\img(G)| = 2^k$. Der durch $G$ definierte lineare Code hat also Rate $k/n$.
Beweis. Sei $\u \in \F_2^k \setminus \{\zero\}$ ein beliebiger Vektor. Als erstes werden wir sehen, dass $G \cdot \u$ gleichverteilt in $\F_2^n$ ist.
Behauptung. Sei $\u \in \F_2^k \setminus \{\zero\}$. Dann ist $G \cdot \u$ gleichverteilt in $\F_2^n$. Das heißt: für jedes $\x \in \F_2^n$ gilt
\begin{align*} \Pr_{G} [G \cdot \u = \x] = 2^{-n} \ . \end{align*}Beweis. Sei $l \in [k]$ der größte Index mit $u_{l} = 1$. Dieser existiert, weil ja $\u \ne \zero$ nach Annahme. Wir schreiben $G$ als $G = [ \mathbf{g}_1, \dots, \mathbf{g}_k]$, wobei jede Spalte $\mathbf{g}_j \in \F_2^n$ zufällig gewählt ist. Es gilt nun
\begin{align*} G \cdot \u = \sum_{i=1}^k \mathbf{g}_i u_i & = \left(\sum_{i=1}^{l-1} u_i \mathbf{g}_i\right) + u_l \mathbf{g}_l\\ & = \left(\sum_{i=1}^{l-1} u_i \mathbf{g}_i\right) + \mathbf{g}_l \end{align*}Wir stellen uns nun vor, dass wir $G$ bilden, indem wir die Spalten nacheinander zufällig wählen. Nachdem wir $\mathbf{g}_1, \dots, \mathbf{g}_{l-1}$ gewählt haben, pausieren wir. Ob nun $G \cdot \u = \x$ gilt oder nicht, hängt nur noch von der Wahl von $\mathbf{g}_l$ ab. In der Tat:
\begin{align*} G \cdot \u = \x & \Longleftrightarrow \left(\sum_{i=1}^{l-1} u_i \mathbf{g}_i\right) + \mathbf{g}_l = \x \\ & \Longleftrightarrow \mathbf{g}_l = \x - \left(\sum_{i=1}^{l-1} u_i \mathbf{g}_i\right) \ . \end{align*}Die rechte Seite ist nun, da wir $\mathbf{g}_1, \dots, \mathbf{g}_{l-1}$ bereits gewählt haben, ein fester Vektor in $\F_2^n$. Somit ist die Wahrscheinlichkeit, dass $\mathbf{g}_l$ genau dieser Vektor wird, genau $2^{-n}$. \(\square\)
Im Weiteren Verlauf werden wir Übungsaufgabe 1.5.1 verwenden: es gilt $\Delta(G) \leq d$ genau dann, wenn es ein Urwort $\u \ne \zero$ gibt mit $|G \cdot \u| \leq d$. Wir müssen nun zeigen, dass dies unwahrscheinlich ist. Sei $\mathcal{E}_{\u}$ das "schlechte" Ereignis, dass $|G \cdot \u| \leq d$ ist. Da $G \cdot \u$ gleichverteilt über $\F_2^n$ ist und es insgesamt $\Phi(n,d)$ viele Vektoren $\y \in \F_2^n$ mit $|\y| \leq d$ gibt, gilt
\begin{align*} \Pr[\mathcal{E}_{\u}] = \frac{\Phi(n,d)}{2^n} \ . \end{align*}Sei nun $\mathcal{E} := \bigcup_{\u \in \F_2^k} \mathcal{E}_{\u}$. Das ist das Ereignis, dass es überhaupt ein $\u \in \F_2^k \setminus \{\zero\}$ gibt mit $|G \cdot \u| \leq d$. Dass also $\Delta(G) \leq d$. Es gilt per "Union Bound":
\begin{align*} \Pr[\mathcal{E}] & = \Pr\left[ \bigcup_{\u \in \F_2^k} \mathbf{E}_{\u}\right] \\ & \leq \sum_{\u \in \F_2^k} \Pr[\mathcal{E}_{\u}] \\ & = \frac{2^k \Phi(n,d)}{2^n} \end{align*}Aus unserer Wahl $k := \floor{\left(1 - \frac{\log_2 \Phi(n,d)}{n} - \epsilon\right) n}$ folgt also
\begin{align*} \Pr[\mathcal{E}] & \leq \frac{2^k \Phi(n,d)}{2^n} \\ & \leq \frac{\left(2^n \Phi(n,d)^{-1} 2^{-\epsilon n}\right) \Phi(n,d)}{2^n} \\ & = 2^{-\epsilon n} \ , \end{align*} wie behauptet. \(\square\)Wir sind nun unserem Ziel näher gekommen: ein solcher Code für $d = \delta n$ hat Abstand mindestens $\delta n$ und Rate $1 - H(\delta) - \epsilon$. Die Codierungsfunktion lässt sich als Matrix $G \in \F_2^{n \times k}$ darstellen und somit in $O(nk)$ berechnen. Für festes $0 \lt \delta \lt 1/2$ ist dads $O(n^2)$. Können wir jetzt das Thema abhaken und nach Hause gehen? Naja, nicht ganz. Der so konstruierte Code hat immer noch einige Nachteile:
- Es ist immer unangenehm, von Zufall abhängig zu sein. Eine vollständig deterministische Konstruktion ist wünschenswert.
- Die Codierung (und bereits die Darstellung) benötigt $O(n^2)$ Platz. Wir hätten gerne eine Komplexität, die näher an $O(n)$ ist.
- Es ist gar nicht klar, wie man aus einem korrumpierten Codewort $\y$ das "richtige" Codewort $\x$ rekonstruiert; wie man den Code also effizient decodiert.