Arithmetic coding

Arithmetic coding (AC) is a form of entropy encoding used in lossless data compression.

[1] A recent family of entropy coders called asymmetric numeral systems allows for faster implementations thanks to directly operating on a single natural number representing the current information.

This is feasible for long sequences because there are efficient, in-place algorithms for converting the base of arbitrarily precise numbers.

In general, arithmetic coders can produce near-optimal output for any given set of symbols and probabilities.

(The optimal value is −log2P bits for each symbol of probability P; see Source coding theorem.)

Compression algorithms that use arithmetic coding start by determining a model of the data – basically a prediction of what patterns will be found in the symbols of the message.

Models can even be adaptive, so that they continually change their prediction of the data based on what the stream actually contains.

Otherwise, the decoding process could continue forever, mistakenly reading more symbols from the fraction than were in fact encoded into it.

bits; the same message could have been encoded in the binary fraction 0.10001001 (equivalent to 0.53515625 decimal) at a cost of only 8bits.

This inefficiency of at most 1 bit results in relatively less overhead as the message size grows.

One advantage of arithmetic coding over other similar methods of data compression is the convenience of adaptation.

An example shows how this would work if the model called for the interval [0,1) to be divided into thirds, and this was approximated with 8 bit precision.

A process called renormalization keeps the finite precision from becoming a limit on the total number of symbols that can be encoded.

Recall that in the case where the symbols had equal probabilities, arithmetic coding could be implemented by a simple change of base, or radix.

The radix is used to express any finite integer in a presumed multiplier in polynomial form.

To encode a message with a length closer to the theoretical limit imposed by information theory we need to slightly generalize the classic formula for changing the radix.

For the computation of L we multiply each term in the above expression by the product of the frequencies of all previously occurred symbols: The difference between this polynomial and the polynomial above is that each term is multiplied by the product of the frequencies of all previously occurring symbols.

After the computation of the upper bound U and the reduction of the message by selecting a number from the interval [L, U) with the longest trail of zeros we can presume that this length can be reduced by

When naively Huffman coding binary strings, no compression is possible, even if entropy is low (e.g. ({0, 1}) has probabilities {0.95, 0.05}).

Huffman encoding assigns 1 bit to each value, resulting in a code of the same length as the input.

Golomb-Rice codes only apply to Bernoulli inputs such as the one in this example, however, so it is not a substitute for blocking in all cases.

Basic algorithms for arithmetic coding were developed independently by Jorma J. Rissanen, at IBM Research, and by Richard C. Pasco, a Ph.D. student at Stanford University; both were published in May 1976.

Pasco cites a pre-publication draft of Rissanen's article and comments on the relationship between their works:[3]

It shifts the code element to the most significant end of the accumulator, using a pointer obtained by addition and exponentiation.

We shall now compare the alternatives in the three choices, and see that it is preferable to shift the code element rather than the accumulator, and to add code elements to the least significant end of the accumulator.Less than a year after publication, IBM filed for a US patent on Rissanen's work.

Techniques covered by patents may be essential for implementing the algorithms for arithmetic coding that are specified in some formal international standards.

The availability of licenses under RAND terms does not necessarily satisfy everyone who might want to use the technology, as what may seem "reasonable" for a company preparing a proprietary commercial software product may seem much less reasonable for a free software or open source project.

[6] JPEG XL, as well as archivers like PackJPG, Brunsli and Lepton, that can losslessly convert Huffman encoded files to ones with arithmetic coding (or asymmetric numeral systems in case of JPEG XL), showing up to 25% size saving.

The JPEG image compression format's arithmetic coding algorithm is based on the following cited patents (since expired).

Every programmatic implementation of arithmetic encoding has a different compression ratio and performance.