Huffman-Codes, Golomb-Codes und Arithmetische Codierung: Eine praxisnahe Einführung mit Beispielen aus der Kryptowelt

Einführung in die Codierungstheorie: Von Huffman bis zur arithmetischen Codierung

Die Codierungstheorie ist ein zentraler Bestandteil der modernen Datenkompression. Ob beim Streamen von Videos, beim Speichern von Dateien oder bei der Übertragung von Kryptowährungstransaktionen – effiziente Codes sparen Bandbreite und Speicherplatz. In diesem Tutorial betrachten wir die Grundlagen der Huffman-Codierung, Golomb-Codes und arithmetischen Codierung, wie sie in der Aufgabenstellung Ee276 homework #3 p0 behandelt werden. Wir verwenden aktuelle Beispiele aus der Kryptowelt und der Spieleentwicklung, um die Konzepte greifbar zu machen.

1. Huffman-Codes: Welche Codes sind gültig?

Ein Huffman-Code ist ein optimaler Präfixcode für eine gegebene Wahrscheinlichkeitsverteilung. Nicht jeder Satz von Codewörtern kann ein Huffman-Code sein. Betrachten wir die Kandidaten:

• {0,10,11}: Dies ist ein gültiger Huffman-Code, da er die Präfixeigenschaft erfüllt und für bestimmte Wahrscheinlichkeiten optimal sein kann (z. B. p(0)=0.5, p(10)=0.25, p(11)=0.25).
• {00,01,10,110}: Dieser Code ist kein Huffman-Code. Warum? Die längsten Codewörter (00,01,10,110) haben unterschiedliche Längen, aber 110 ist länger als die anderen. In einem Huffman-Code für vier Symbole wären die längsten Codewörter idealerweise gleich lang oder unterscheiden sich nur um ein Bit. Zudem verletzt 110 die Präfixeigenschaft nicht, aber die Struktur entspricht nicht dem Huffman-Algorithmus, der immer die beiden seltensten Symbole zusammenfasst.
• {01,10}: Dies ist ein gültiger Huffman-Code für zwei Symbole mit beliebigen Wahrscheinlichkeiten (z. B. p(01)=p(10)=0.5).

Merkregel: Ein Huffman-Code muss die Kraft-Ungleichung erfüllen und die Präfixeigenschaft besitzen. Die Längen der Codewörter müssen aus dem Huffman-Algorithmus resultieren, der die beiden unwahrscheinlichsten Symbole zusammenfasst.

2. Golomb-Codes für seltene Ereignisse: Analogie zu Bitcoin-Mining

Stell dir vor, du betreibst Bitcoin-Mining: Die Wahrscheinlichkeit, einen Block zu finden (ein „T“ in unserer Terminologie), ist sehr gering, ähnlich wie p=1/16 in der Aufgabenstellung. Möchtest du die Anzahl der Versuche bis zum nächsten Erfolg codieren, eignet sich der Golomb-Code hervorragend.

2.1 Verteilung von Zk

Die Zufallsvariable Zk (Anzahl der Versuche bis zum nächsten T) folgt einer geometrischen Verteilung mit Parameter p=1/16: P(Zk=j) = (1-p)^(j-1) * p für j=1,2,3,...

2.2 Erwartungswert und Entropie

Der Erwartungswert ist E[Zk] = 1/p = 16. Die Entropie H(Zk) = ( -log2(p) - (1-p)/p * log2(1-p) ) ≈ 4,2 Bit. Das Verhältnis H/E ≈ 0,26, während die Entropie von Xk (Bernoulli mit p=1/16) h2(p) ≈ 0,34 Bit beträgt. Die geometrische Verteilung hat also eine geringere Entropie pro Symbol, was die Effizienz der Golomb-Codierung erklärt.

2.3 Golomb-Code für m=16

Der Golomb-Code teilt den Quotienten q = floor((j-1)/m) und den Rest r = (j-1) mod m auf. Der Code besteht aus q Einsen, gefolgt von einer Null und dann einer binären Darstellung des Rests mit log2(m) Bits (bei m=16 sind das 4 Bits). Zum Beispiel: j=1 → q=0, r=0 → Code: 0 0000; j=16 → q=0, r=15 → 0 1111; j=17 → q=1, r=0 → 10 0000; usw. Die erwartete Codelänge berechnet sich aus der geometrischen Verteilung und liegt nahe an der Entropie.

3. Arithmetische Codierung: Präzise Kompression für Kryptografie

Arithmetische Codierung ist besonders nützlich, wenn die Quelle viele Symbole mit unterschiedlichen Wahrscheinlichkeiten hat – wie bei der Kompression von Blockchain-Daten. Sie arbeitet mit Intervallen statt einzelnen Codewörtern.

3.1 Funktionsweise

Stell dir vor, du hast drei Symbole R, G, B mit Wahrscheinlichkeiten 0.1, 0.2, 0.7. Das Startintervall [0,1) wird gemäß den Wahrscheinlichkeiten unterteilt. Für die Sequenz „GRB“ ergibt sich ein immer kleineres Intervall. Der Encoder wählt eine Dezimalzahl aus diesem Intervall und gibt deren Nachkommastellen aus. Im Beispiel ist das Intervall [0.106, 0.12), und die kürzeste Zahl ist 0.11 (entspricht „11“).

3.2 Länge des Ausgabeintervalls

Die Länge des Intervalls nach n Schritten ist das Produkt der Wahrscheinlichkeiten der einzelnen Symbole: l_n = ∏ q(x_i). Der Logarithmus zur Basis 10 der Intervalllänge gibt die Anzahl der benötigten Dezimalstellen an.

4. Fazit und Ausblick

Huffman-Codes, Golomb-Codes und arithmetische Codierung sind grundlegende Werkzeuge der Datenkompression. Während Huffman für kleine Alphabete optimal ist, eignen sich Golomb-Codes für geometrisch verteilte Daten (wie Mining-Erfolge). Arithmetische Codierung erreicht nahezu die Entropie und ist flexibel einsetzbar. In der Praxis – etwa bei der Kompression von Kryptowährungsdaten oder in Spielen – helfen diese Verfahren, Speicherplatz und Bandbreite zu sparen.

Häufig gestellte Fragen (FAQ)

Was ist der Unterschied zwischen Huffman- und arithmetischer Codierung?

Huffman-Codes weisen jedem Symbol ein ganzzahliges Codewort zu, während arithmetische Codierung ein gesamtes Intervall verwendet und so Bruchteile von Bits ermöglicht. Arithmetische Codierung ist daher näher an der Entropie, aber rechenintensiver.

Wann verwendet man Golomb-Codes?

Golomb-Codes sind ideal, wenn die Daten einer geometrischen Verteilung folgen – z. B. die Anzahl der Fehlversuche vor einem Erfolg. Sie werden in der Bildkompression (JPEG-LS) und bei der Codierung von Lauflängen eingesetzt.

Können diese Codes in der Kryptografie eingesetzt werden?

Ja, insbesondere bei der Kompression von Blockchain-Daten oder bei der Übertragung von Transaktionen, um Speicherplatz zu sparen. Arithmetische Codierung wird auch in verlustfreien Kompressionsverfahren für kryptografische Schlüssel verwendet.