Range Coding
Range coding is the integer-arithmetic variant of arithmetic coding, replacing floating-point operations with an interval low bound and width, which avoids precision problems and carries fewer patent restrictions.
Purpose
It achieves near-entropy compression with integer arithmetic, serving as a patent-free replacement for arithmetic coding.
Mechanism
Maintain an interval [low, low+range); for each symbol, subdivide the interval by cumulative probability and renormalize, emitting the high-order bits that have become fixed. It is mathematically equivalent to arithmetic coding but uses integer intervals instead of floating point.
Use cases
- Entropy coding back end of PPMd
- General-purpose compression implementations
- Patent-free arithmetic coding replacement