arithmetic-coding · shipping · also Arithmetic entropy coding

Arithmetic coding

Arithmetic coding represents a symbol sequence by successively narrowing a numeric interval according to a shared probability model.

Related Observatory article: Read on hesela.com

Mechanism: Each symbol selects a subinterval proportional to its model probability. Decoding also requires a stopping rule, such as a known message length or an end symbol; a tag inside the final interval alone does not specify when to stop. [1]

Implementation: Practical implementations such as Opus use integer state and renormalization. Model updates, rounding and finalization must match the decoder. Opus specifies one range-coding implementation; its format rules do not define every arithmetic coder or make the whole audio codec lossless. [2]

Example: With ordered probabilities A=3/4 and B=1/4 and externally known length two, AA occupies [0,9/16) and AB occupies [9/16,3/4). The shortest fully enclosed binary-prefix cells use 1 and 3 payload bits respectively. Each still occupies one packed byte before model and framing costs. Decoding the AB tag 5/8 with probabilities A=1/4 and B=3/4 instead produces BB. [3]

Relations

related
Entropy coding, Huffman coding, Asymmetric numeral systems

Citations

  1. Ian H. Witten, Radford M. Neal and John G. Cleary: Arithmetic Coding for Data Compression, CACM 30(6), 520-540 (1987), DOI 10.1145/214762.214771 (accessed 2026-11-18)
  2. RFC 6716: Definition of the Opus Audio Codec, sections 4.1 and 5.1.5, range coding and finalization (accessed 2026-11-18)
  3. Hesela: exact rational interval worksheet, source and regression tests (accessed 2026-11-18)
Sources & caveats
  • The example uses exact rational intervals and a declared dyadic-cell convention, not an Opus-compatible bitstream, finite-precision codec measurement or reproduction of paper results.

JSON: /data/terms/arithmetic-coding.json

Published by Hesela team · Updated

Report a correction · Editorial standards · Reuse guidance

Cite this page
Hesela team. Arithmetic coding. Hesela. 2026-11-19. https://hesela.dev/terms/arithmetic-coding/