1. Einleitung: Zwei alltägliche und doch wundersame Meisterleistungen der Datenrekonstruktion

Sowohl in den Tiefen des interstellaren Raums als auch auf dem Display Ihres Smartphones vollbringt die moderne Informationstechnik täglich ein scheinbares physikalisches Wunder: die 100 % bitgenaue Wiederherstellung digitaler Informationen aus Signalen oder Datenträgern, die durch thermisches Rauschen, Kratzer oder physische Zerstörung massiv beschädigt wurden.

Wunder 1: Voyager 1 & 2 senden aus 24 Milliarden Kilometern mit $10^{-16}\text{ Watt}$

Die 1977 gestarteten NASA-Raumsonden Voyager 1 und Voyager 2 lieferten spektakuläre Nahaufnahmen von Jupiter, Saturn, Uranus und Neptun und befinden sich heute im interstellaren Raum in über 24 Milliarden Kilometern Entfernung von der Erde. Der Funksender an Bord von Voyager arbeitet mit einer Sendeleistung von lediglich $23\text{ Watt}$ – weniger als die Glühbirne in einem Haushaltskühlschrank. Wenn diese elektromagnetische Welle nach Milliarden Kilometern die 70-Meter-Parabolantennen des NASA Deep Space Network (DSN) auf der Erde erreicht, ist die Empfangsleistung auf rund $10^{-16}\text{ Watt}$ ($0{,}1\text{ Attowatt}$) abgefallen.

Bei $10^{-16}\text{ Watt}$ versinkt das Signal tief im thermischen Rauschen (Johnson-Nyquist-Rauschen) der Empfängerelektronik. Würde Voyager uncodierte Bildbits ($0$ und $1$) senden, würden Tausende Bits pro Sekunde zufällig kippen ($0 \leftrightarrow 1$). Dennoch empfing die Erde gestochen scharfe Farbporträts des Großen Roten Flecks des Jupiters und der Neptun-Atmosphäre ohne unkorrigierbare Bitfehler.

Wunder 2: Ein QR-Code, der zu $30\,\%$ durch einen Kaffeefleck oder ein Logo verdeckt ist

Betrachten wir nun das irdische Gegenstück: Sie richten Ihre Smartphone-Kamera auf einen QR-Code, dessen Ecke durch einen Kaffeefleck geschwärzt ist oder dessen Zentrum zu bis zu $30\,\%$ absichtlich durch ein Markenlogo überdeckt wurde. Innerhalb von weniger als $10\text{ Millisekunden}$ berechnet Ihr Smartphone die exakte URL oder Zahlungsinformation mit null Bitfehlern (Zero Bit Errors).

  flowchart TD
    subgraph Voyager["Tiefraum-Telemetrie (Voyager 1 & 2)"]
        V1["Planetenbild-Nutzdaten (k Bits)"] --> V2["Verkettete Codierung (Äußerer RS-Code + Innerer Faltungs-/LDPC-Code)"]
        V2 --> V3["23-W-Sender über Milliarden km (10⁻¹⁶ W Empfangsleistung)"]
        V3 --> V4["Massives thermisches Rauschen (AWGN) & Bit-Flips"]
        V4 --> V5["Soft-Decision-Viterbi / Belief Propagation + RS-Dekodierung"]
        V5 --> V6["Gestochen scharfes Planetenbild (Null Bitfehler)"]
    end
    subgraph QR["Alltäglicher QR-Code-Scan"]
        Q1["URL / Textdaten (k Bytes)"] --> Q2["GF(2⁸) Reed-Solomon-Codierung (n Bytes)"]
        Q2 --> Q3["Kaffeefleck oder Firmenlogo zerstört 30 % der Module"]
        Q3 --> Q4["Syndromberechnung + Berlekamp-Massey / Euklidischer Algorithmus"]
        Q4 --> Q5["Chien-Suche + Forney-Fehlerwertformel (10 ms)"]
        Q5 --> Q6["100 % bitgenaue Datenrekonstruktion"]
    end

Wie ist das mathematisch möglich? Die Antwort liegt in Claude Shannons Informationstheorie (1948) und der Algebra fehlerkorrigierender Codes (Error-Correcting Codes, ECC).

