Exkurs: Fehlerkorrigierende Codes Lit.: MacWilliams, F.J., Sloane, N.J.A.: The Theory of Error-Correcting Codes, North-Holland, Amsterdam 1978. van Lint, J.H.: Introduction to Coding Theory (3. Aufl.), Springer 1999. Problem: bei der Übermittlung von Daten entstehen Fehler. Gesucht ist eine Methode, die die (meisten) Fehler automatisch korrigiert. Daten ⟶^{Kodierung} endl. Folge der Länge n von 0, 1 ⟶^{Übermittlung} fehlerhafter Folge von 0, 1 ⟶^{automat. Fehlerkorrektur} ursprüngl. Folge von 0, 1 ⟶^{Dekodierung} ursprüngl. Daten. Das kann nur funktionieren, wenn bei der Kodierung nur spezielle Folgen von 0, 1 (“die Wörter des Codes”) verwendet werden. Mathematische Formulierung:

{0, 1}^{n} = {(x_{1}, …, x_{n}) | x_{1} ∈ {0, 1}, …, x_{n} ∈ {0, 1}}

Folgen von 0, 1 der Länge n, z.B. (0, 1, 0, 1, 0, 1, 0) ∈ {0, 1}^{7} Hamming-Abstand d von Elementen x, y ∈ {0, 1}^{n}

d(x, y) = #{i | 1 ≤ i ≤ n und x_{i} ≠ y_{i}} (⇒ d(x, y) ∈ {0, …, n})

Dabei wird mit #M die Anzahl der Elemente einer Menge M bezeichnet. Bsp.: (n = 4) x = (0, 0, 1, 1), y = (0, 1, 1, 0) ⇒ d(x, y) = 2. Eigenschaften von d: ∀x, y, z ∈ {0, 1}^{n} gilt:

(i) d(x, y) ≥ 0 und d(x, y) = 0 ⇔ x = y

(ii) d(x, y) = d(y, x) (“Symmetrie”)

(iii) d(x, y) ≤ d(x, z) + d(z, y) (“Dreiecksungleichung”) (i)-(iii) ⇔ “d ist Abstandsfunktion” Zu x ∈ {0, 1}^{n}, t ∈ ℕ sei

B(x, t) = {y ∈ {0, 1}^{n} | d(x, y) ≤ t}

der (d-)Ball um x vom Radius t. Bem.: B(x, 1) enthält genau (n + 1) Elemente. (E1) Def.:

(i) Ein Code der Länge n ist eine Teilmenge C ≠ ∅ von {0, 1}^{n}.

(ii) Ein Code C heißt t-fehlerkorrigierend ⇔ Ist x ∈ C, y ∈ C, x ≠ y, so gilt B(x, t) ∩ B(y, t) = ∅.

Idee: Sei C t-fehlerkorrigierender Code. Als kodierte Nachrichten sind nur “Codewörter” x ∈ C erlaubt.

x ∈ C ⟶^{Übermittlung} \overline{x} ∈ \{0, 1\}^{n} ⟶^{automat. Korrektur} \overline{\overline{x}} ∈ C so, daß d(\overline{x}, \overline{\overline{x}}) minimal. Dann: Ist d(x, \overline{x}) ≤ t, so gilt \overline{\overline{x}} = x, da es nur ein x ∈ C mit d(\overline{x}, x) ≤ t gibt. D.h.: Sind bei der Übermittlung höchstens t Fehler aufgetreten, so ordnet die automatische Fehlerkorrektur der fehlerhaften Nachricht \overline{x} das ursprüngliche Codewort x zu. Bem.: 1) C ⊆ {0, 1}^{n} ist t-fehlerkorrigierend ⇔ Ist x ∈ C, y ∈ C und x ≠ y, so gilt d(x, y) ≥ 2t + 1 (Dreiecksungleichung!)

