Arithmetic coding: keep encoder and decoder in the same interval

A Huffman code assigns a whole number of bits to each symbol. Arithmetic coding assigns a narrowing interval to the whole message. The encoder gradually writes enough bits to identify that interval. The decoder uses the same model to reverse each subdivision.

Before this module, be comfortable with cumulative sums, integer division, and MSB-first bit I/O. The bit I/O module supplies the bit reader/writer. Here the central question is: after rounding, emitting bits, and changing coordinates, do both sides still mean the same interval?

Start with an interval you can draw

Use a static alphabet with frequencies A:2, B:1, EOF:1. The total is 4, so the initial real interval [0,1) is divided into:

Symbol	Cumulative frequency interval	Real interval
A	[0,2)	[0,1/2)
B	[2,3)	[1/2,3/4)
EOF	[3,4)	[3/4,1)

For AB, first choose A's half. Subdivide that half using the same proportions: B selects [1/4,3/8). EOF then selects its upper quarter, [11/32,12/32). A number inside the final interval identifies AB followed by its terminator.

Why EOF? Without a terminator or a separately supplied length, a point inside the interval for AB also lies in the larger interval for A. Padding bits do not tell the decoder when the message ends.

The exercise uses symbols 0–255 for bytes and symbol 256 for EOF. Both sides receive the same frequency table; transmitting that table is outside this API. Frequencies count occurrences, not bytes in the compressed output.

Replace fractions with inclusive integer endpoints

The exercise uses a 32-bit coding interval but 64-bit arithmetic for intermediate products. Start with low=0, high=2^32-1. Unlike the real interval above, both integer endpoints are included, so its size is high-low+1.

Let C[s] be the sum of frequencies for symbols smaller than s, and let T=C[257]. To encode symbol s:

R = high - low + 1
base = low
low  = base + floor(R * C[s]     / T)
high = base + floor(R * C[s + 1] / T) - 1

Both expressions use the old low. Saving base makes this explicit. The minus one changes an exclusive upper partition boundary into an inclusive endpoint. Without it, neighboring symbol intervals overlap.

Try this with a toy four-bit state [0,15] and the 2:1:1 model. A occupies [0,7], B [8,11], and EOF [12,15]. There are no gaps and no overlaps. A zero-frequency symbol owns no interval; every byte you encode, and EOF, must have positive frequency.

We use four bits only for hand traces. The implementation uses 32 bits and total frequency at most 2^20; a product can reach 2^52, so a 32-bit multiply is insufficient even though the stored interval has 32-bit endpoints.

Emit information before the interval runs out of room

Repeated subdivision eventually makes an integer interval too narrow. Renormalization removes information already determined and expands the remaining uncertainty.

Write H=2^31, Q=2^30, and 3Q=3*2^30. After each symbol, repeat the following rules in order until none applies:

Case	Condition	Action before scaling
E1: lower half	high < H	Emit 0
E2: upper half	low >= H	Emit 1; subtract H from both endpoints
E3: middle half	low >= Q and high < 3Q	Count one pending bit; subtract Q from both endpoints

After any case, set low=2*low, high=2*high+1. Including the final +1 preserves the entire inclusive integer range.

Emitting a resolved bit b also emits every pending bit as 1-b, then clears the pending count. E3 emits nothing immediately.

Crossing the midpoint alone does not trigger E3. In four-bit coordinates, [3,12] crosses 8 but is not contained in [4,11]; none of the rules applies. The earlier slogan “straddles the midpoint” misses the condition that makes expansion safe.

Trace the difficult case: deferred bits

Use the four-bit model A:1, B:2, EOF:1. Now B owns the middle half [4,11]. Encode BB and EOF:

Event	Interval before normalization	Action	Interval afterward	Bits written
First B	[4,11]	E3, pending=1	[0,15]	none
Second B	[4,11]	E3, pending=2	[0,15]	none
EOF	[12,15]	E2; resolve pending	[8,15]	100
Continue normalizing EOF	[8,15]	E2	[0,15]	1
Finish	[0,15]	Finalization below	—	01

