Quelle → Kanal: Zweistufige Codierung
Hamming's Kapitel 10 beginnt mit Shannons Kommunikationsmodell, das für jedes System gilt, das Informationen überträgt: Telefonate, Radio, Festplatten, DNA-Replikation, Computer-Speicher.
Die Zweistufige Architektur
Stufe 1: Quellcodierung (Kompression). Wandeln Sie die Quellnachricht in eine kompakte Darstellung um. Ziel: Entfernen Sie Redundanz, die dem Quellmedium eigen ist. Morse-Code tut dies: häufige Buchstaben erhalten kurze Codes, seltene Buchstaben lange Codes.
Stufe 2: Kanalcodierung (Fehlerschutz). Fügen Sie kontrollierte Redundanz hinzu, die den Merkmale der Kanalrauschen entspricht. Ein rauschiger Telefonzugang benötigt mehr Redundanz als ein Glasfaserkabel. Die beiden Stufen sind voneinander unabhängig: optimieren Sie jede für ihre eigene Aufgabe.
Die gemeinsame Schnittstelle zwischen den beiden Stufen - ein standardisierter Bitstrom - bedeutet, dass jede Quelle mit jeder Kanalverbindung kombiniert werden kann. Dies ist Shannons entscheidender architektonischer Einblick.
Speicherung als Kommunikation. Hamming bemerkt, dass das Senden einer Nachricht durch Raum (Übertragung) und das Senden durch Zeit (Speicherung) das gleiche Modell verwenden. Eine Sicherheitskopie ist ein rauschiger Kanal in der Zeit.
Die Rolle von Rauschen
Shannons Modell macht eine radikale Annahme: Rauschen ist unvermeidlich. Jeder Kanal, jedes Speichermedium, jede Schaltkreisverbindung führt zu einer gewissen Wahrscheinlichkeit von Fehlern. Die Frage ist nicht 'wie eliminieren wir Rauschen?' sondern 'wie können wir die ursprüngliche Nachricht trotz Rauschen wiederherstellen?'
Dies steht im Gegensatz zur klassischen Physik, in der Rauschen als nachträgliche Einführung (Unschärferelation) auftritt. Shannon behandelt Rauschen als grundlegende Bedingung - alle Theorie baut darauf auf.
Für den Moment konzentriert sich Kapitel 10 auf den rauschenfreien Fall: Quellcodierung ohne Fehler. Das Kanalcodierungsproblem (Fehlkorrektur) wartet auf spätere Kapitel.
Wann können Sie eindeutig dekodieren?
Für einen variablen Längencode ist es nützlich, dass der Empfänger eine Bitstruktur eindeutig dekodiert. Hamming illustriert dies 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 unmittelbar) wenn kein Codewort ein Präfix eines anderen Codeworts ist. Wenn Sie eine empfangene Bitstruktur erhalten, wissen Sie, dass ein Symbol am Ende ist, sobald Sie ein Blatt in der Dekodiertree erreichen - kein Vorhersagen erforderlich.
Beispiel präfixfreier Code für {s1, s2, s3, s4}: s1 = 0, s2 = 10, s3 = 110, s4 = 111.
Überprüfen Sie: 0 ist kein Präfix von 10, 110 oder 111. 10 ist kein Präfix von 110 oder 111 (10 gefolgt von mehreren Bits gibt 100... oder 101..., von denen keines mit 110 oder 111 beginnt). Der Code erfüllt die Anforderungen.
Das Dekodierverfahren: Folgen Sie dem Baum, biegen Sie sich bei jedem einlaufenden Bit ab, geben Sie das Symbol aus, wenn Sie ein Blatt erreichen, kehren Sie zum Wurzel zurück.
Die Kraftungleichheit
Für einen präfixfreien binären Code mit Codewortlängen l_1, l_2, ..., l_n:
Σ 2^(−l_i) ≤ 1
Gilt die Gleichheit, 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. Gleichzeitig kann für jedes Satzes von Längen, die die Kraftungleichheit erfüllen, ein präfixfreier Code existieren.
Anwendung der Kraftungleichheit
Gegeben Codewortlängen, überprüfen Sie die 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. ✓
Shannons Entropie
Der durchschnittliche Codellänge einer veränderlichen Codierung: L = Σ p_i · l_i, wo p_i die Wahrscheinlichkeit von Symbol s_i und l_i ihre Codellänge ist.
Wie kurz kann L werden? Shannons Antwort: nicht unter der Quellententropie.
Shannons Entropie: H = −Σ p_i · log₂(p_i) (Einheiten: Bits/Symbol)
Die Entropie misst die durchschnittliche Information pro Symbol. Hohe Entropie bedeutet, dass die Symbole ungefähr gleich wahrscheinlich sind (maximale Unvorhersagbarkeit). Niedrige Entropie bedeutet, dass einige Symbole überwiegen (hohe Vorhersagbarkeit, mehr komprimierbar).
Noiseless Coding Theorem
Für jede Präfixfreie-Codierung gilt: H(source) ≤ L ≤ H(source) + 1.
Es gibt keine Codierung, die die Entropie übertreffen kann. Huffman-Codierung (nächster Kapitel) erreicht den oberen Grenzwert: L < H + 1. Für Block-Codes über n Symbole engt sich der Grenzwert: H ≤ L/n < H + 1/n.
Die Entropie ist auch der theoretische Komprimierungsgrenzwert: Sie können die 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 ist die Entropie eine untere Schranke
Die untere Schranke des rauschfreien Codierungssatzes ist nicht nur eine Formel - sie spiegelt etwas Tiefes über Information wider: Sie können nicht komprimieren, was bereits maximal unvorhersagbar ist.
Wenn alle Symbole gleich wahrscheinlich sind (gleichmäßige Verteilung), ist die Entropie H = log₂(n) für n Symbole. Eine Blockcode mit Länge log₂(n) Bit erreicht genau H. Keine Code kann besser sein.
Wenn ein Symbol dominiert (z. B. p(A) = 0,99, p(B) = 0,01), ist H klein - nahe an 0. Ein veränderlicher Längencode kann A eine sehr kurze Code zuweisen, die Strömung sehr effizient codieren.
Der praktische Ertrag: Große Komprimierungsverluste existieren nur, wenn die Symbolwahrscheinlichkeiten sich erheblich unterscheiden. Wenn die Quelle bereits 'gleichmäßig' (zufällig) ist, gewinnt Huffman-Codierung nichts.