2) C ⊆ {0, 1}^{n} 1-fehlerkorriegierend ⇒ #C · (n + 1) ≤ 2^{n}(= #{0, 1}^{n}) Problem: Zeitaufwand Fehlerkorrektur ≈ #C · n ≈ 2^{n} Lineare Codes {0, 1}^{n} ist Vektorraum über dem Körper {0, 1} = ℤ_{2} (E2) Def. C ⊆ {0, 1}^{n} heißt linearer Code ⇔ C ist Unterraum von {0, 1}^{n} (⇔ \underline{0} ∈ C und ∀x, y ∈ C : x + y ∈ C) Sei p ∈ ℕ und n := 2^{p} − 1 (z.B. p = 5, n = 31 ⇒ 2^{n} = 3^{31} = 2 · (2^{10})^{3} = 2 · (1024)^{3} ≈ 2 · 10^{9}) Seien v_{1}, …, v_{n} die von \underline{0} ∈ \{0, 1\}^{p} verschiedenen Elemente von \{0, 1\}^{p} und F : \{0, 1\}^{n} → {0, 1}^{p} definiert durch

F (x_{1}, …, x_{n}) = x_{1}v_{1} + x_{2}v_{2} + … + x_{n}v_{n} ∈ {0, 1}^{p}

Dann gilt für alle x, y ∈ {0, 1}^{n} : F (x + y) = F (x) + F (y). Daraus folgt: C := \{x ∈ \{0, 1\}^{n} | F (x) = \underline{0}\} ist Unterraum (=linearer Code). C heißt der n’te Hammingcode. (E3) Satz. Der n’te Hammingcode ist ein 1-fehlerkorrigierender Code der Länge n

mit #C = \frac{2^{n}}{n + 1}(“C ist perfekt”)

Bew.: Seien x, y ∈ C, x ≠ y. Zu zeigen: d(x, y) ≥ 3

x, y ∈ C ⇒ (∗) (x_{1} − y_{1})v_{1} + … + (x_{n} − y_{n})v_{n} = \underline{0}.

Wegen x ≠ y existiert ein i ∈ \{1, …, n\} : x_{i} ≠ y_{i}. Dann (x_{i} − y_{i})v_{i} = v_{i} ≠ \underline{0}. Wegen (∗) existiert ein j ≠ i mit x_{j} ≠ y_{j}, also (x_{j} − y_{j})v_{j} = v_{j}. Wenn alle anderen Komponenten von x und y übereinstimmten, so wäre (∗) die Gleichung

v_{i} + v_{j} = \underline{0} Da in ℤ_{2} 1+1 = 0 gilt, gilt v +v = \underline{0} für alle v ∈ \{0, 1\}^{n}. D.h. aus v_{i} +v_{j} = \underline{0}, folgt v_{i} = v_{j}, im Widerspruch dazu, daß die v_{i} alle verschieden sind. Also gibt es mindestens eine weitere Komponente, in der x und y nicht übereinstimmen, d.h. d(x, y) ≥ 3, wie behauptet.

Ist x ∈ \{0, 1\}^{n} und F (x) ≠ \underline{0}, so gilt F (x) = v_{i} für ein i ∈ \{1, …, n\}. Daraus folgt F (x − e_{i}) = F (x) − F (e_{i}) = \underline{0}, d.h. x − e_{i} ∈ C und d(x, x − e_{i}) = 1. Also ⋃_{x∈C} B(x, 1) = {0, 1}^{n} und damit #C · (n + 1) = 2^{n}.

Algorithmus zur Korrektur \underline{eines} Fehlers:

Sei \overline{x} ∈ \{0, 1\}^{n} die empfangene Nachricht. Berechne F (\overline{x}) ∈ \{0, 1\}^{p}.

\begin{aligned}F (\overline{x}) = \underline{0} & ⇒ & \overline{\overline{x}} := \overline{x} \\ F (\overline{x}) = v_{i} & ⇒ & \overline{\overline{x}} := \overline{x} + e_{i} \end{aligned}

Zeitaufwand ≈ n^{2}p (= 31^{2} · 5 ≈ 5 · 10^{3}) ≪ 2^{n} ≈ 2 · 10^{9})