> tunstall | variabel | fest <
// Tunstall-Codierung – optimale variabel-zu-festlängige Kompression
V2F-Codierung
Ordnet Sequenzen variabler Länge Codes mit fester Länge zu.
Wahrscheinlichkeitsbasiert
Das Wörterbuch wird aus der Wahrscheinlichkeitsverteilung der Symbole aufgebaut.
Einfache Dekodierung
Codes fester Länge ermöglichen eine einfache und schnelle Dekodierung.
>> Technische Infos
Wie Tunstall-Codierung funktioniert:
Die Tunstall-Codierung erstellt ein Wörterbuch aus Folgen variabler Länge, die auf binäre Codes fester Länge abgebildet werden. Ausgehend von Einzelsymbolen wird iterativ die wahrscheinlichste Sequenz gewählt und durch alle möglichen Erweiterungen um ein Symbol ersetzt. So entsteht ein optimaler variabel-zu-festlängiger Code, bei dem wahrscheinliche Sequenzen eigene Codewörter erhalten.
Tunstall-Beispiel:
Text: 'aabaa' mit P(a)=0.8, P(b)=0.2 Wörterbuchaufbau (3-Bit-Codes): Initial: a, b Erweitere 'a': aa, ab Erweitere 'aa': aaa, aab Erweitere 'ab': aba, abb Endgültiges Wörterbuch (8 Codes): aaa → 000 aab → 001 aba → 010 abb → 011 aa → 100 ab → 101 a → 110 b → 111 Kodierung: 'aabaa' → 001 100 (aab + aa)
Warum Tunstall-Codierung verwenden?:
- ▸Ausgabe mit fester Codewortlänge
- ▸Einfache Decoder-Implementierung
- ▸Keine Synchronisationsprobleme im Bitstrom
- ▸Gut geeignet für Hardware-Implementierungen
- ▸Optimal für gedächtnislose Quellen
>> Häufig gestellte Fragen
Was ist Tunstall-Codierung?
Tunstall-Codierung ist ein Entropie-Codierverfahren mit variabler Eingabe- und fester Ausgabelänge. Anders als bei Huffman (fest-zu-variabel) ordnet Tunstall Folgen variabler Länge Codewörtern fester Länge zu und ist damit ideal für Anwendungen mit konstantem Ausgaberatenbedarf.
Tunstall vs. Huffman-Codierung?
Huffman: feste Eingabe → variable Ausgabe (z. B. 'a' → '0', 'b' → '10'). Tunstall: variable Eingabe → feste Ausgabe (z. B. 'aa' → '000', 'ab' → '001'). Tunstall ist besser für Hardware und Synchronisation geeignet, erreicht aber meist etwas geringere Kompressionsraten.
Wie wird das Wörterbuch aufgebaut?
Man beginnt mit Einzelsymbolen. Dann wiederholt man: 1) Finde die Sequenz mit der höchsten Wahrscheinlichkeit, 2) entferne sie und füge alle möglichen Erweiterungen um ein Symbol hinzu, 3) fahre fort, bis die gewünschte Wörterbuchgröße (2^n für n-Bit-Codes) erreicht ist.
Wo wird Tunstall-Codierung eingesetzt?
Tunstall-Codierung wird in Sprachkompression, Bildkodierung und überall dort eingesetzt, wo eine feste Bitrate erforderlich ist. Sie ist besonders nützlich in Hardware-Implementierungen und Echtzeitsystemen, in denen variable Codewortlängen das Timing erschweren würden.