Arithmetic Coding by Interval Subdivision

A prefix code spends at least one bit on any symbol that appears at all, because a codeword must have positive length. For a source where one symbol dominates, that constraint alone can multiply the encoded size by a large factor. Arithmetic coding removes the constraint by abandoning per-symbol codewords entirely: the entire message is represented as one number, chosen from a range whose width is the product of the symbol probabilities.

The message as a shrinking interval

Fix an order over the alphabet and assign each symbol a subinterval of $[0,1)$ proportional to its probability. Encoding maintains a current interval $[lo, hi)$. For each symbol, the encoder replaces the interval with the subinterval corresponding to that symbol, scaled to the current width:

$$lo’ = lo + w \cdot c(x), \qquad hi’ = lo + w \cdot (c(x) + p(x))$$

where $w = hi - lo$, and $c(x)$ is the cumulative probability of all symbols before $x$. After $n$ symbols the width is the product $\prod_{i=1}^{n} p(x_i)$, so the interval length equals the probability of the entire message under the model. Any number inside the final interval identifies the message uniquely, and the shortest binary fraction inside it is the codeword.

The cost follows immediately. To specify a number inside an interval of width $w$, about $-\log_2 w$ bits are needed, and $-\log_2 w = \sum_i -\log_2 p(x_i)$, which is the message’s self-information. The encoder achieves exactly the ideal code length, up to the rounding needed to land inside the interval, and that rounding costs at most two bits for the whole message rather than per symbol. This is the reason the method approaches entropy with no per-symbol penalty.

Decoding is the inverse operation and requires no search. Start with the same initial interval and read bits from the codeword until the accumulated value falls inside some symbol’s subinterval; emit that symbol; narrow the interval the same way the encoder did; continue. The decoder never needs to know the message length in advance if the model supplies an end-of-message symbol, and the number of symbols is implicit in the process.

Renormalization and finite precision

The description above uses exact rational arithmetic, which is not what implementations do. A 64-bit integer interval narrows by a factor of roughly $2^{-1}$ per bit of information, so a stream carrying 64 bits or more of information exhausts the width of the state and the split eventually rounds to nothing. The standard remedy is renormalization: when the interval lies entirely in the lower or upper half of the current range, the corresponding bit is determined and can be emitted immediately, and the interval is shifted and rescaled.

Concretely, with the interval held as integers in $[0, 2^{32})$ or similar, two conditions trigger output:

• If $hi < \text{HALF}$, the leading bit is 0: emit 0, shift both endpoints left by one bit, and continue.
• If $lo \ge \text{HALF}$, the leading bit is 1: emit 1, subtract HALF from both, shift left, and continue.

A third condition handles the interval that straddles the midpoint but is narrow enough that the next bit is not yet determined. If $lo \ge \text{QUARTER}$ and $hi < \text{THREE_QUARTERS}$, the interval will eventually fall on one side after further narrowing; the encoder counts these cases and emits the pending bit followed by its complement once the side is known. This is the E3 condition in the standard formulation, and omitting it causes the encoder to stall with an interval that never leaves the middle region.

# Binary arithmetic coder, 32-bit state, with the E3 (pending bit) rule.
TOP = 1 << 32
HALF = TOP >> 1
QUARTER = TOP >> 2
THREE_Q = QUARTER * 3

class Encoder:
    def __init__(self):
        self.lo, self.hi = 0, TOP - 1
        self.pending, self.out = 0, []

    def bit(self, b, p1):
        # p1 is P(bit == 1) scaled to 16 bits; symbol 0 occupies the low interval
        rng = self.hi - self.lo
        split = self.lo + (rng * (65536 - p1)) // 65536
        if b == 0:
            self.hi = split - 1
        else:
            self.lo = split
        while True:
            if self.hi < HALF:                      # interval in the lower half
                self.out.append(0)
                self.out.extend([1] * self.pending)
                self.pending = 0
            elif self.lo >= HALF:                   # interval in the upper half
                self.out.append(1)
                self.out.extend([0] * self.pending)
                self.pending = 0
                self.lo -= HALF
                self.hi -= HALF
            elif self.lo >= QUARTER and self.hi < THREE_Q:
                self.pending += 1                   # middle bit still undecided
                self.lo -= QUARTER
                self.hi -= QUARTER
            else:
                break
            self.lo = (self.lo << 1) & (TOP - 1)
            self.hi = (self.hi << 1) & (TOP - 1)

    def finish(self):
        self.pending += 1                           # one bit disambiguates the end
        if self.lo < QUARTER:
            self.out.append(0)
            self.out.extend([1] * self.pending)
        else:
            self.out.append(1)
            self.out.extend([0] * self.pending)
        return self.out

