TheoremProved

Shannon's source coding theorem

Statement

Let a discrete memoryless source emit symbols from an alphabet according to a probability distribution with entropy $H$ (in bits, using $\log_2$ ). Then for any $\varepsilon > 0$ , there exists a lossless block code with average length per symbol below $H + \varepsilon$ for block length $n$ large enough; conversely, no lossless code can achieve an average length per symbol below $H$ . In short, the entropy $H$ is exactly the minimal achievable average number of bits per symbol.

Why is it true?

A message is only as long as the surprise it carries: a symbol that occurs with near certainty needs almost no bits to convey, while a rare symbol needs many. Entropy averages this 'surprise' (measured as $-\log_2 p$ ) over the whole source, giving a hard floor: you can compress common patterns away, but you can never compress a random source below the true unpredictability baked into its own statistics.

Proof sketch

For long blocks of $n$ i.i.d. symbols, the asymptotic equipartition property shows that almost all probability mass concentrates on a 'typical set' of roughly $2^{nH}$ sequences, each with probability close to $2^{-nH}$ . Assigning short codewords (about $nH$ bits) only to this typical set, and longer codewords to the negligible remainder, achieves average length close to $H$ per symbol; the converse follows because any code assigning fewer than $nH$ bits on average would have too few codewords to cover the typical set without collisions, by a counting argument.

Stated by

Claude Shannon

Topics that use this theorem

Information theory

Step-by-step proofs

No step-by-step proof yet for this theorem.

References

Claude E. Shannon (1948). A Mathematical Theory of Communication
Thomas M. Cover, Joy A. Thomas (2006). Elements of Information Theory