Arithmetische Kodierung ist ein Verfahren der Entropiekodierung, das eine ganze Nachricht als ein einziges Intervall zwischen 0 und 1 darstellt. Mit jedem Symbol wird das Intervall proportional zur Wahrscheinlichkeit des Symbols verkleinert; der Code ist am Ende eine Zahl aus dem finalen Intervall. Anders als die Huffman-Codierung, die jedem Symbol einen Code aus ganzen Bits zuweist, kann die arithmetische Kodierung Bruchteilsbits pro Symbol nutzen und kommt dadurch näher an die von Claude Shannon definierte Entropiegrenze heran.
Wie funktioniert es?
Der Encoder startet mit dem Intervall [0, 1). Für jedes Symbol s mit Wahrscheinlichkeit p(s) wird das aktuelle Intervall in Teilintervalle zerlegt, deren Breite der Wahrscheinlichkeit entspricht, und auf das Teilintervall von s eingeschränkt. Häufige Symbole verkleinern das Intervall wenig, seltene stark. Nach der Verarbeitung aller Symbole genügt eine einzelne Zahl im verbliebenen Intervall, um die gesamte Nachricht zu repräsentieren. Der Decoder rekonstruiert die Symbole, indem er die Zahl Schritt für Schritt den Intervallen zuordnet.
Weil die Intervallbreite mit jedem Symbol exponentiell schrumpft, ist eine naive Umsetzung mit Gleitkommazahlen praktisch unmöglich. Echte Implementierungen arbeiten mit Ganzzahlarithmetik und einer Renormalisierung: Sobald sich führende Ziffern stabilisiert haben, werden sie ausgegeben und das Intervall neu skaliert. Eine verbreitete Ganzzahl-Form ist der Range Coder.
Einsatzgebiete
- JPEG 2000 und JBIG 2 (Bildkompression)
- H.264/H.265 und VP9/AV1: Codecs setzen CABAC ein, eine kontextadaptive binäre arithmetische Kodierung
- Moderne Archiv- und Kompressionsformate als Teil größerer Verfahren
Geschichte und Abgrenzung
Grundlagen stammen aus den 1940er-Jahren (Shannon-Fano), praktikable Verfahren entwickelten in den 1970er-Jahren unter anderem Jorma Rissanen. In den 1980er-Jahren belasteten IBM-Patente die Nutzung, die um die Jahrtausendwende ausliefen und die Verbreitung in Standards erleichterten. Während die Huffman-Codierung bei Einzelsymbol-Codierung mit ganzzahligen Codes optimal ist, erreicht die arithmetische Kodierung in der Praxis eine höhere Kompressionsdichte, ist aber rechenintensiver. Eine neuere Alternative mit ähnlicher Dichte, aber höherer Geschwindigkeit sind die Asymmetric Numeral Systems (ANS).
Verwandte Grundlagen: Datenkompression, verlustfreie Kompression.