The masking after each shift keeps the state within the word size. Without it the endpoints drift upward and the comparisons against HALF stop meaning what they should. The pending counter is the E3 mechanism: it accumulates ambiguous middle bits and flushes them as a run once the interval commits to a side. The decoder mirrors every branch, subtracting the same offsets from its value and pulling a bit on each shift, and it must read exactly the bits the encoder wrote in the order written.

The precision requirement is a genuine constraint. The total of the model’s frequencies must stay below $2^{32} - 2^{32}/4 + 2$, the bound under which the encoder’s split point always lands strictly inside the current interval. The arithmetic itself then never needs more than 32 bits, provided the width never falls below a quarter of the full range, which renormalization guarantees. If the model is allowed to violate the bound, the split can land on an endpoint, the smallest symbol’s subinterval can collapse to zero width, and the symbol becomes unencodable, a failure that manifests as a decoder that cannot reproduce the input rather than as an exception.

Adaptive models and the cost of learning

A static model requires transmitting the frequency table, and for a short message that table dominates the output. Adaptive arithmetic coding avoids the table by updating counts after each symbol, with the decoder performing the identical update. The model cost is then zero at the start and grows as the counts accumulate, which is the same trade-off as adaptive Huffman but without the per-symbol rounding loss.

The price is that early symbols are coded under a poor model. For an alphabet of $k$ symbols with initial count 1 each, the first symbol costs $\log_2 k$ bits regardless of its true probability, and the model converges as counts accumulate. A rescaling rule is needed to keep the total bounded: when the total reaches the limit, halve all counts, rounding up so no count reaches zero. Halving loses precision but preserves the relative frequencies, and the loss is bounded.

A subtler cost is that adaptive coding cannot be parallelized across the stream in the obvious way, because every symbol’s interval depends on all previous symbols through the model. Block-independent coding, where each block starts from a fresh model, restores parallelism at the cost of resetting the model per block. This is one of the reasons Range Coding and rANS in Modern Compressors displaced arithmetic coding in high-throughput settings: rANS keeps several interleaved states so that independent symbol streams can be coded in parallel within one block.

Where the interval view becomes exact and where it does not

The arithmetic-coding construction is exact in the sense that the encoded length equals the negative logarithm of the message probability plus a rounding term bounded by a constant. The bound is not a per-symbol approximation; it is a constant for the message, and it is what makes arithmetic coding the reference against which other entropy coders are measured.

Three practical qualifications apply.

Termination. The encoder must emit enough bits for the decoder to identify a point inside the final interval, plus a convention for signalling the end. Emitting the shortest binary fraction strictly inside the interval plus a trailing 1 bit is sufficient; the extra bit resolves the case where the interval endpoint is exactly representable and the decoder’s comparison must distinguish the endpoint from the interior. The overhead is at most two bits.

Integer division and bias. Using floor division for the split introduces a bias that depends on the state size. At 32 bits the bias is negligible in rate terms but not zero, and a decoder using a different rounding rule will diverge. The split rule must be specified as part of the format, not left to the implementation, which is why arithmetic-coded formats are precise about the frequency scaling. A count of 1 in a total that is a small fraction of the state size is representable, but the width it receives is the floor of the ideal $w \cdot p$ rather than the exact value, and the shortfall shows up as a fractional bit per rare symbol: floor division can only shorten a subinterval, never lengthen it.

Model mismatch. The interval width is the product of model probabilities, not true probabilities. If the model assigns probability $q$ where the true probability is $p$, the encoded length is $-\log_2 q$ and the excess over the entropy is the Kullback–Leibler divergence $D(p | q)$. A model that is wrong by a factor of 2 on a symbol’s probability costs one bit per occurrence of that symbol, which is why model quality dominates encoder quality in practice.

That divergence term is additive across symbols and does not shrink with message length, so a mismatched model produces a rate gap that is proportional to the message, not a fixed overhead. Halving the model error halves the gap, which is why small improvements in probability estimation are worth pursuing long after the coder itself has been made exact.

Bit order and symmetry. The bits emitted by renormalization are the high-order bits of the final code value, so they must be written in the order produced, and the decoder must consume them in the same order. An encoder that buffers bits and writes them in blocks must preserve that order; a decoder that reads ahead must not consume a bit it has not yet needed, or the two will desynchronize on the next symbol even though the arithmetic is correct. The standard test for an implementation is a round trip over every message of length up to four symbols from a small alphabet, with a model whose probabilities are deliberately not powers of two, the case where rounding errors accumulate fastest.

The interval representation also clarifies why arithmetic coding handles deterministic contexts gracefully. A symbol with probability 1 contributes zero width change: the interval is unchanged and no bits are emitted. A prefix code cannot represent that, since every codeword has length at least one; arithmetic coding can, and the difference is exactly the redundancy that Prefix Codes, the Kraft Inequality, and Why Huffman Is Optimal identifies as the ceiling penalty.