Shannon noiseless coding theorem

For binary prefix codes, the optimal expected length $L$ obeys $H(X)\le L<H(X)+1$.

Lengths of a binary prefix code satisfy $K={\sum }_x{2}^{-L(x)}\le 1$ and therefore define the probability mass function $R(x)=2^{-L(x)}/K$. Conversely, a mass function gives ideal lengths $-{\log }_{2}R(x)$ and integer prefix lengths after rounding.

For an IID finite-alphabet source $Q$ encoded at rate $R>H(Q)$, the optimal block error probability has exponential rate