Arithmetic coding
Arithmetic coding represents a symbol sequence by successively narrowing a numeric interval according to a shared probability model.
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
Citations
- 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
- RFC 6716: Definition of the Opus Audio Codec, sections 4.1 and 5.1.5, range coding and finalization
- Hesela: exact rational interval worksheet, source and regression tests
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.