Overview of Arithmetic Encoding

The method of arithmetic coding was suggested by Elias, and presented by Abramson in his text on Information Theory. It is a form of entropy encoding used in lossless data compression. Normally, a string of characters such as the words “hello there” is represented using a fixed number of bits per character, as in the ASCII code. When a string is converted to arithmetic encoding, frequently used characters will be stored with fewer bits and not-so-frequently occurring characters will be stored with more bits, resulting in fewer bits used in total. Arithmetic coding differs from other forms of entropy encoding, such as Huffman coding, in that rather than separating the input into component symbols and replacing each with a code, arithmetic coding encodes the entire message into a single number, a fraction n where [0.0 ≤ n < 1.0).

Here a source ensemble is represented by an interval between 0 and 1 on the number line. Each symbol of the ensemble narrows the interval. As the interval becomes smaller, the number of bits needed to specify it grows, Arithmetic coding assumes an explicit probabilistic model of the source. A higher probability message narrows the interval less than a low probability message so that high probability messages contribute fewer bits to the coded ensemble. The method with an unordered list of sources and their probabilities. The number line is partitioned into sub-intervals based on cumulative probabilities.