2. Claude Shannons Revolution von 1948 und das Kanalcodierungstheorem

2.1 Warum naive Wiederholungscodes ($0 \to 00000$) scheitern

Zwar gilt für $n \to \infty$ nach dem Gesetz der großen Zahlen $P_e^{(n)} \to 0$, doch gleichzeitig kollabiert die Coderate $R = k/n = 1/n \to 0$.

2.2 Shannons Kanalcodierungstheorem und das Shannon-Limit ($-1{,}59\,\text{dB}$)

1948 bewies Claude E. Shannon in seiner Arbeit “A Mathematical Theory of Communication” das Gegenteil:

Satz (Shannons Kanalcodierungstheorem, 1948): Jeder gedächtnislose verrauschte Kanal besitzt eine strikt positive Kanalkapazität $C$:

• Für den binären symmetrischen Kanal (BSC) mit Übergangswahrscheinlichkeit $p$ und binärer Entropiefunktion $H_2(p) = -p\log_2 p - (1-p)\log_2(1-p)$ gilt: $$C_{\text{BSC}}(p) = 1 - H_2(p) = 1 + p\log_2 p + (1-p)\log_2(1-p) \quad [\text{Bits / Kanalnutzung}]$$
• Für den AWGN-Kanal (Bandbreite $B$, Signalleistung $S$, Rauschleistung $N = N_0 B$) gilt nach dem Shannon-Hartley-Gesetz: $$C_{\text{AWGN}} = B \log_2\!\left(1 + \frac{S}{N}\right) = B \log_2\!\left(1 + \frac{S}{N_0 B}\right) \quad [\text{Bits / s}]$$

Für jede beliebige Übertragungsrate $R < C$ existieren Blockcodes der Länge $n \to \infty$, deren Dekodierfehlerwahrscheinlichkeit beliebig klein wird ($P_e \to 0$)!

3. Richard Hammings geometrischer Durchbruch (1950): Hamming-Distanz und der $[7, 4, 3]$-Code

3.1 Hamming-Distanz $d_H(\mathbf{u}, \mathbf{v})$ auf dem Hyperwürfel $\mathbb{F}_2^n$

Für einen Code $\mathcal{C} \subset \mathbb{F}_q^n$ mit Minimaldistanz $d_{\min} = \min_{\mathbf{u}\neq\mathbf{v}} d_H(\mathbf{u},\mathbf{v})$ beweist die Geometrie paarweise disjunkter Hamming-Kugeln vom Radius $t$:

• Fehlererkennung: bis zu $d_{\min} - 1$ Fehler;
• Auslöschungskorrektur (Erasures, Position bekannt): bis zu $e = d_{\min} - 1$ Auslöschungen;
• Fehlerkorrektur (Errors, Position unbekannt): bis zu $t = \lfloor(d_{\min} - 1)/2\rfloor$ beliebige Fehler. Zusammen mit der Hamming-Kugelpackungsschranke (Sphere-Packing Bound) gilt: $$\mathbf{d_{\min} \ge 2t + e + 1}, \qquad |\mathcal{C}| \cdot \sum_{i=0}^{t} \binom{n}{i} (q-1)^i \le q^n$$

3.2 Der perfekte Hamming-$(7,4)$-Code und die Syndromdekodierung

Ordnet man die Spalten von $\mathbf{H}$ als Binärzahlen $1 \dots 7$, gibt das Syndrom $\mathbf{s}$ bei einem Einzelfehler direkt den Binärindex $(1 \dots 7)$ des gekippten Bits aus! Genau diese Logik schützt heute jeden ECC-DRAM-Serverspeicher.

4. Reed und Solomons Meisterwerk (1960): Reed-Solomon-Codes über Galois-Feldern $\mathbb{F}_{2^m}$

4.1 Galois-Felder $\text{GF}(2^8)$ und Schutz gegen Bündelfehler (Burst Errors)