The bits are 100101, padded to the byte 10010100 (0x94). Because all partitions in this example are exact powers of two, the 32-bit implementation produces the same byte.

Why complements? A middle-half interval has unresolved leading alternatives 01... and 10.... Removing its second bit postpones that distinction. Once a later bit resolves the side, each postponed position is the opposite bit. Writing the resolved bit repeatedly instead would select the wrong original interval.

Decode by asking which partition contains the code value

Read the first 32 stream bits into code; after physical input ends, this format supplies zero bits. Maintain:

low <= code <= high

The inverse of the integer subdivision is:

R = high - low + 1
v = floor(((code - low + 1) * T - 1) / R)
find s such that C[s] <= v < C[s+1]

For toy state [0,15], total 4, and code=11, the value is floor((12*4-1)/16)=2, selecting B in the 2:1:1 model. At code=12, the value becomes 3, selecting EOF. These boundary values test the off-by-one arithmetic better than a point in the middle of a partition.

After selecting a non-EOF symbol, apply the same interval update and normalization rules. E2 subtracts H from code too; E3 subtracts Q. Every scaling step shifts code left and reads one new bit. The decoder does not need a pending-bit counter: the emitted stream already expresses the encoder's resolved choices.

The invariant explains correctness inductively. Initially the code lies in the full interval. Subdivision selects its unique positive-frequency partition. Applying the same coordinate change to the endpoints and code preserves membership. Both sides therefore select the same next symbol, until EOF.

Finish, padding, and the model contract

After encoding EOF and normalizing, the encoder increments pending once, then emits 0 if low<Q, otherwise 1, using the same complement-flushing rule. The last partial byte is padded with zero bits. This gives the decoder a point inside the final interval under the format's implicit zero extension.

An empty input still encodes EOF. With BuildFrequencies(nil), only EOF has positive frequency; this protocol emits 01, stored as 0x40. A decoder returning empty output without reading EOF could pass that one example while failing framing generally.

The codec assumes a valid model and a valid encoded stream. It has no error return, checksum, or declared output-length field; it cannot certify that an arbitrary truncated or corrupted stream is safe or authentic. The exercise does not ask you to build a file format. A container around it would need model serialization, bounded lengths, and integrity/error handling.

Reconstruction lab

Before opening an answer, write the interval or bit sequence yourself.

1. With A:2, B:1, EOF:1, what byte encodes AB under this protocol?
2. With a four-bit state, does [3,12] trigger E3? Does [5,10]?
3. A decoder subtracts Q from its endpoints on E3 but leaves code unchanged. Which invariant breaks?
4. Why can a round-trip test miss a format bug?

Model answers

1. A emits 0, B emits 10, EOF emits 11, and finalization emits 01: 0101101, padded to 0x5a.
2. [3,12] does not fit inside [4,11]. [5,10] does, so subtract 4 and scale to [2,13].
3. The code and interval now use different coordinates; low <= code <= high is no longer assured. Even if it happens to remain true for one step, the selected symbol can change.
4. An encoder and decoder can share the same wrong convention and still reverse each other. Check independently derived bytes, boundary partitions, and an externally supplied model as well as round trips.

For input length n, alphabet size A=257, and b emitted bits, cumulative-table construction costs O(A), encoding O(n+A+b), and the reference's linear symbol lookup makes decoding O(nA+b). Binary search can reduce lookup to O(log A). Storage is O(A) beyond input/output buffers. Small messages can expand because EOF, padding, and any separately stored model have costs; fractional average symbol costs do not mean every message compresses.

Implement Static Arithmetic Coding, then take the checkpoint.

For the original integer-coding treatment and separation of model from coder, see Witten, Neal and Cleary, Arithmetic Coding for Data Compression. The precise 32-bit format and worked vectors here follow this pack's exercise contract.