Data Compression


Criteria

Survey Formats

Basics

Compression Methods

Data Formats


Arithmetic Coding (AC)

Principle of the AC

General Algorithm

AC versus Huffman

Data with high Redundancy

Adaptive AC

Implementations


Glossary

Index


Download


www.BinaryEssence.com

Arithmetic Coding (AC)


The aim of the arithmetic coding (AC) is to define a method that provides code words with an ideal length. Like for every other entropy coder, it is required to know the probability for the appearance of the individual symbols.


The AC assigns an interval to each symbol, whose size reflects the probability for the appearance of this symbol. The code word of a symbol is an abritrary rational number belonging the corresponding interval.


The entire set of data is represented by a rational number, which is always placed within the interval of each symbol. With data being added the number of significant digits rises continuously.


The development of arithmetic coding starts in the 60's, the crucial algorithms were introduced at the end of the 70's up to the 80's. Jorma Rissanen and Glen G. Langdon Jr., who presented their work in "IBM Journal of Research and Development", were considerably involved.


Although the AC usually provides a better result in comparison to the wide-spread Huffman code, it is applied rarely. At first this was due to the requirements on the computer's performance. Later legal considerations became more important. The companies IBM, AT&T and Mitsubishi shall have valid patents at least.


 <   ^   > 

Data Compression Implementations Principle of the Arithmetic Coding