# arithmetic coding

(algorithm)

**Definition:**
A minimal variable-length message coding based on the frequency of each character. The message is represented by a fraction which is the repeated offset-plus-product reduction of the range (offset) and probability (product) of each character.

**See also**
*Huffman coding*, *Shannon-Fano coding*.

*Note:
Shannon-Fano is a minimal prefix code. Huffman is optimal for character coding (one character-one code word) and simple to program. Arithmetic coding is even more compact, since it can allocate fractional bits, but is more complicated and patents cover some uses. *

*
** Range encoding is essentially the same, but uses integers and integer ranges instead of fractions. The implementation in ***Martin** 1979 is thought to not be covered by patents.

Author: PEB

## Implementation

Jürgen Abel's excellent Range and Arithmetic Coding resources (C, Java, C++), with links to papers, people, and implementations. Mark Nelson's article on theory development and implementation (C).
## More information

An introduction to data compression methods. Wikipedia entries for Arithmetic coding and Range encoding.

**Ian H. Witten, Radford M. Neal**, and **John G. Cleary**, *Arithmetic Coding for Data Compression*, CACM 30(6):520-540, June 1987.

**G. N. N. Martin**, *Range encoding: an algorithm for removing redundancy from a digitised message*, Video & Data Recording Conference, Southampton, UK, July 1979.

Go to the
Dictionary of Algorithms and Data
Structures home page.

If you have suggestions, corrections, or comments, please get in touch
with Paul Black.

Entry modified 12 December 2011.

HTML page formatted Mon Feb 2 13:10:39 2015.

Cite this as:

Paul E. Black, "arithmetic coding", in
*Dictionary of Algorithms and Data Structures* [online], Vreda Pieterse and Paul E. Black, eds. 12 December 2011. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/arithmeticCoding.html