1.6 Lineare Codes existieren

In Kapitel 1.2 haben wir einen Code $C \in {0, 1}^{n}$ mit Abstand $Δ (C) \geq d + 1$ und Größe $2^{n} / Φ (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 {0, 1}^{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} / Φ (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 1.6.1 Sei $ϵ > 0$ und $n \in N$ . Sei

\begin{array}{r} k := ⌊ (1 - \frac{\log_{2} Φ (n, d)}{n} - ϵ) n ⌋ \end{array}

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{array}{r} Pr [Δ (G) \geq d + 1] \geq 1 - 2^{- ϵ n} . \end{array}

Falls $Δ (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} ∖ {0}$ 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} ∖ {0}$ . Dann ist $G \cdot u$ gleichverteilt in $F_{2}^{n}$ . Das heißt: für jedes $x \in F_{2}^{n}$ gilt

\begin{array}{r} \underset{G}{Pr} [G \cdot u = x] = 2^{- n} . \end{array}

Beweis. Sei $l \in [k]$ der größte Index mit $u_{l} = 1$ . Dieser existiert, weil ja $u \neq 0$ nach Annahme. Wir schreiben $G$ als $G = [g_{1}, \dots, g_{k}]$ , wobei jede Spalte $g_{j} \in F_{2}^{n}$ zufällig gewählt ist. Es gilt nun

\begin{aligned} G \cdot u = \sum_{i = 1}^{k} g_{i} u_{i} & = (\sum_{i = 1}^{l - 1} u_{i} g_{i}) + u_{l} g_{l} \\ = (\sum_{i = 1}^{l - 1} u_{i} g_{i}) + g_{l} \end{aligned}

Wir stellen uns nun vor, dass wir $G$ bilden, indem wir die Spalten nacheinander zufällig wählen. Nachdem wir $g_{1}, \dots, 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 $g_{l}$ ab. In der Tat:

\begin{aligned} G \cdot u = x & ⟺ (\sum_{i = 1}^{l - 1} u_{i} g_{i}) + g_{l} = x \\ ⟺ g_{l} = x - (\sum_{i = 1}^{l - 1} u_{i} g_{i}) . \end{aligned}

Die rechte Seite ist nun, da wir $g_{1}, \dots, g_{l - 1}$ bereits gewählt haben, ein fester Vektor in $F_{2}^{n}$ . Somit ist die Wahrscheinlichkeit, dass $g_{l}$ genau dieser Vektor wird, genau $2^{- n}$ . $◻$

Im Weiteren Verlauf werden wir Übungsaufgabe 1.5.1 verwenden: es gilt $Δ (G) \leq d$ genau dann, wenn es ein Urwort $u \neq 0$ gibt mit $| G \cdot u | \leq d$ . Wir müssen nun zeigen, dass dies unwahrscheinlich ist. Sei $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 $Φ (n, d)$ viele Vektoren $y \in F_{2}^{n}$ mit $| y | \leq d$ gibt, gilt

\begin{array}{r} Pr [E_{u}] = \frac{Φ (n, d)}{2^{n}} . \end{array}

Sei nun $E := ⋃_{u \in F_{2}^{k}} E_{u}$ . Das ist das Ereignis, dass es überhaupt ein $u \in F_{2}^{k} ∖ {0}$ gibt mit $| G \cdot u | \leq d$ . Dass also $Δ (G) \leq d$ . Es gilt per "Union Bound":

\begin{aligned} Pr [E] & = Pr [⋃_{u \in F_{2}^{k}} E_{u}] \\ \leq \sum_{u \in F_{2}^{k}} Pr [E_{u}] \\ = \frac{2^{k} Φ (n, d)}{2^{n}} \end{aligned}

Aus unserer Wahl $k := ⌊ (1 - \frac{\log_{2} Φ (n, d)}{n} - ϵ) n ⌋$ folgt also

\begin{aligned} Pr [E] & \leq \frac{2^{k} Φ (n, d)}{2^{n}} \\ \leq \frac{(2^{n} Φ (n, d)^{- 1} 2^{- ϵ n}) Φ (n, d)}{2^{n}} \\ = 2^{- ϵ n}, \end{aligned}

wie behauptet.

◻

Wir sind nun unserem Ziel näher gekommen: ein solcher Code für $d = δ n$ hat Abstand mindestens $δ n$ und Rate $1 - H (δ) - ϵ$ . Die Codierungsfunktion lässt sich als Matrix $G \in F_{2}^{n \times k}$ darstellen und somit in $O (n k)$ berechnen. Für festes $0 < δ < 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.