Quelle → Kanal: Zweistufige Codierung
Hammings Kapitel 10 beginnt mit Shannons Kommunikationsmodell, das auf jedes System anwendbar ist, das Informationen transportiert: Telefonanrufe, Radio, Festplatten, DNA-Replikation, Computerspeicher.
Die zweistufige Architektur
Stufe 1: Quellencodierung (Kompression). Konvertieren Sie die Quellennachricht in eine kompakte Darstellung. Ziel: Redundanz, die der Quelle eigen ist, entfernen. Morse-Code macht dies: häufige Buchstaben erhalten kurze Codes, seltene Buchstaben erhalten lange.
Stufe 2: Kanalcodierung (Fehlerschutz). Fügen Sie kontrollierte Redundanz hinzu, die den Rauschmerkmalen des Kanals angepasst ist. Eine verrauschte Telefonleitung benötigt mehr Redundanz als ein Glasfaserkabel. Die beiden Stufen entkoppeln: optimieren Sie jede unabhängig für ihre eigene Aufgabe.
Die gemeinsame Schnittstelle zwischen den beiden Stufen – ein standardisierter Bitstrom – bedeutet, dass jede Quelle mit jedem Kanal gekoppelt werden kann. Diese Modularität ist Shannons wichtigste architektonische Einsicht.
Speicher als Kommunikation. Hamming stellt fest, dass das Senden einer Nachricht durch den Raum (Übertragung) und das Senden durch die Zeit (Speicherung) das gleiche Modell verwenden. Ein Backup-Laufwerk ist ein verrauschter Kanal in der Zeit.
Die Rolle des Rauschens
Shannons Modell trifft eine radikale Annahme: Rauschen ist unvermeidlich. Jeder Kanal, jedes Speichermedium, jede Schaltung führt eine gewisse Fehlerwahrscheinlichkeit ein. Die Frage ist nicht 'wie eliminieren wir Rauschen?', sondern 'wie stellen wir die ursprüngliche Nachricht trotz Rauschen wieder her?'
Dies steht im Gegensatz zur klassischen Physik, in der Rauschen als Nachgedanke (das Unschärfeprinzip) auftritt. Shannon behandelt Rauschen als Grundbedingung – die gesamte Theorie baut darauf auf.
Für jetzt konzentriert sich Kapitel 10 auf den fehlerfreien Fall: Quellencodierung ohne Fehler. Das Kanalcodierungsproblem (Fehlerkorrektur) wartet auf spätere Kapitel.
Wann können Sie eindeutig decodieren?
Damit ein Code mit variabler Länge nützlich ist, muss der Empfänger einen Bitstrom eindeutig decodieren können. Hamming illustriert mit einem 4-Symbol-Code, der diesen Test nicht besteht, und führt dann die Lösung ein: präfixfreie Codes.
Präfixfreie Bedingung
Ein Code ist präfixfrei (oder instantan), wenn kein Codewort ein Präfix eines anderen Codewortes ist. Wenn Sie einen empfangenen Bitstrom erhalten, wissen Sie, dass ein Symbol geendet hat, sobald Sie ein Blatt im Decodierungsbaum erreichen – keine Vorausschau erforderlich.
Beispiel für einen präfixfreien Code für {s1, s2, s3, s4}: s1 = 0, s2 = 10, s3 = 110, s4 = 111.
Überprüfen: 0 ist kein Präfix von 10, 110 oder 111. 10 ist kein Präfix von 110 oder 111 (10 gefolgt von mehr Bits ergibt 100... oder 101..., von denen keines mit 110 oder 111 beginnt). Der Code erfüllt die Anforderungen.
Das Decodierungsverfahren: dem Baum folgen, bei jedem eingehenden Bit verzweigen, das Symbol ausgeben, wenn Sie ein Blatt erreichen, zur Wurzel zurückkehren.
Die Kraft-Ungleichung
Für jeden präfixfreien Binärcode mit Codewortlängen l_1, l_2, ..., l_n:
Σ 2^(−l_i) ≤ 1
Gleichheit gilt, wenn der Code vollständig ist (Blätter füllen den vollständigen Binärbaum ohne Lücken aus). Dies ist eine notwendige Bedingung: Kein präfixfreier Code kann sie verletzen. Umgekehrt existiert für jede Menge von Längen, die Krafts Ungleichung erfüllt, ein präfixfreier Code.
Krafts Ungleichung anwenden
Überprüfen Sie bei gegebenen Codewortlängen Kraft: Σ 2^(−l_i) ≤ 1.
Für {s1=0, s2=10, s3=110, s4=111}: Längen sind 1, 2, 3, 3.
Σ = 2^(−1) + 2^(−2) + 2^(−3) + 2^(−3) = 1/2 + 1/4 + 1/8 + 1/8 = 1. ✓
Shannon-Entropie
Die durchschnittliche Codewortlänge eines Codes mit variabler Länge: L = Σ p_i · l_i, wobei p_i die Wahrscheinlichkeit von Symbol s_i ist und l_i seine Codewortlänge ist.
Wie kurz kann L werden? Shannons Antwort: nicht unter der Quellenentropie.
Shannon-Entropie: H = −Σ p_i · log₂(p_i) (Einheiten: bits/Symbol)
Entropie misst die durchschnittliche Information pro Symbol. Hohe Entropie bedeutet, dass Symbole ungefähr gleich wahrscheinlich sind (maximale Unvorhersehbarkeit). Niedrige Entropie bedeutet, dass einige Symbole dominieren (hohe Vorhersehbarkeit, stärker komprimierbar).
Verlustfreier Codierungssatz
Für jeden präfixfreien Code gilt: H(source) ≤ L ≤ H(source) + 1.
Kein Code kann Entropie schlagen. Huffman-Codierung (nächstes Kapitel) erreicht die Obergrenze: L < H + 1. Für Blockcode über n Symbole wird die Grenze enger: H ≤ L/n < H + 1/n.
Entropie ist auch die theoretische Kompressionslimit: Sie können eine Quelle nicht unter H Bits pro Symbol komprimieren, ohne Informationen zu verlieren.
Entropie berechnen
Beispiel: 4 Symbole mit Wahrscheinlichkeiten p = [1/2, 1/4, 1/8, 1/8].
H = −(1/2)·log₂(1/2) − (1/4)·log₂(1/4) − (1/8)·log₂(1/8) − (1/8)·log₂(1/8)
= (1/2)·1 + (1/4)·2 + (1/8)·3 + (1/8)·3
= 0,5 + 0,5 + 0,375 + 0,375 = 1,75 bits/Symbol
Und der Huffman-Code {0, 10, 110, 111} erreicht L = 1,75 = H genau.
Warum Entropie eine Untergrenze ist
Die Untergrenze des verlustfreien Codierungssatzes ist nicht nur eine Formel – sie spiegelt etwas Tiefes über Information wider: Sie können nicht komprimieren, was bereits maximal unvorhersehbar ist.
Wenn alle Symbole gleich wahrscheinlich sind (gleichmäßige Verteilung), ist die Entropie H = log₂(n) für n Symbole. Ein Blockcode der Länge log₂(n) bits erreicht genau H. Kein Code kann besser sein.
Wenn ein Symbol dominiert (sagen wir, p(A) = 0,99, p(B) = 0,01), ist H klein – nahe bei 0. Ein Code mit variabler Länge kann A einen sehr kurzen Code zuweisen, den Strom sehr effizient codieren.
Das praktische Fazit: Große Kompressionsergebnisse existieren nur, wenn sich die Symbolwahrscheinlichkeiten erheblich unterscheiden. Wenn die Quelle bereits 'gleichmäßig' (zufällig aussehend) ist, bringt Huffman-Codierung nichts.