> For the complete documentation index, see [llms.txt](https://isubasinghe.gitbook.io/isithas-wiki/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://isubasinghe.gitbook.io/isithas-wiki/computer_science/compression/source_coding_theorem.md).

# Shannon's source coding theorem

## Basic idea

The noiseless source-coding theorem characterizes the best achievable lossless compression rate for a stationary source. Entropy is both a lower bound on average code length and an asymptotically achievable rate.

## Key formulas

* For a binary prefix code, the expected length satisfies $H(X)\le L < H(X)+1$.
* For blocks of $n$ symbols, $H(X^n)\le L\_n < H(X^n)+1$, so the per-symbol overhead is below $1/n$.
* For an i.i.d. source, $H(X^n)=nH(X)$ and typical sequences number about $2^{nH(X)}$.
* Rates above $H(X)$ are achievable with arbitrarily small failure probability; rates below it cannot be reliable asymptotically.
* Kraft–McMillan, $\sum\_i2^{-l\_i}\le1$, characterizes possible binary prefix-code lengths.

## Resources

<https://en.wikipedia.org/wiki/Shannon%27s_source_coding_theorem>