Concept

Arithmetic coding — where it appears

A coder representing a whole message as one number in a narrowing interval, so a symbol may cost a fraction of a bit rather than a whole one. It reaches the entropy where a whole-bit code cannot, and the gain is largest exactly where one symbol dominates and a Huffman code must still spend a bit on it.

Named by 2 essays across 2 fields — each of them below, with the objects they name alongside it.

The bits a coder emits

A stream of 16,384 symbols with a zeroth-order entropy of 3.891 bits per symbol was coded by a Huffman coder into 3.937 and by an arithmetic coder into 3.898, and neither went under 3.891 because neither can. That floor is a third kind of limit, the first that is a property of a model rather than of a question, and the same stream has a different one under every model of it.

floors · Bits

The optimal code that is beaten

Huffman's code is optimal, the proof is correct, and on a stream where one symbol arrives 99 times in a hundred it spends 1.030 bits per symbol against an arithmetic coder's 0.119. Both facts hold. The word "optimal" in the theorem has a precondition attached that almost nobody quotes with it, and everything interesting about coding lives on the other side of that precondition.

wrong · Bits

Named alongside it

The objects these essays reach for when they reach for this one.

Bits per symbol Entropy Huffman coding Prefix code Blocking Cost model Information-theoretic bound Kraft inequality Optimality Precondition Shannon bound Skewed distribution

All concepts