Kratzer auf optischen Medien oder Kaffeeflecken auf QR-Codes zerstören viele aufeinanderfolgende Bits (Bündelfehler / Burst Errors). Irving Reed und Gustave Solomon fassten 1960 jeweils $m=8$ Bits (1 Byte) zu einem einzigen Symbol im endlichen Galois-Feld $\text{GF}(2^8) = \mathbb{F}_2[x]/(x^8 + x^4 + x^3 + x^2 + 1)$ zusammen. Selbst wenn alle 8 Bits eines Bytes zerstört werden, ist dies in $\text{GF}(2^8)$ nur ein einziger Symbolfehler!

4.2 Polynominterpolation und die MDS-Singleton-Schranke $d_{\min} = n - k + 1$

Mit $n - k = 2t$ Paritätsbytes korrigiert ein RS-Code bis zu $e = n - k$ Auslöschungen (RAID-6, Cloud-Storage) oder bis zu $t = \lfloor(n-k)/2\rfloor$ unbekannte Symbolfehler (QR-Code Level H korrigiert 30 % Flächenverlust; Voyager nutzte den $[255, 223]$-RS-Code). Die Dekodierung löst über die Syndrome $S_j = y(\alpha^j)$ mittels Berlekamp-Massey- oder Euklidischem Algorithmus die Schlüsselgleichung $\Lambda(x)S(x) \equiv \Omega(x) \pmod{x^{2t}}$ nach dem Fehlerlokatorpolynom $\Lambda(x)$, bestimmt dessen Wurzeln per Chien-Suche und berechnet die Fehlerwerte über die Forney-Formel.

5. Annäherung an das Shannon-Limit: LDPC-Codes (1962), Turbo-Codes (1993) und Polar-Codes (2009)

1. Robert Gallagers LDPC-Codes (Low-Density Parity-Check, 1962): Nutzen eine dünnbesetzte Prüfmatrix $\mathbf{H}$ und einen bipartiten Tanner-Graphen. Durch iterativen Austausch weicher Log-Likelihood-Verhältnisse $L(c_i) = \ln\frac{P(c_i=0|y_i)}{P(c_i=1|y_i)}$ mittels Belief Propagation (Sum-Product-Algorithmus) nähern sich LDPC-Codes dem Shannon-Limit bis auf $0{,}0045\,\text{dB}$ und bilden das Rückgrat von 5G NR (Datenkanäle), Wi-Fi 6/7 und modernen 3D-NAND-SSDs.
2. Erdal Arıkans Polar-Codes (2009): Durch rekursive Anwendung der Kronecker-Transformation $\mathbf{G}_N = \mathbf{B}_N \begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix}^{\otimes m}$ entsteht Kanalpolarisierung (Channel Polarization): Für $N \to \infty$ konvergiert ein Anteil $C = I(W)$ der synthetischen Kanäle gegen Kapazität $1$ (rauschfrei, trägt Informationsbits), während der Anteil $1 - C$ gegen Kapazität $0$ konvergiert (Frozen Bits $= 0$). Polar-Codes sind die ersten konstruktiven Codes, die mit Komplexität $O(N \log N)$ beweisbar die Shannon-Kapazität erreichen, und sichern heute die 5G-NR-Steuerkanäle.

  flowchart TD
    subgraph Shannon["Moderne kapazitätserreichende Codes"]
        L1["LDPC-Codes (Dünnbesetzter bipartiter Tanner-Graph)"] --> L2["Iterativer Austausch weicher LLR-Nachrichten"]
        L2 --> L3["Sum-Product Belief Propagation (0,0045 dB vor dem Shannon-Limit)"]
        P1["Polar-Codes (Kronecker-Transformation G_N = B_N F^{⊗m})"] --> P2["Kanalpolarisierung in W⁻ (degradiert) und W⁺ (aufgewertet)"]
        P2 --> P3["Anteil C → Kapazität 1 (Datenbits), Anteil 1-C → Kapazität 0 (Frozen Bits)"]
    end

Vergleichstabelle der wichtigsten fehlerkorrigierenden Codes

6. Vollständige Python-Implementierung: Hamming $(7,4)$ & $\text{GF}(2^8)$ Reed-Solomon

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

from typing import List

