Fundamental Data Compression

Chapter 6

Arithmetic coding

Arithmetic coding is important historically because it was at the time the most successful alternative to Huffman coding after a gap of 25 years. It is superior in performance to the Huffman coding especially when the alphabet is fairly small. The arithmetic method extended the early coding work by Shannon, Fano and Elias and was developed largely by Pasco (1976), Rissanene (1976, 1984), and Langdon (1984). It bypasses the idea of replacing every single input symbol with a codeword. Instead, it encodes a stream of input symbols with a single fraction as the compressed output.

6.1 Probabilities and subintervals

The idea comes first from Shannon’s observation in 1948 that messages N symbols long may be encoded by their ...