Arithmetic coding

Goal: keep encoder and decoder in the same interval.

Predict before coding: why does a message need EOF when the compressed bytes already end?

1 / 10

One model, three partitions

A:2, B:1, EOF:1; total 4.

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

AB + EOF: [0,1) → [0,1/2) → [1/4,3/8) → [11/32,12/32).

EOF distinguishes a complete message from a prefix.

2 / 10

Inclusive integer endpoints

Toy state [0,15]: A → [0,7], B → [8,11], EOF → [12,15].

R = high - low + 1; base = low
low  = base + R*C[s]/T
high = base + R*C[s+1]/T - 1

Use floor division. Both updates read the old base.

Predict the bug if the final -1 is removed.

3 / 10

Three ways to expand safely

For four-bit traces: half=8, quarter=4.

Condition Before doubling
high < 8 Emit 0
low >= 8 Emit 1; subtract 8
low >= 4 and high < 12 Defer one bit; subtract 4

Then low *= 2; high = 2*high+1.

Repeat while possible. Merely crossing 8 does not imply E3.

4 / 10

Predict: E3 or no change?

  • [3,12]
  • [5,10]

First: no change. Second: E3 → [2,13].

The full interval must fit in the middle half.

5 / 10

Deferred bits become complements

Model A:1, B:2, EOF:1, message BB:

Symbol Action Output
B E3; pending=1 —
B E3; pending=2 —
EOF E2 twice 1001
Finish Resolve final interval 01

100101 → padded byte 0x94.

6 / 10

Decoder's invariant

low <= code <= high

v = ((code-low+1)*T - 1) / (high-low+1)
choose s with C[s] <= v < C[s+1]

On E2/E3, subtract from code and endpoints.

After doubling, shift in one new bit.

7 / 10

Stop at EOF, not at byte padding

  • Encode EOF, then finalize the interval.
  • Finalization: pending++; emit 0 if low<Q, else 1.
  • Emission flushes pending complementary bits.
  • Pad the last byte with zeros; decoder reads virtual zeros afterward.
  • Empty input still has an EOF stream: 0x40 with its own frequency table.
8 / 10

What tests distinguish implementations?

Round trips can hide a shared encoder/decoder error.

Also check:

  • Known bytes: AB under 2:1:1 → 0x5a.
  • Consecutive E3 events: BB under 1:2:1 → 0x94.
  • Byte values 0 and 255; sparse and supplied models.
  • Input/model unchanged after calls.
9 / 10

Reconstruct the codec

  1. Draw cumulative partitions.
  2. Derive inclusive endpoint updates.
  3. Implement E1/E2/E3 and pending complements.
  4. Invert subdivision to select a decoded symbol.
  5. Finish at EOF and verify independent vectors.

32-bit state needs 64-bit products. Valid stream/model assumed; framing and corruption detection belong to a container.

Exercise · Checkpoint

10 / 10
←/→ or click edges to navigate · ? help · N notes · F fullscreen