Arithmetic coding is a method for lossless data compression. It is a form of variable-length entropy encoding, but where other entropy encoding techniques 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). Lossless data compression is a class of data compression algorithms that allows the exact original data to be reconstructed from the compressed data. ... In coding theory a variable-length code is a code which maps source symbols to a variable number of bits. ... In information theory an entropy encoding is a data compression scheme that assigns codes to symbols so as to match code lengths with the probabilities of the symbols. ...

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. In information theory, the source coding theorem (Shannon 1948) informally states that: N i. ... An abstract model (or conceptual model) is a theoretical construct that represents something, with a set of variables and a set of logical and quantitative relationships between them. ...

Example: a simple, static model for describing the output of a particular monitoring instrument over time might be: Look up static in Wiktionary, the free dictionary. ...

• 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; the first and only time this symbol appears in the data stream, the decoder will know that the entire stream has been decoded.)

Models can handle other alphabets than the simple four-symbol set chosen for this example, of course. 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. Adaptive coding refers to variants of entropy encoding methods of lossless data compression. ...

A simplified example

Now we discuss how a sequence of symbols is encoded. As a motivating example, consider the following simple problem: we have a sequence 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 combinations is never used. In computer science, a block code is a type of channel coding. ...

Instead, we 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₃. We then 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, we can simply convert back to base 3, round to 6 digits, and recover the string.

Encoding and decoding

Now we generalize this approach. 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. In mathematics, interval is a concept relating to the sequence and set-membership of one or more numbers. ...

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 identifies, unambiguously, the sequence of symbols that produced it. Anyone who has the final interval and the model 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.

Suppose we are trying to decode a message encoded with the four-symbol model described above. The message is encoded in the fraction 0.538 (for clarity, we are using decimal, instead of binary; we are also assuming that whoever gave us the encoded message gave us only as many digits as needed to decode the message. We will discuss both issues later.) Image File history File links This is a lossless scalable vector image. ... Image File history File links This is a lossless scalable vector image. ...

We start, as the encoder did, with the interval [0,1), and using the same model, we divide it into the same four sub-intervals that the encoder must have. Our fraction 0.538 falls into the sub-interval for NEUTRAL, [0, 0.6); this indicates to us that the first symbol the encoder read must have been NEUTRAL, so we can write that down as the first symbol of our message.

We then 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)

Our fraction of .538 is within the interval [0.48, 0.54); therefore the second symbol of the message must have been NEGATIVE.

Once more we 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).

