Arithmetic coding

This article may require copy-editing for grammar, style, cohesion, tone or spelling. You can assist by editing it. (May 2009)

Arithmetic coding is a method for 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. Like Huffman coding, arithmetic coding is a form of variable-length entropy encoding that converts a string into another form that represents frequently used characters using fewer bits and infrequently used characters using more bits, with the goal of using fewer bits in total. As opposed to other entropy encoding techniques that separate the input message into its component symbols and replace each symbol with a code word, arithmetic coding encodes the entire message into a single number, a fraction n where (0.0 ≤ n < 1.0).

Arithmetic coding and elementary numbers theory

Both arithmetic and range coding may be examined from the perspective of numbers theory. It can be interpreted as generalized change of radix. For example, if we consider the short message

• DABDDB

we may look at it as a number in a certain base presuming that involved symbols form an ordered set and each symbol represents integer A=0, B=1, C=2, D=3 and so on. If we make table of frequencies and cumulative frequencies for this message it looks like follows

If we choose radix=6, which is length of the message and convert number DABDDB into decimal number we shall have

6⁵ * 3 + 6⁴ * 0 + 6³ * 1 + 6² * 3 + 6¹ * 3 + 6⁰ * 1 = 23671

Result 23671 has length of 15 bits and does not make message close to theoretical limit computed via entropy, which must be near 9 bits. In order to make it in accordance with information theory we need to slightly generalize classic formula for changing the radix. We have to compute LOW and HIGH limits and choose convenient number between them. For computation of LOW limit we multiply each next term in above expression by product of frequencies of all previously occurred symbols, so it turned into the following

LOW = 6⁵ * 3 + 3 * [ 6⁴ * 0 + 1 * [ 6³ * 1 + 2 * [ 6² * 3 + 3 * [ 6¹ * 3 + 3 * [ 6⁰ * 1 ] ] ] ] ] = 25002

HIGH limit must be LOW plus product of all frequencies. HIGH = LOW + 3 * 1 * 2 * 3 * 3 * 2 = 25002 + 108 = 25110. Now we can choose any number to represent the message from semi-closed interval [LOW, HIGH), which we can take as number with longest possible trail of zeros, for example 25100. In case of long message this trail of zeros will be much longer and can be either dropped or presented as exponent. The number 251, received after truncation of zeros has length of 8 bits, which is even less than theoretical limit. It looks like computing of LOW and HIGH limits and considered selection of convenient number is completely different from switch to classical base change formula, but we can see that classic formula simply presumes all frequencies equal to 1 so it is particular case of more generic case considered here. In our frequency table all frequencies are the distances to the next symbol, or, for the last symbol, is distance to base. In case when all them equal to 1 we have classic particular case. In order to complete the topic we have to show that number 25100 can be converted back to original message. Back conversion is made in the way as for classic case with only difference that we consider intervals instead of truncation of fractional part. On the first step we divide 25100 by 6⁵. The result 3.227 is between 3 and base, so we identify first cumulative frequency as 3, symbol as D and after identification we subtract 6⁵ * 3 from 25100 and divide result by 3, which gives us 590. Next symbol is identified by division of 590 by 6⁴, which gives us 0.455, that means symbol is A and remainder is the same (590 - 6⁴ * 0) / 1 = 590. If we continue in the same way to the end we restore correctly the whole original message. If we look at LOW expression we can see that by subtracting 6⁵ * 3 from result 25002 and dividing it by 3 we actually remove first symbol. Naturally, identification works for any number between LOW and HIGH.

It is more than another way of demonstration of arithmetic coding concept. First and most important it is clear that changing radix exists in more generic form than we knew before and that formula that we used before was a particular case. Second, it can be considered as natural law or foundation of the numbers theory and by that can make any patenting of arithmetic coding highly debatable. Third, it lead to much more elegant way of programming of arithmetic coders or range coders. Since base can be chosen as 2ⁿ all powers in LOW expression turn into binary shifts. Multipliers can be presented as limited length mantissa and exponent, which was successfully implemented in Article: Adaptive Arithmetic Coding. This concept frees from computing HIGH limit on every step. In numerical implementation it is not computed at all. It also allows more elegant way to carry propagation. Some theoretical aspects and relation to classical information theory can be also found in Anatomy of Range Encoder.

