Arithmetic coding is a method of lossless data compression that converts a sequence of symbols into a compact bitstream using a probability model. Rather than assigning a separate codeword to each symbol, it represents the sequence through progressively narrower numerical intervals. It separates the task of estimating symbol probabilities from the task of encoding them, allowing the same coder to work with different statistical models. (www2.isye.gatech.edu)
Encoding and decoding
In the idealized construction, encoding begins with the half-open interval ([0,1)). For each symbol, the current interval is partitioned into subintervals proportional to the model’s probability distribution, and the subinterval corresponding to that symbol becomes the new interval. (arxiv.org)
Let the current interval be ([L,U)), and let (C(s)) be the cumulative probability of symbols preceding (s) in an agreed ordering. If (p(s)) is its probability, the update is
[ L'=L+(U-L)C(s),\qquad U'=L+(U-L)\bigl(C(s)+p(s)\bigr). ]
After all symbols have been processed, the encoder supplies enough binary digits to identify a value within the final interval. The decoder reconstructs the successive subdivisions and determines which symbol contains the code value at each step. Encoder and decoder must agree on probabilities, symbol ordering, numerical rules, and message termination. (www2.isye.gatech.edu)
Worked example
Consider a fixed model with (p(A)=1/2), (p(B)=1/4), and (p(C)=1/4), ordered as (A,B,C). Applying the interval-update rule to the message AB gives:
| Step | Selected symbol | Resulting interval |
|---|---|---|
| Initial state | — | ([0,1)) |
| First symbol | A | ([0,1/2)) |
| Second symbol | B | ([1/4,3/8)) |
The binary fraction (0.0101_2=5/16) lies inside the final interval. Its binary-prefix interval, ([5/16,6/16)), also lies entirely within it. These calculations illustrate how a binary representation can distinguish a message without assigning independent codewords to its symbols.
The decoder still needs to know that the message has two symbols, or encounter an explicitly encoded end-of-message symbol; the code value alone does not establish when decoding should stop. (www2.isye.gatech.edu)
Compression efficiency
The ideal final interval has width equal to the model probability (P(x)) of the sequence. Consequently, its required description length is approximately the sequence’s self-information,
[ -\log_2 P(x), ]
measured in bits, with additional termination and implementation overhead. For a correctly modeled independent source, the average rate approaches its information entropy as message length increases, consistent with the source coding theorem. (arxiv.org)
Unlike symbol-by-symbol Huffman coding, arithmetic coding does not require each symbol to consume an integer number of bits independently. It can therefore approach the ideal rate even when highly probable symbols contribute substantially less than one bit on average. This is an average contribution across a sequence, not a physically fractional bit. (www2.isye.gatech.edu)
Probability models
A static model uses probabilities fixed for a message or block. An adaptive model updates estimates as symbols are processed; the decoder performs matching updates using symbols already recovered, avoiding transmission of each update. Context-dependent models estimate probabilities from preceding symbols or other information available to both sides. Compression depends on how accurately the model predicts the data, not solely on the coding mechanism. (www2.isye.gatech.edu)
Practical implementation
Implementations generally use bounded integer registers rather than indefinitely precise fractions. Renormalization rescales the interval and releases output digits as coding progresses; deferred-bit or carry-handling mechanisms resolve digits that are not yet determined. Consistent rounding and nonzero subintervals are necessary for correct decoding. (arxiv.org)
Implementation techniques include low-precision interval calculations and shift-and-add operations that reduce expensive arithmetic. Multisymbol coders also require cumulative-frequency lookup and updates, making the choice of data structures important. Coding, modeling, and probability estimation can be implemented as separate components. (researchcommons.waikato.ac.nz)
Development and applications
Ian H. Witten, Radford M. Neal, and John G. Cleary published an influential implementation in 1987. Alistair Moffat, Neal, and Witten subsequently described refinements in Arithmetic Coding Revisited in 1998, including support for wider probability ranges and reduced arithmetic costs. (doi.org)
Arithmetic coding also appears in multimedia compression. Context-based Adaptive Binary Arithmetic Coding (CABAC), specified in H.264/AVC, codes binary decisions with adaptive probability contexts. The arithmetic-coding stage is lossless even when the larger video-compression process includes lossy operations. (itu.int)
References
- Arithmetic Coding for Data Compressionwww2.isye.gatech.edu
- Introduction to Arithmetic Coding -- Theory and Practicearxiv.org
- Arithmetic coding revisitedresearchcommons.waikato.ac.nz
- ITU-T Rec. H.264 (08/2024): Advanced video coding for generic audiovisual servicesitu.int
- ITU-T Rec. H.264 (06/2019): Advanced video coding for generic audiovisual servicesitu.int