Lossless source coding

Lossless source coding encodes source messages so they can be recovered exactly. Shannon's source coding theorem relates its achievable average code length to information entropy.

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