1.1 Definitionen

Wir betrachten ${0, 1}^{n}$ , die Menge aller Bitstrings der Länge $n$ . Darauf ist ein Abstandsmaß definiert, der Hammingabstand:

\begin{array}{r} d_{H} (x, y) := | {i \in [n] | x_{i} \neq y_{i}} |, \end{array}

also die Anzahl der Stellen, an denen $x$ und $y$ sich unterscheiden. Wir wollen Datenpakete der Länge $m$ codieren als Pakete der Länge $n \geq m$ , sodass wir erkennen können, wenn bei der Übertragung Fehler aufgetreten sind, solange weniger als $d$ der $n$ Stellen fehlerhaft sind. Wir bezeichnen hier $x \in {0, 1}^{m}$ als Nachricht oder Urwort und $E (x)$ als das Codewort. Die Länge $n$ der Codewörter heißt Blocklänge des Codes. Formal also wollen wir eine Codierfunktion

\begin{array}{r} E : {0, 1}^{m} \to {0, 1}^{n} \end{array}

so dass sich $E (x)$ und $E (y)$ in mindestens $d$ Stellen unterscheiden:

\begin{array}{r} \forall x, y \in {0, 1}^{m}, x \neq y : d_{H} (E (x), E (y)) \geq d . \end{array}

Wir definieren den Minimalabstand von $E$ als

\begin{array}{r} Δ (E) := min_{x \neq y \in {0, 1}^{m}} d_{H} (E (x), E (y)) . \end{array}

Üblicherweise wollen wir, dass $Δ (E)$ proportional zur Blocklänge $n$ sind (z.B. weil wir erwarten, dass maximal jedes zehnte Bit korrumpiert wird). Daher betrachten wir $δ (E) := Δ (E) / n$ , den relativen Minimalabstand. Je größer dieser ist, desto besser. Der zweite Parameter eines Codes, der uns interessiert, ist die Rate, die misst, wie viele Nutzbits wir pro gesendetem Bit haben:

\begin{array}{r} R (E) := \frac{m}{n} . \end{array}

Eine Rate $R (E) = 1 / 2$ beispielsweise würde bedeuten, dass ein Codewort doppelt so lang ist wie ein Urwort. Auch bei $R (E)$ gilt: je größer, desto besser. Üblicherweise sind wir nicht mit einem konkreten $E : {0, 1}^{m} \to {0, 1}^{n}$ zufrieden, sondern wollen eine Lösung, die skalierbar ist; die uns erlaubt, beliebig lange Pakete zu codieren. Also eine Familie von Codes $E_{1}, E_{2}, \dots$ mit $E_{m} : {0, 1}^{m} \to {0, 1}^{n (m)}$ , wobei nun die Blocklänge $n (m)$ von $m$ abhängt. Oft sind wir allerdings schlampig und sprechen nur von einem Code $E : {0, 1}^{m} \to {0, 1}^{n}$ statt einer Familie $(E_{m})_{m \geq 1}$ von Codes.

Ziel. Wir wollen einen Code $E : {0, 1}^{m} \to {0, 1}^{n}$ oder besser gesagt eine Familie von Codes $E_{m} : {0, 1}^{m} \to {0, 1}^{n (m)}$ mit folgenden Eigenschaften:

$δ (E_{m}) \geq δ$ : der Code soll also einen konstanten Anteil fehlerhafter Bits tolerieren (d.h. erkennen) können;
$R (E_{m}) \geq r$ : die Anzahl der gesendeten Bits ( $n$ ) sind proportional zur Anzahl der Nutzbits ( $m$ );
$E$ soll effizient berechenbar sein, also zum Beispiel in Zeit $poly (m)$ .
Wir wollen die Umkehrfunktion $E^{- 1}$ effizient berechnen können. Und noch mehr: für ein Wort $z \in {0, 1}^{n}$ wollen wir effizient entscheiden können, ob $z \in img (E)$ liegt, ob $z$ also ein Codewort ist und wenn ja, welchem Urwort $x$ es entspricht, also $E (x) = z$ .
Noch mehr: falls es ein Codewort $z^{'} \in img (E)$ gibt mit $d_{H} (z, z^{'}) < 1 / 2$ (es kann höchstens ein solches geben), dann wollen wir $z^{'}$ und das $x^{'} \in {0, 1}^{m}$ mit $E (x^{'}) = z$ effizient finden können. Wir wollen den Fehler also nicht nur erkennen, sondern auch korrigieren können.

Codes als Teilmenge $C \subseteq {0, 1}^{n}$

Fürs erste interessieren uns nur die kombinatorischen Eigenschaften (1) und (2) der obigen Liste, also Rate und Abstand eines Codes. In diesem Falle ist es einfacher, die Menge der Codewörter $img (E)$ als Teilmenge $C \subseteq {0, 1}^{n}$ zu betrachten und ${0, 1}^{m}$ und $E$ fürs erste zu vergessen. Solange wir uns in diesem kombinatorischen Kontext befinden, ist ein Code einfach das: eine Teilmenge $C \subseteq {0, 1}^{n}$ .

Die Abstand von $C$ ist nun ganz analog definiert als

\begin{array}{r} Δ (C) := min {d_{H} (x, y) | x, y \in C, x \neq y} . \end{array}

Wie definieren wir die Rate? Den Wert $m$ gibt es ja nicht mehr. Im obigen Setting, also mit $E$ , gilt $C = img (E)$ und $| C | = 2^{m}$ (da $E$ injektiv ist, zumindest solange $Δ (E) \geq 1$ gilt). Daher $m = \log_{2} | C |$ , und somit definieren wir die Rate als

\begin{array}{r} R (C) := \frac{\log_{2} | C |}{n} . \end{array}

Codes über einem größeren Alphabet

Obwohl auf einem Computer oder bei den meisten Netzwerkprotokollen schlussendlich doch alles binär codiert wird, ist es nützlich, Codes über einem größeren Alphabet zu studieren. Also

\begin{array}{r} E : Σ_{1}^{m} \to Σ_{2}^{n} . \end{array}

Hamming-Abstand und Minimalabstand können wie zuvor definiert werden. Allerdings kann man die Rate nun nicht mehr als $m / n$ definieren. Wenn zum Beispiel $Σ_{1} = {0, 1}$ und $Σ_{2} = {00, 01, 10, 11}$ und wir $E : Σ_{1}^{2} \to Σ_{2}^{1}$ via $E (x, y) = x y$ definieren, dann ist $Δ (E) = 1$ und die Rate $R (E)$ wäre $m / n = 2 / 1 = 1$ . Wir hätten also eine Rate größer als $1$ , was unsinnig ist. Der Punkt: je größer $Σ$ ist, desto mehr Information trägt ein einzelnes Element daraus, und die Rate sollte das entsprechend reflektieren. Daher:

\begin{array}{r} R (E) := \frac{m \log | Σ_{1} |}{n \log | Σ_{2} |} . \end{array}

Für $Σ_{1} = Σ_{2} = {0, 1}$ stimmt das mit der vorherigen, obigen Definition überein. Eine andere Sichtweise: solagne $E : A \to B$ injektiv ist, gilt $| img (A) | = | A |$ und wir definieren die Rate von $E$ als

\begin{array}{r} \frac{\log_{2} | A |}{\log_{2} | B |}, \end{array}

also der (logarithmische) Anteil des Wertebereichs, der von $E$ tatsächlich genutzt wird.

1.1 Definitionen

Codes als Teilmenge C⊆{0,1}n

Codes über einem größeren Alphabet

Codes als Teilmenge $C \subseteq {0, 1}^{n}$