edVirtus Reference

What Is Arithmetic Coding?

How Does Arithmetic Coding Work?

Preview: Learn more about arithmetic coding and how it achieves highly efficient lossless data compression.

Arithmetic coding is a lossless entropy-coding technique that compresses data by representing an entire sequence of symbols as a single fractional number rather than assigning a separate binary codeword to each symbol. By encoding complete messages instead of individual characters or symbols, arithmetic coding can achieve compression performance that is very close to the theoretical limit established by Claude Shannon's information theory.

Like all entropy-coding methods, arithmetic coding exploits the fact that some symbols occur much more frequently than others. Instead of assigning shorter codewords to common symbols, as in Huffman coding, arithmetic coding repeatedly narrows a range of numbers between 0 and 1 according to the probability of each successive symbol. After the final symbol has been processed, any number lying within the remaining interval uniquely represents the entire message.

A useful analogy is locating a house on a map. Rather than assigning every house its own postcode, you progressively zoom into smaller and smaller regions of the map until only a single house remains. Arithmetic coding performs a similar process mathematically, repeatedly narrowing the interval until it uniquely identifies the transmitted sequence.

One of the principal advantages of arithmetic coding is that it is not restricted to assigning an integer number of bits to each symbol. Huffman coding, for example, can assign one, two, or three bits to individual symbols but cannot assign fractional bit lengths. Arithmetic coding effectively achieves fractional average code lengths over an entire message, allowing it to produce slightly better compression than Huffman coding, particularly when symbol probabilities are highly uneven or change continuously.

Arithmetic coding is especially effective when combined with adaptive probability models. As the encoder processes the message, it continually updates its estimate of the symbol probabilities, allowing the compression process to adapt automatically to the changing characteristics of the data. This adaptability contributes significantly to its excellent compression performance.

Because arithmetic coding reproduces the original information exactly, it is a lossless compression technique. It has therefore been widely used in image compression, document storage, facsimile transmission, and multimedia systems. Standards such as JPEG 2000, JBIG, HEVC, and several modern video codecs employ arithmetic coding or closely related techniques as their final entropy-coding stage.

It is important to distinguish arithmetic coding from Huffman coding. Both are entropy-coding techniques that exploit symbol probabilities, but Huffman coding assigns variable-length codewords to individual symbols, whereas arithmetic coding encodes the entire message as a single numerical value. Huffman coding is generally simpler to implement, while arithmetic coding usually achieves slightly higher compression efficiency.

Today, arithmetic coding is regarded as one of the most powerful lossless compression techniques. By approaching the theoretical entropy limit more closely than most alternative methods, it has become a key component of many modern image, video, and data-compression systems, demonstrating how sophisticated mathematical techniques can significantly reduce the amount of information that must be stored or transmitted.