This example and theoretical conclusion may raise few questions:
1. How it all related to many pages of explanation of arithmetic coding via probabilities? The answer is simple. It is same thing. If you divide expression for LOW value by 6⁶, where 6 is size of message you may see everything in fractions and each step will be computing of the new point on interval between 0 and 1.0. In considered case this interval is between 0 and 6⁶ = 46656. This explanation does not need introduction into renormalization issues that occupies chapters in books on data compression.
2. Is it always reversible? Yes it is. Theoretical part was published in IP.com (publication identifier IPCOM000144439D).
3. Is it stable in numerical implementation when products of all frequencies are computed approximately? Yes it is, because when we compute it as mantissa and exponent we make them smaller not larger and it can't be smaller than 1.0. So it is always between exact number and 1.0. In case of 1.0 we have classic formula, which also works.
4. How to prove that we reduce the size of the message in accordance with Shannon entropy? It needs some algebraic transformations. It is elementary enough to be omitted.
5. How about adaptive technique? In adaptive technique we consider sub sequences selected for specific preceding combinations. For example, should this message be long enough we would consider symbols following expression 'DAB' and make another frequency table for them. The method works if we switch tables in syncronous way in encoding and decoding.

How arithmetic coding works

Defining a model

Arithmetic coders produce near-optimal output for a given set of symbols and probabilities (the optimal value is −log₂P 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. The more accurate this prediction is, the closer to optimality the output will be.

Example: a simple, static model for describing the output of a particular monitoring instrument over time might be:

• 60% chance of symbol NEUTRAL
• 20% chance of symbol POSITIVE
• 10% chance of symbol NEGATIVE
• 10% chance of symbol END-OF-DATA. (The presence of this symbol means that the stream will be 'internally terminated', as is fairly common in data compression; when this symbol appears in the data stream, the decoder will know that the entire stream has been decoded.)

Models can also handle alphabets other than the simple four-symbol set chosen for this example. More sophisticated models are also possible: higher-order modelling changes its estimation of the current probability of a symbol based on the symbols that precede it (the context), so that in a model for English text, for example, the percentage chance of "u" would be much higher when it follows a "Q" or a "q". Models can even be adaptive, so that they continuously change their prediction of the data based on what the stream actually contains. The decoder must have the same model as the encoder.

A simplified example

As an example of how a sequence of symbols is encoded, consider a sequence taken from a set of three symbols, A, B, and C, each equally likely to occur. Simple block encoding would use 2 bits per symbol, which is wasteful: one of the bit variations is never used.

A more efficient solution is to represent the sequence as a rational number between 0 and 1 in base 3, where each digit represents a symbol. For example, the sequence "ABBCAB" could become 0.011201₃. The next step is to encode this ternary number using a fixed-point binary number of sufficient precision to recover it, such as 0.001011001₂ — this is only 9 bits, 25% smaller than the naive block encoding. This is feasible for long sequences because there are efficient, in-place algorithms for converting the base of arbitrarily precise numbers.

Finally, knowing the original string had length 6, one can simply convert back to base 3, round to 6 digits, and recover the string.

Encoding and decoding

In general, each step of the encoding process, except for the very last, is the same; the encoder has basically just three pieces of data to consider:

• The next symbol that needs to be encoded
• The current interval (at the very start of the encoding process, the interval is set to [0,1), but that will change)
• The probabilities the model assigns to each of the various symbols that are possible at this stage (as mentioned earlier, higher-order or adaptive models mean that these probabilities are not necessarily the same in each step.)

The encoder divides the current interval into sub-intervals, each representing a fraction of the current interval proportional to the probability of that symbol in the current context. Whichever interval corresponds to the actual symbol that is next to be encoded becomes the interval used in the next step.

Example: for the four-symbol model above:

• the interval for NEUTRAL would be [0, 0.6)
• the interval for POSITIVE would be [0.6, 0.8)
• the interval for NEGATIVE would be [0.8, 0.9)
• the interval for END-OF-DATA would be [0.9, 1).

When all symbols have been encoded, the resulting interval unambiguously identifies the sequence of symbols that produced it. Anyone who has the same final interval and model that is being used can reconstruct the symbol sequence that must have entered the encoder to result in that final interval.

It is not necessary to transmit the final interval, however; it is only necessary to transmit one fraction that lies within that interval. In particular, it is only necessary to transmit enough digits (in whatever base) of the fraction so that all fractions that begin with those digits fall into the final interval.

Example

A diagram showing decoding of 0.538 (the circular point) in the example model. The region is divided into subregions proportional to symbol frequencies, then the subregion containing the point is successively subdivided in the same way.

Consider the process for decoding a message encoded with the given four-symbol model. The message is encoded in the fraction 0.538 (using decimal for clarity, instead of binary; also assuming that there are only as many digits as needed to decode the message.)

The process starts with the same interval used by the encoder: [0,1), and using the same model, dividing it into the same four sub-intervals that the encoder must have. The fraction 0.538 falls into the sub-interval for NEUTRAL, [0, 0.6); this indicates that the first symbol the encoder read must have been NEUTRAL, so this is the first symbol of the message.

Next divide the interval [0, 0.6) into sub-intervals:

• the interval for NEUTRAL would be [0, 0.36) -- 60% of [0, 0.6)
• the interval for POSITIVE would be [0.36, 0.48) -- 20% of [0, 0.6)
• the interval for NEGATIVE would be [0.48, 0.54) -- 10% of [0, 0.6)
• the interval for END-OF-DATA would be [0.54, 0.6). -- 10% of [0, 0.6)

Since .538 is within the interval [0.48, 0.54), the second symbol of the message must have been NEGATIVE.

Again divide our current interval into sub-intervals:

• the interval for NEUTRAL would be [0.48, 0.516)
• the interval for POSITIVE would be [0.516, 0.528)
• the interval for NEGATIVE would be [0.528, 0.534)
• the interval for END-OF-DATA would be [0.534, 0.540).

Now .538 falls within the interval of the END-OF-DATA symbol; therefore, this must be the next symbol. Since it is also the internal termination symbol, it means the decoding is complete. If the stream was not internally terminated, there needs to be some other way to indicate where the stream stops. Otherwise, the decoding process could continue forever, mistakenly reading more symbols from the fraction than were in fact encoded into it.

The same message could have been encoded by the equally short fractions .534, .535, .536, .537 or .539. This suggests that the use of decimal instead of binary introduced some inefficiency. This is correct; the information content of a three-digit decimal is approximately 9.966 bits; the same message could have been encoded in the binary fraction .10001010 (equivalent to .5390625 decimal) at a cost of only 8 bits. (The final zero must be specified in the binary fraction, or else the message would be ambiguous without external information such as compressed stream size.)

This 8 bit output is larger than the information content, or entropy of the message, which is 1.57 * 3 or 4.71 bits. The large difference between the example's 8 (or 7 with external compressed data size information) bits of output and the entropy of 4.71 bits is caused by the short example message not being able to exercise the coder effectively. The claimed symbol probabilities were [.6, .2, .1, .1], but the actual frequencies in this example are [.33, 0, .33 .33]. If the intervals are readjusted for these frequencies, the entropy of the message would be 1.58 bits and the same NEUTRAL NEGATIVE ENDOFDATA message could be encoded as intervals [0, 1/3); [1/9, 2/9); [5/27, 6/27); and a binary interval of [1011110, 1110001). This could yield an output message of 111, or just 3 bits. This is also an example of how statistical coding methods like arithmetic encoding can produce an output message that is larger than the input message, especially if the probability model is off.

Precision and renormalization

The above explanations of arithmetic coding contain some simplification. In particular, they are written as if the encoder first calculated the fractions representing the endpoints of the interval in full, using infinite precision, and only converted the fraction to its final form at the end of encoding. Rather than try to simulate infinite precision, most arithmetic coders instead operate at a fixed limit of precision which they know the decoder will be able to match, and round the calculated fractions to their nearest equivalents at that precision. 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. Note that as now the precision is known, so are the binary ranges we'll be able to use.

A process called renormalization keeps the finite precision from becoming a limit on the total number of symbols that can be encoded. Whenever the range is reduced to the point where all values in the range share certain beginning digits, those digits are sent to the output. For however many digits of precision the computer can handle, it is now handling fewer than that, so the existing digits are shifted left, and at the right, new digits are added to expand the range as widely as possible. Note that this result occurs in two of the three cases from our previous example.

Teaching aid

An interactive visualization tool for teaching arithmetic coding, dasher.tcl, was also the first prototype of the assistive communication system, Dasher.

Connections between arithmetic coding and other compression methods

Huffman coding

There is great similarity between arithmetic coding and Huffman coding – in fact, it has been shown that Huffman is just a specialized case of arithmetic coding – but because arithmetic coding translates the entire message into one number represented in base b, rather than translating each symbol of the message into a series of digits in base b, it will sometimes approach optimal entropy encoding much more closely than Huffman can.

In fact, a Huffman code corresponds closely to an arithmetic code where each of the frequencies is rounded to a nearby power of ½ — for this reason Huffman deals relatively poorly with distributions where symbols have frequencies far from a power of ½, such as 0.75 or 0.375. This includes most distributions where there are either a small numbers of symbols (such as just the bits 0 and 1) or where one or two symbols dominate the rest.

For an alphabet {a, b, c} with equal probabilities of 1/3, Huffman coding may produce the following code:

• a → 0: 50%
• b → 10: 25%
• c → 11: 25%

This code has an expected (2 + 2 + 1)/3 ≈ 1.667 bits per symbol for Huffman coding, an inefficiency of 5 percent compared to log₂3 ≈ 1.585 bits per symbol for arithmetic coding.

For an alphabet {0, 1} with probabilities 0.625 and 0.375, Huffman encoding treats them as though they had 0.5 probability each, assigning 1 bit to each value, which doesn't achieve any compression over naive block encoding. Arithmetic coding approaches the optimal compression ratio of:

.

When the symbol 0 has a high probability of 0.95, the difference is much greater:

.

One simple way to address this weakness is to concatenate symbols to form a new alphabet in which each symbol represents a sequence of symbols in the original alphabet. In the above example, grouping sequences of three symbols before encoding would produce new "super-symbols" with the following frequencies:

• 000: 85.7%
• 001, 010, 100: 4.5% each
• 011, 101, 110: .24% each
• 111: 0.0125%

With this grouping, Huffman coding averages 1.3 bits for every three symbols, or 0.433 bits per symbol, compared with one bit per symbol in the original encoding.

Range encoding

Range encoding is another way of looking at arithmetic coding. Arithmetic coding and range encoding can be regarded as different interpretations of the same coding methods; arithmetic coders can be regarded as range encoders/decoders, and vice-versa. However, there is a tendency for arithmetic coders to be called range encoders when renormalization is performed a byte at a time, rather than one bit at a time (as is often the case with arithmetic coding), but this distinction is not definitive. When renormalization is applied a byte at a time, rather than with each output bit, there is a very slight reduction in compression, but the range encoder may be faster as a result.

When implemented in the manner described in G N N Martin's 1979 paper, range encoders are free from patents relating to arithmetic coding, even though they're the same thing in practice.

US patents on arithmetic coding

A variety of specific techniques for arithmetic coding are covered by US patents. Some of these patents may be essential for implementing the algorithms for arithmetic coding that are specified in some formal international standards. When this is the case, such patents are generally available for licensing under what is called "reasonable and non-discriminatory" (RAND) licensing terms (at least as a matter of standards-committee policy). In some well-known instances (including some involving IBM patents) such licenses are available free, and in other instances, licensing fees are required. The availability of licenses under RAND terms does not necessarily satisfy everyone who might want to use the technology, as what may be "reasonable" fees for a company preparing a proprietary software product may seem much less reasonable for a free software or open source project.

At least one significant compression software program, bzip2, deliberately discontinued the use of arithmetic coding in favor of Huffman coding due to the patent situation. Also, encoders and decoders of the JPEG file format, which has options for both Huffman encoding and arithmetic coding, typically only support the Huffman encoding option, due to patent concerns; the result is that nearly all JPEGs in use today use Huffman encoding.^[1]

Some US patents relating to arithmetic coding are listed below.

• U.S. Patent 4,122,440 — (IBM) Filed March 4, 1977, Granted 24 October 1978 (Now expired)
• U.S. Patent 4,286,256 — (IBM) Granted 25 August 1981
• U.S. Patent 4,467,317 — (IBM) Granted 21 August 1984
• U.S. Patent 4,652,856 — (IBM) Granted 4 February 1986
• U.S. Patent 4,891,643 — (IBM) Filed 15 September 1986, granted 2 January 1990
• U.S. Patent 4,905,297 — (IBM) Filed 18 November 1988, granted 27 February 1990
• U.S. Patent 4,933,883 — (IBM) Filed 3 May 1988, granted 12 June 1990
• U.S. Patent 4,935,882 — (IBM) Filed 20 July 1988, granted 19 June 1990
• U.S. Patent 4,989,000 — Filed 19 June 1989, granted 29 January 1991
• U.S. Patent 5,099,440 — (IBM) Filed 5 January 1990, granted 24 March 1992
• U.S. Patent 5,272,478 — (Ricoh) Filed 17 August 1992, granted 21 December 1993

Note: This list is not exhaustive. See the following link for a list of more patents.^[2] The Dirac codec uses arithmetic coding and is not patent pending.^[3]

Patents on arithmetic coding may exist in other jurisdictions, see software patents for a discussion of the patentability of software around the world.

Benchmarks and other technical characteristics

Every programmatic implementation of arithmetic encoding has a different compression ratio and performance. While compression ratios vary only a little (usually under 1%) the code execution time can vary by a factor of 10. Choosing the right encoder from a list of publicly available encoders is not a simple task because performance and compression ratio depend also on the type of data, particularly on the size of the alphabet (number of different symbols). One of two particular encoders may have better performance for small alphabets while the other may show better performance for large alphabets. Most encoders have limitations on size of the alphabet and many of them are designed for dual alphabet only (zero and one).

See also

• Data compression

References

1. ^ [1]
2. ^ [2]
3. ^ [3]

• Rissanen, Jorma (May 1976). "Generalized Kraft Inequality and Arithmetic Coding" (PDF). IBM Journal of Research and Development 20 (3): 198–203. http://domino.watson.ibm.com/tchjr/journalindex.nsf/4ac37cf0bdc4dd6a85256547004d47e1/53fec2e5af172a3185256bfa0067f7a0?OpenDocument. Retrieved 2007-09-21. 
• Rissanen, J.J.; Langdon, G.G., Jr. (March 1979). "Arithmetic coding" (PDF). IBM Journal of Research and Development 23 (2): 149–162. http://researchweb.watson.ibm.com/journal/rd/232/ibmrd2302G.pdf. Retrieved 2007-09-22. 
• Witten, Ian H.; Neal, Radford M.; Cleary, John G. (June 1987). "Arithmetic Coding for Data Compression" (PDF). Communications of the ACM 30 (6): 520–540. doi:10.1145/214762.214771. http://www.stanford.edu/class/ee398a/handouts/papers/WittenACM87ArithmCoding.pdf. Retrieved 2007-09-21. 
• MacKay, David J.C. (September 2003). "Chapter 6: Stream Codes" (PDF/PostScript/DjVu/LaTeX). Information Theory, Inference, and Learning Algorithms. Cambridge University Press. ISBN 0-521-64298-1. http://www.inference.phy.cam.ac.uk/mackay/itila/book.html. Retrieved 2007-12-30. 

External links

• Paul E. Black, arithmetic coding at the NIST Dictionary of Algorithms and Data Structures.
• Newsgroup posting with a short worked example of arithmetic encoding (integer-only).
• PlanetMath article on arithmetic coding
• Anatomy of Range Encoder The article explains both range and arithmetic coding. It has also code samples for 3 different arithmetic encoders along with performance comparison.
• Introduction to Arithmetic Coding. 60 pages.
• Eric Bodden, Malte Clasen and Joachim Kneis: Arithmetic Coding revealed. Technical Report 2007-5, Sable Research Group, McGill University.
• Arithmetic Coding + Statistical Modeling = Data Compression by Mark Nelson.