Datenkompression


Kriterien

Übersicht Formate

Grundlagen

Kompressionsverfahren

Datenformate


arithmetische Kodierung (AC)

Prinzip der AC

allgemeiner Algorithmus

AC versus Huffman

Daten hoher Redundanz

adaptive AC

Implementationen


Glossar

Stichwortverzeichnis


Download


www.BinaryEssence.de

arithmetische Kodierung (AC)


Ziel der arithmetischen Kodierung (AC - Arithmetic Coding) ist es, ein Verfahren zu definieren, das bei Kenntnis der relativen Wahrscheinlichkeit für das Auftreten eines Zeichens einen Kode idealer Länge zur Verfügung stellt.


Die AC ordnet dazu jedem Zeichen ein Intervall zu, dessen Größe die Wahrscheinlichkeit für das Auftreten dieses Zeichens wiederspiegelt. Die Kodierung erfolgt durch Auswahl einer rationalen Zahl, die innerhalb dieses Intervalls liegt. Das gesamte Datenvolumen wird durch eine rationalen Zahl dargestellt, die für jedes Zeichen immer innerhalb von dessen Intervall liegt. Mit zunehmendem Datenbestand wird die Länge, bzw. die Anzahl von signifikanten Nachkommastellen, der Zahl immer größer.


Die Entwicklung der arithmetischen Kodierung geht bis auf die 60er Jahre zurück, die entscheidenden Algorithmen sind jedoch erst Ende der 70er bis hin zu den 80er Jahren vorgestellt worden. Maßgeblich beteiligt waren Jorma Rissanen und Glen G. Langdon Jr., die ihre Arbeiten im "IBM Journal of Research and Development" vorgestellt haben.


Obwohl die AC in der Regel ein besseres Ergebnis liefert, als die klassische Huffman-Kodierung, ist sie nur verhältnismäßig selten eingesetzt worden. Dies lag zunächst in den Anforderungen an die Rechenleistung begründet. Später kamen jedoch patentrechtliche Erwägungen primär zum Tragen. Die Firmen IBM, AT&T und Mitsubishi sollen gültige Patente besitzen.


 <   ^   > 

oben zurück weiter



Anzeigen:

Informations- und Kodierungstheorie