Entropiekodierung - Grundlagen

Im vorigen Schritt wurden die Symbol1-Symbole durch die VLI-Kodierung komprimiert, während die Symbol2-Symbole bisher unangetastet blieben.
Als letzten Schritt werden nun die Symbol1, die noch als 8-bit Werte (bei AC-Komponenten), bzw. als 4-bit Werte (bei DC-Komponenten) vorliegen, einer Huffman-Kodierung unterworfen. Dabei werden die Symbol1 (konstante Länge) durch neue Symbole mit unterschiedlicher Länge (die Huffman-Symbole) ersetzt, und zwar der Gestalt, dass häufig vorkommende Symbol1 kurze Huffman-Symbole erhalten, während seltene Symbol1 durch längere Huffman-Symbole kodiert werden. Dadurch wird die Datenmenge insgesamt reduziert.

Für die Kodierung wird eine Tabelle benutzt, in der für jedes Symbol1 die entsprechende Bitfolge steht, mit der es kodiert wird. Diese Huffman-Tabelle muss natürlich so aufgebaut sein, dass kein Huffman-Symbol der Anfang eines anderen Huffman-Symbols ist, sonst könnte die Huffman-kodierte Folge nicht mehr eindeutig dekodiert werden, denn die Huffman-Symbole stoßen ja nicht an Byte-Grenzen aufeinander.

Ein Beispiel für eine mögliche Kodierung: Nehmen wir an, es gäbe die Symbole 'A', 'B', 'D', 'K' und 'R'. Die zu kodierende Symbolfolge ist "ABRAKADABRA", also tritt das Symbol 'A' 5-mal auf, die Symbole 'B' und 'R'2-mal und die Symbole 'K' und 'D' einmal. Wir könnten also folgende Huffman-Kodierung verwenden:

Häufigkeit des Symbols
Originalsymbol
Huffman-Symbol
5
A
0
2
B
100
2
R
101
1
D
111
1
K
110

Die Folge "ABRAKADABRA" wäre dann kodiert 01001010111011001001010. Die Länge dieser Huffman-kodierten Folge ist 23. Ohne Huffman-Kodierung hätten wir für jedes Symbol 3 Bits gebraucht, also wäre die Länge der unkodierten Folge gleich 11*3 = 33 Bits. Wir haben uns folglich 10 Bits gespart.
Allerdings muss man dem Code noch die Huffman-Tabelle voranstellen, damit der Dekodierer weiß, wie die Huffman-Symbole in die ursprünglichen Symbole umgewandelt werden müssen, aber die ist verhältnismäßig klein. Bei einem JPEG-Bild machen die 4 Huffman-Tabellen (jeweils für Chrominanz/Luminanz und für AC/DC) nur wenige hundert Bytes aus.