In diesem Artikel beschreibe ich innerhalb der Artikelserie die Codierung von Informationen über die Entropiecodierung und das Prinzip bei der arithmetrischen Codierung.

Codierung von Zeichen

Entropiecodierung

Bei dieser Art der Codierung erhalten Zeichen umso mehr Informationen bei der Codierung (Bitlänge), je unwahrscheinlicher deren Auftreten ist. Die Codierung jedes Zeichens wird über sog. Huffman-Bäumchen ermittelt. Bei dem zugrunde liegenden Algorithmus werden immer die Zeichen mit der niedrigsten absoluten Häufigkeit solange zusammengefasst bis die Wurzel des Baums erreicht ist. Die Redundanz einer Huffmancodierung (also des Huffmanbaums) ergibt sich aus der Differenz zwischen Summe der durchschnittlicher Wortlänge und Entropie. Sofern diese Differenz größer 0 ist, ist die Codierung nicht optimal.

Arithmetrische Codierung

Bei dieser Art der Codierung findet während der Verschlüsselung eine Art Intervallschachtelung statt. In einem ersten Schritt werden allen bei der Codierung verwendeten Zeichen je eine Auftrittswahrscheinlichkeit zugeordnet.

Bsp.: K hat 0,25, M hat 0,5 und O hat 0,25.

Über die Auftrittswahrscheinlichkeit wird das das zur Verfügung stehende Intervall in Teilbereiche unterteilt und immer weiter verschachtelt, bis alle Zeichen des Worts einbezogen wurden. Im Bild wurde z.B. das Wort KOMM verschlüsselt.

Anschließend werden die Grenzen des letzten Intervalls ermittelt, um danach eine binäre Zahl zu finden, die möglichst kurz ist und deren dezimales Gegenüber dort enthalten ist. Im Beispiel ist das letzte Intervall von 0,2109375 bis 0,2265625:

2 hoch -1 = 0,5 und daher nicht enthalten

2 hoch -2 = 0,25 und daher nicht enthalten

2 hoch -3 = 0,125 ist enthalten, womit noch mindestens 0,0859375 offen sind

2 hoch -4 = 0,0625 ist enthalten, womit noch mindestens 0,022875 offen sind

2 hoch -5 = 0,03125 ist enthalten, die Summer aller Zahlen beträgt 0,21875 und liegt im Intervall

Die Binärzahl lautet daher 00111, wobei die ersten 2 Nullen für 2 hoch -1 und 2 hoch -2 stehen.