An Introduction to Arithmetic Coding

TLDR

Arithmetic coding compresses data by mapping a data string to a fractional value between 0 and 1, differing from Huffman codes and unrelated to error‑control coding. The paper introduces arithmetic coding concepts through simple examples. The algorithm recursively partitions the [0,1] interval for each symbol, retaining a subinterval to encode the data, and decodes by comparing the code magnitude to reconstruct the successive partitions.

Abstract

Arithmetic coding is a data compression technique that encodes data (the data string) by creating a code string which represents a fractional value on the number line between 0 and 1. The coding algorithm is symbolwise recursive; i.e., it operates upon and encodes (decodes) one data symbol per iteration or recursion. On each recursion, the algorithm successively partitions an interval of the number line between 0 and 1, and retains one of the partitions as the new interval. Thus, the algorithm successively deals with smaller intervals, and the code string, viewed as a magnitude, lies in each of the nested intervals. The data string is recovered by using magnitude comparisons on the code string to recreate how the encoder must have successively partitioned and retained each nested subinterval. Arithmetic coding differs considerably from the more familiar compression coding techniques, such as prefix (Huffman) codes. Also, it should not be confused with error control coding, whose object is to detect and correct errors in computer operations. This paper presents the key notions of arithmetic compression coding by means of simple examples.