Arithmetic Coding

Mapping Messages to Intervals

Instead of replacing each symbol with a fixed prefix code like Huffman coding,arithmetic coding represents an entire sequence of symbols as a single real number within the interval [0, 1). As the message grows longer, the interval grows smaller. Any number within that final bounded interval can be decoded to reconstruct the original message, provided the decoder knows the message length and the exact same probability model.

Nested Fractional Intervals

The interval is divided according to the probability model. When a symbol is encoded, its assigned sub-interval becomes the new total interval for the next step. Because exact arithmetic coding requires infinite precision, it is implemented with integer bounds and rescaling in practice. However, this demonstration explicitly traces the exact nested rational fractions for a short bounded message length without underflow or scaling limits.

Worked Example: Encoding 'AB'

Assume an alphabet {A, B, C} with the weights (2, 1, 1). Summing these gives a denominator of 4, so the probabilities are 2/4 for A, 1/4 for B, and 1/4 for C. The initial interval is [0, 1).

First symbol 'A': The cumulative distribution assigns A to the first 2/4 of the current interval. The interval becomes [0, 2/4) or [0, 1/2). The width is now 1/2.
Second symbol 'B': B is assigned the segment from the 2nd quarter to the 3rd quarter. Within the new [0, 1/2) interval, B's portion starts at (2/4) * (1/2) = 1/4, and its width is (1/4) * (1/2) = 1/8. The end is 1/4 + 1/8 = 3/8.

The final interval for "AB" is [1/4, 3/8). The midpoint, 5/16, can unambiguously decode to "AB" if the receiver knows the length is 2 and the model is 2,1,1.

Interactive Experiment

You can test the previous derivation in the Arithmetic Coding module.

Ensure the Message input is AB.
Verify the Model is set to 2,1,1 (default).
Click Step to encode 'A'. The interval [0, 1/2) appears.
Click Finish to encode 'B'. The interval [1/4, 3/8) appears.
The results panel displays the final interval [1/4, 3/8), width 1/8, and the exact rational midpoint 5/16. Click Reset to rewind without changing Message or Model.

Limitations and Assumptions

This demonstration explicitly calculates the bounds using exact rational fractions. In a production compressor, infinite precision is impossible. Real arithmetic coders use finite-bit integer registers, shifting bits out as the top and bottom bounds converge, and employing bit-stuffing to prevent underflow.

Furthermore, this bounded visualizer requires the decoder to be provided the message length and probability model as side information to know how to decode and when to stop. The decoder actually walks the model subintervals from the midpoint; it does not use the entered symbols as its answer. On the fixed [0,1) plot a short final interval can become subpixel; the fraction table is the authoritative readout, with decimal displays rounded to six places. Production systems often encode a special EOF symbol or stream the length first.

References

The implementation matches textbook definitions of finding probability segments.

CMU 15-750: Algorithms in the Real World, Fall 2023. Lecture 2: Data Compression. Defines mapping sequences to probability intervals and exact calculation of bounds.

Arithmetic Coding