def hamming74_demo() -> None:
    G = [[1,0,0,0,1,1,0], [0,1,0,0,1,0,1], [0,0,1,0,0,1,1], [0,0,0,1,1,1,1]]
    H = [[1,1,0,1,1,0,0], [1,0,1,1,0,1,0], [0,1,1,1,0,0,1]]
    msg = [1, 0, 1, 1]
    c = [sum(msg[i] * G[i][j] for i in range(4)) % 2 for j in range(7)]
    y = c.copy()
    y[2] ^= 1
    s = [sum(H[r][col] * y[col] for col in range(7)) % 2 for r in range(3)]
    err_idx = next(col for col in range(7) if [H[r][col] for r in range(3)] == s)
    y[err_idx] ^= 1
    print(f"[Hamming (7,4)] Syndrome={s} -> Flipped idx={err_idx}, Recovered={y[:4] == msg}")

class GF256:
    def __init__(self, poly: int = 0x11D) -> None:
        self.exp, self.log = [0] * 512, [0] * 256
        v = 1
        for i in range(255):
            self.exp[i] = self.exp[i + 255] = v
            self.log[v] = i
            v <<= 1
            if v & 0x100:
                v ^= poly

    def mul(self, a: int, b: int) -> int:
        return 0 if (a == 0 or b == 0) else self.exp[self.log[a] + self.log[b]]

    def inv(self, a: int) -> int:
        return self.exp[255 - self.log[a]]

    def power(self, a: int, p: int) -> int:
        return 1 if p == 0 else (0 if a == 0 else self.exp[(self.log[a] * p) % 255])

    def eval_poly(self, coeffs: List[int], x: int) -> int:
        res = 0
        for c in reversed(coeffs):
            res = self.mul(res, x) ^ c
        return res

    def solve(self, A: List[List[int]], b: List[int]) -> List[int]:
        n = len(b)
        M = [row[:] + [b[i]] for i, row in enumerate(A)]
        for col in range(n):
            piv = next(r for r in range(col, n) if M[r][col] != 0)
            M[col], M[piv] = M[piv], M[col]
            inv_p = self.inv(M[col][col])
            for j in range(col, n + 1):
                M[col][j] = self.mul(M[col][j], inv_p)
            for r in range(n):
                if r != col and M[r][col] != 0:
                    f = M[r][col]
                    for j in range(col, n + 1):
                        M[r][j] ^= self.mul(f, M[col][j])
        return [M[i][n] for i in range(n)]

def rs_demo() -> None:
    gf = GF256()
    text = "VOYAGER-1"
    k, t = len(text), 3
    n = k + 2 * t
    pts = [gf.exp[i] for i in range(n)]
    cw = [gf.eval_poly([ord(c) for c in text], x) for x in pts]
    rx = cw.copy()
    rx[1] ^= 0xFF; rx[6] ^= 0xA5; rx[13] ^= 0x3C
    A = [[gf.power(pts[i], d) for d in range(k + t)] + [gf.mul(rx[i], gf.power(pts[i], d)) for d in range(t)] for i in range(n)]
    b = [gf.mul(rx[i], gf.power(pts[i], t)) for i in range(n)]
    sol = gf.solve(A, b)
    E = sol[k + t:] + [1]
    err_pos = [i for i, x in enumerate(pts) if gf.eval_poly(E, x) == 0]
    valid = [(pts[i], rx[i]) for i in range(n) if i not in err_pos][:k]
    rec = gf.solve([[gf.power(x, d) for d in range(k)] for x, _ in valid], [y for _, y in valid])
    print(f"[RS(15,9) over GF(2^8)] Located Errors={err_pos}, Recovered='{''.join(chr(c) for c in rec)}'")

if __name__ == "__main__":
    hamming74_demo()
    rs_demo()

7. Fazit

Von Shannons Kanalkapazität $C$ und dem $-1{,}59\,\text{dB}$-Limit (1948) über Hammings Hyperwürfel-Geometrie (1950) und Reed-Solomons Polynominterpolation über Galois-Feldern $\mathbb{F}_{2^m}$ (1960) bis hin zu Gallagers LDPC-Belief-Propagation und Arıkans Kanalpolarisierung: Die Codierungstheorie ist der Triumph der reinen Mathematik über die physikalische Entropie.