Skip to content
Tutorials Center
My learning

Topics

Lesson 12 of 37 ยท Source Coding

The Source Coding Theorem

Why no lossless code beats entropy and how close you can get: the bound H <= L < H+1, block coding that squeezes the overhead, and the entropy rate of sources with memory.

Here is the first of Shannon's great theorems. It says that entropy is not just a number we defined: it is exactly the limit of lossless compression. No prefix code can use fewer than H(X) bits per symbol on average, and some code gets within one bit of it. By coding blocks of symbols the leftover gap can be made as small as you like.

This lesson proves the bounds with the tools you already have (Kraft and Gibbs) and checks them with code.

The theorem for single symbols

Let L = sum p(x) l(x) be the expected length of a binary prefix code for a source with entropy H. Then

TEXT
H(X)  <=  L  <  H(X) + 1

Lower bound. Write L - H = sum p l + sum p log2 p. Define q(x) = 2^(-l(x)) / S where S = sum 2^(-l). Then L - H = D(p || q) - log2 S. By Gibbs, D >= 0, and by Kraft, S <= 1 so -log2 S >= 0. Hence L >= H.

Upper bound. Take lengths l(x) = ceil(-log2 p(x)). They satisfy Kraft (The Kraft Inequality), and since ceil(a) < a + 1, the expected length is below H + 1.

Equality L = H happens exactly when every probability is a power of 1/2 (a dyadic source) and each length is -log2 p.

Python Check H <= L < H+1

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.

Where the extra bit comes from

The gap between L and H is rounding. A symbol with p = 0.9 ideally costs 0.152 bits but a whole-bit code spends at least 1. For a highly skewed source the overhead is large relative to the entropy.

Python Overhead on a skewed source

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 best symbol code spends more than three times the entropy. Block coding fixes this.

Block coding closes the gap

Instead of coding one symbol, code blocks of n symbols at once. The block is itself a symbol of a bigger source, X^n, with entropy n H(X) (for an i.i.d. source). The one-symbol theorem applied to blocks gives

TEXT
n H(X)  <=  L_n  <  n H(X) + 1

Dividing by n gives a per-symbol length L_n / n between H and H + 1/n. Choose n large enough and the overhead vanishes. This is the source coding theorem proper: the best achievable rate is H, and it can be approached arbitrarily closely.

Python Per-symbol cost of coding blocks

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 per-symbol cost tracks the bound H + 1/n and heads toward H = 0.286. The price is complexity: the code table has 2^n entries here, which is why practical coders (arithmetic coding, see Arithmetic Coding) avoid tables and work on the whole message.

Typical sequences: why this works

Why can long blocks be compressed to n H bits? A long i.i.d. sequence is almost surely typical: its empirical frequencies match the true probabilities, so its probability is about 2^(-nH). There are only about 2^(nH) such sequences, so indexing them takes nH bits. Everything else is so improbable that a few bits more for those cases does not change the average.

Python Typical sequences concentrate

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 per-symbol surprisal of a random sequence clusters tightly around H; the spread is only a few hundredths even for n = 1000. This is the asymptotic equipartition property: almost all the probability sits on sequences of nearly equal probability 2^(-nH).

Sources with memory: entropy rate

Real data is not i.i.d. Letters in English depend on neighbors. The right measure is the entropy rate, the entropy per symbol in the long run:

TEXT
H_rate = lim H(X_n | X_1, ..., X_(n-1))

For a Markov source, where the next symbol depends only on the current one, it equals sum over states of pi(s) * H(next | s), with pi the stationary distribution. The source coding theorem holds with H_rate in place of H.

Python Entropy rate of a two-state Markov source

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.

Treating the symbols as independent would cost 0.72 bits each, but exploiting the memory brings the cost down to about 0.57. That gap is exactly what context-modelling compressors such as PPM and LZMA exploit.

The converse also says something striking: no lossless compressor, however clever, can beat the entropy rate on average. Claims of "compress any file by 50%" are impossible. A counting argument shows the same: there are fewer short bit strings than long ones.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. For the best prefix code, the expected length L satisfies

    Entropy is a lower bound, and Shannon lengths ceil(-log2 p) stay within one bit above it.
  2. 2. When is L exactly equal to H for a prefix code?

    Then -log2 p is an integer for every symbol and the lengths can equal it exactly.
  3. 3. How does block coding reduce the overhead above the entropy?

    The rounding loss is at most one bit per block, so it shrinks to 1/n bits per symbol.
  4. 4. For a source with memory, the relevant limit of compression is

    The entropy rate accounts for dependence between symbols and is the true compression limit.

Summary

  • Any prefix code has L >= H; Shannon lengths give L < H + 1.
  • The proof uses Gibbs' inequality and the Kraft inequality.
  • Coding blocks of n symbols gives H <= L_n/n < H + 1/n, so the rate H is achievable in the limit.
  • Long sequences are typical: probability about 2^(-nH), and there are only about 2^(nH) of them.
  • For sources with memory, replace H by the entropy rate; exploiting context lowers the cost.

Next: Shannon and Shannon-Fano Codes