Skip to content
Tutorials Center
My learning

Topics

Lesson 17 of 37 ยท Huffman and Arithmetic Coding

Arithmetic Coding with Integers and Adaptive Models

Build a real 32-bit integer arithmetic coder with renormalization and carry handling, pair it with an adaptive frequency model, and see how learning probabilities on the fly compares with static ones.

The Fraction coder of the last lesson is exact but its numbers grow with every symbol. Practical coders keep the interval in fixed-width integers and ship bits to the output as soon as they are decided. They pair the coder with a model that supplies probabilities, which can adapt as the data are read. This lesson builds both, following the classic Witten-Neal-Cleary design.

Integer intervals and renormalization

Represent the interval by integers low and high inside a 32-bit range [0, 2^32 - 1]. To code a symbol with cumulative counts cum_lo..cum_hi out of total, shrink [low, high] proportionally. Then keep the interval large by renormalizing:

  • If high < HALF: the leading bit is surely 0. Output it and double the interval.
  • If low >= HALF: the leading bit is surely 1. Output it (and subtract HALF) then double.
  • If the interval straddles the midpoint but sits inside the middle half (QUARTER <= low and high < 3*QUARTER): the leading bit is not yet known. Remember one pending bit and expand around the middle. When the next certain bit arrives, output it followed by the pending bits of the opposite value.

At the end, output enough bits to pin down a value inside the final interval.

flowchart TD
    A["code symbol: shrink [low, high]"] --> B{"high < HALF?"}
    B -- "yes" --> C["emit 0 and pending 1s, double"]
    B -- "no" --> D{"low >= HALF?"}
    D -- "yes" --> E["emit 1 and pending 0s, double"]
    D -- "no" --> F{"in the middle half?"}
    F -- "yes" --> G["pending += 1, double around the middle"]
    F -- "no" --> H["done with this symbol"]
    C --> B
    E --> B
    G --> B

The renormalization loop that runs after every symbol.

A complete coder with an adaptive model

The model starts knowing nothing: every symbol, including a special end-of-data (EOF) symbol, gets a count of 1. After each symbol is coded, its count is increased by 1. The encoder and decoder update identically, so no table is sent: the decoder learns the statistics in the same way.

Python 32-bit adaptive arithmetic coder

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The round trip correct line prints True. This is a genuine arithmetic coder: it works on a message of any length with constant memory and without sending a table. The repetitive text compresses to about 2.75 bits per symbol against 8 for raw bytes, even though the model starts out knowing nothing and has to learn which letters dominate.

How good is an adaptive model?

An adaptive model pays a learning cost: the first symbols are coded with poor probabilities. With the "start every count at 1" rule (Laplace smoothing), the cost is roughly (k/2) log2 n bits over the whole message for an alphabet of size k, which is tiny relative to the message when n is large. A static model is cheaper only if you already know the true probabilities, and then you must send them.

Python Adaptive ideal cost versus the static optimum

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The adaptive overhead is a modest constant amount and grows only logarithmically, so per symbol it falls toward 0, even though the model needed no table.

Changing statistics: why adaptivity matters

If the source changes its behavior halfway through, a single static distribution is a poor fit for both halves. An adaptive model that forgets old counts (by halving all counts when the total passes a limit) tracks the change.

Python Static versus adaptive when statistics change

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The static model costs about 1 bit per symbol, since overall a and b are balanced, while the forgetting adaptive model costs only a fraction of that: it tracks each half. Choosing the limit trades off reaction speed against estimation noise.

Production formats go further: they condition the probabilities on context (the previous symbols or bits) and mix several models, as in CABAC (H.264/H.265 video), JPEG 2000, bzip3 and the PAQ family. The coder underneath is still this one.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why does an integer arithmetic coder renormalize after each symbol?

    Without renormalization the interval would shrink below the integer precision and symbols could no longer be distinguished.
  2. 2. What are 'pending' bits used for?

    The coder counts how many straddle expansions happened and emits the opposite bits once the next sure bit is known.
  3. 3. How does the decoder know the adaptive model's probabilities?

    Both sides start identical and update identically, so they always agree.
  4. 4. When statistics change halfway through a file, which model usually wins?

    Halving counts lets the model track the new regime.

Summary

  • Practical arithmetic coders keep [low, high] in fixed-width integers and renormalize, emitting settled bits and counting pending ones.
  • An end-of-data symbol tells the decoder when to stop.
  • An adaptive model starts with count 1 per symbol, updates after each symbol and needs no table; its learning overhead grows only logarithmically.
  • Forgetting old counts lets the model follow changing statistics; richer context models plug into the same coder.

Next: Comparing Source Coders