Our fraction of .538 falls within the interval of the END-OF-DATA symbol; therefore, this must be our next symbol. Since it is also the internal termination symbol, it means our decoding is complete. (If the stream was not internally terminated, we would need to know where the stream stops from some other source -- otherwise, we would continue the decoding process 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 our 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; we could have encoded the same message in the binary fraction .10001010 (equivalent to .5390625 decimal) at a cost of only 8 bits. (Note that 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 article is about the unit of information. ...

This 8 bit output is larger than the information content, or entropy of our 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. We claimed symbol probabilities of [.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 you could encode the same NEUTRAL NEGATIVE ENDOFDATA message 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 yield a size gain, especially if the probability model is off. Claude Shannon In information theory, the Shannon entropy or information entropy is a measure of the uncertainty associated with a random variable. ...

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 that 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 now that the precision is known, so are the binary ranges we'll be able to use. The precision of a value describes the number of digits that are used to express that value. ...

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. 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. Dasher running under Linux Dasher is a computer accessibility tool enabling users to enter text efficiently using a pointing device rather than a keyboard. ...

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 often approach optimal entropy encoding much more closely than Huffman can. In computer science and information theory, Huffman coding is an entropy encoding algorithm used for lossless data compression. ... The radix (Latin for root), also called base, is the number of various unique symbols (or digits or numerals) a positional numeral system uses to represent numbers. ... In information theory an entropy encoding is a data compression scheme that assigns codes to symbols so as to match code lengths with the probabilities of the symbols. ...

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 example, if our symbols were 0 and 1, and their 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:

1 - (0.625(−log₂0.625) + 0.375(−log₂0.375)) ≈ 4.6%.

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

1 - (0.95(−log₂0.95) + 0.05(−log₂0.05)) ≈ 71.4%.

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, if we were to group sequences of three symbols before encoding, then we would have 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. Range encoders are also rumoured to be free from patents relating to arithmetic coding, even though they're the same thing in practice. Range encoding is a form of arithmetic coding, a data compression method, that is believed to be free from arithmetic coding related patents. ...

The idea behind range encoding is that, instead of starting with the interval [0,1) and dividing it into sub-intervals proportional to the probability of each symbol, the encoder starts with a large range of non-negative integers, such as 000,000,000,000 to 999,999,999,999, and divides it into sub-ranges proportional to the probability of each symbol. When the sub-ranges get narrowed down sufficiently that the leading digits of the final result are known, those digits may be shifted "left" out of the calculation, and replaced by digits shifted in on the "right" -- each time this happens, it is roughly equivalent to a retroactive multiplication of the size of the initial range.

The corresponding arithmetic coding interpretation can be found by regarding the non-negative integers in the range as being the numerators of fractions in the interval [0,1). The common denominator is the size of the original range (once retroactively multiplied). In the same way, arithmetic coding can be reinterpreted as range encoding.

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.

US patents on arithmetic coding

A variety of specific techniques for arithmetic coding have been protected 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 are 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 for 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. A patent is a set of exclusive rights granted by a state to a patentee for a fixed period of time in exchange for a disclosure of an invention. ... Reasonable and Non Discriminatory Licensing (RAND) is a term for a type of licensing typically used during standardisation processes. ... Clockwise from top: The logo of the GNU Project (the GNU head), the Linux kernel mascot Tux the Penguin, and the FreeBSD daemon Free software is a term coined by Richard Stallman and the Free Software Foundation[1] to refer to software that can be used, studied, and modified without... Open source refers to projects that are open to the public and which draw on other projects that are freely available to the general public. ...

One company well known for innovative work and patents in the area of arithmetic coding is IBM. There are some in the data compression community who think that no kind of practical and effective arithmetic coding can be performed in the US without infringing on valid patents held by IBM or others; others think that this is just a persistent urban legend considering that effective designs for arithmetic coding have now been in use long enough for many of the original patents to have expired. Nevertheless, because the patent law provides no "bright line" test that proactively allows you to determine whether a court would find a particular use to infringe a patent, and as even investigating a patent more closely to determine what it actually covers could actually increase the damages awarded in an unfavorable judgement, the patenting of these techniques has nevertheless caused a chilling effect on their use. International Business Machines Corporation (IBM, or colloquially, Big Blue) (NYSE: IBM) (incorporated June 15, 1911, in operation since 1888) is headquartered in Armonk, New York, USA. The company manufactures and sells computer hardware, software, and services. ... An urban legend or urban myth is similar to a modern folklore consisting of stories often thought to be factual by those circulating them. ... A bright-line rule is a clear-cut, easy to make decision. ... It has been suggested that Legal terrorism be merged into this article or section. ...

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] The correct title of this article is . ... In computing, JPEG (pronounced JAY-peg; IPA: ) is a commonly used standard method of compression for photographic images. ...

Some US patents relating to arithmetic coding are listed below.

• Patent 4,122,440 — (IBM) Filed March 4, 1977, Granted 24 October 1978 (Now expired)
• Patent 4,286,256 — (IBM) Granted 25 August 1981 (presumably now expired)
• Patent 4,467,317 — (IBM) Granted 21 August 1984 (presumably now expired)
• Patent 4,652,856 — (IBM) Granted 4 February 1986 (presumably now expired)
• Patent 4,891,643 — (IBM) Filed 15 September 1986, granted 2 January 1990
• Patent 4,905,297 — (IBM) Granted 27 February 1990
• Patent 4,933,883 — (IBM) Granted 12 June 1990
• Patent 4,935,882 — (IBM) Granted 19 June 1990
• Patent 4,989,000 — Filed 19 June 1989, granted 29 January 1991
• Patent 5,099,440 — (IBM) Filed 5 January 1990, granted 24 March 1992
• 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] is the 63rd day of the year (64th in leap years) in the Gregorian calendar. ... Also: 1977 (album) by Ash. ... October 24 is the 297th day of the year (298th in leap years) in the Gregorian calendar. ... Year 1978 (MCMLXXVIII) was a common year starting on Sunday (link displays the 1978 Gregorian calendar). ... is the 237th day of the year (238th in leap years) in the Gregorian calendar. ... Year 1981 (MCMLXXXI) was a common year starting on Thursday (link displays the 1981 Gregorian calendar). ... is the 233rd day of the year (234th in leap years) in the Gregorian calendar. ... Year 1984 (MCMLXXXIV) was a leap year starting on Sunday (link displays the 1984 Gregorian calendar). ... is the 35th day of the year in the Gregorian calendar. ... Year 1986 (MCMLXXXVI) was a common year starting on Wednesday (link displays 1986 Gregorian calendar). ... is the 258th day of the year (259th in leap years) in the Gregorian calendar. ... Year 1986 (MCMLXXXVI) was a common year starting on Wednesday (link displays 1986 Gregorian calendar). ... January 2 is the 2nd day of the year in the Gregorian calendar. ... Year 1990 (MCMXC) was a common year starting on Monday (link displays the 1990 Gregorian calendar). ... is the 58th day of the year in the Gregorian calendar. ... Year 1990 (MCMXC) was a common year starting on Monday (link displays the 1990 Gregorian calendar). ... is the 163rd day of the year (164th in leap years) in the Gregorian calendar. ... Year 1990 (MCMXC) was a common year starting on Monday (link displays the 1990 Gregorian calendar). ... is the 170th day of the year (171st in leap years) in the Gregorian calendar. ... Year 1990 (MCMXC) was a common year starting on Monday (link displays the 1990 Gregorian calendar). ... is the 170th day of the year (171st in leap years) in the Gregorian calendar. ... Year 1989 (MCMLXXXIX) was a common year starting on Sunday (link displays 1989 Gregorian calendar). ... January 29 is the 29th day of the year in the Gregorian calendar. ... Year 1991 (MCMXCI) was a common year starting on Tuesday (link will display the 1991 Gregorian calendar). ... January 5 is the 5th day of the year in the Gregorian calendar. ... Year 1990 (MCMXC) was a common year starting on Monday (link displays the 1990 Gregorian calendar). ... is the 83rd day of the year (84th in leap years) in the Gregorian calendar. ... Year 1992 (MCMXCII) was a leap year starting on Wednesday (link will display full 1992 Gregorian calendar). ... August 17 is the 229th day of the year (230th in leap years) in the Gregorian calendar. ... Year 1992 (MCMXCII) was a leap year starting on Wednesday (link will display full 1992 Gregorian calendar). ... December 21 is the 355th day of the year (356th in leap years) in the Gregorian calendar. ... Year 1993 (MCMXCIII) was a common year starting on Friday (link will display full 1993 Gregorian calendar). ...

Patents on arithmetic coding may exist in other jurisdictions, see software patents for a discussion of the patentability of software around the world. Software patent does not have a universally accepted definition. ...

Benchmarks and other technical characteristics

Every programmatic implementation of arithmetic encoder has different compression ratio and performance. While compression ratios vary insignificantly (typically within 1%) the time of code execution may be different by the 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).

Some tests and benchmark reports can be found in the article Anatomy of Range Encoder. It describes a project where randomly generated data sample was passed to three known encoders for round trip compression and decompression and a printed report with timestamps was documented for each.

See also

• Data compression
• Range encoding
• Huffman coding
• Entropy encoding

In computer science and information theory, data compression or source coding is the process of encoding information using fewer bits (or other information-bearing units) than an unencoded representation would use through use of specific encoding schemes. ... Range encoding is a form of arithmetic coding, a data compression method, that is believed to be free from arithmetic coding related patents. ... In computer science and information theory, Huffman coding is an entropy encoding algorithm used for lossless data compression. ... In information theory an entropy encoding is a data compression scheme that assigns codes to symbols so as to match code lengths with the probabilities of the symbols. ...

References

• David J.C. MacKay (2003) Information theory, inference and learning algorithms, CUP, ISBN 0-521-64298-1, (also available online)

David J.C. MacKay (born April 22, 1967) is the professor of natural philosophy in the department of Physics at the University of Cambridge. ...

External links

• The on-line textbook: Information Theory, Inference, and Learning Algorithms, by David J.C. MacKay, explains arithmetic coding in Chapter 6.
• 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.