The source coding theorem gives entropy its first operational identity: entropy is the sharp asymptotic rate for lossless representation.
Fixed-length compression
Definition. An \((n,M_n,\varepsilon_n)\) lossless source code maps \(X^n\) to one of \(M_n\) messages and decodes with error probability at most \(\varepsilon_n\). Its rate is \(R_n=n^{-1}\log M_n\).
Source coding theorem
Theorem. For an iid finite-alphabet source with entropy \(H(X)\), every rate \(R>H(X)\) is achievable with \(\varepsilon_n\to0\), and every rate \(R<H(X)\) has error probability bounded away from zero.
Achievability by typical sets
Proof. Encode typical strings injectively and send a special error symbol for atypical strings. The AEP gives a typical set of size at most \(\exp(n(H+\eta))\) and probability tending to one. Thus any \(R>H\) eventually leaves enough codewords.
Converse by counting
Proof. Any code with \(M_n\le\exp(nR)\) can decode correctly on at most \(M_n\) strings. If \(R<H\), the AEP says no set of that exponential size can carry probability tending to one. Hence vanishing error is impossible.
Fixed-length almost-lossless coding
Definition. An \((n,M_n)\) source code consists of encoder \(f_n:\mathcal X^n\to\{1,\ldots,M_n\}\) and decoder \(g_n\). Its error probability is \[ \epsilon_n=P\{g_n(f_n(X^n))\ne X^n\}, \] and its rate is \(n^{-1}\log M_n\).
Achievability
Theorem. For an iid finite-alphabet source, every rate \(R>H(X)\) is achievable with \(\epsilon_n\to0\).
Proof. Choose \(\varepsilon>0\) with \(H+\varepsilon<R\). Assign distinct indices to sequences in the typical set \(\mathcal T_\varepsilon^{(n)}\), whose cardinality is at most \(e^{n(H+\varepsilon)}\le e^{nR}\). Encode all atypical sequences to one arbitrary index. Decoding is correct on the typical set, whose probability tends to one.
Converse
Theorem. If \(R<H(X)\), every sequence of codes with \(\limsup n^{-1}\log M_n\le R\) has error probability bounded away from zero; in fact \(\epsilon_n\to1\) for the iid finite-alphabet source.
Proof. The decoder can reproduce correctly on at most \(M_n\) source strings. Fix \(\varepsilon>0\) with \(R<H-\varepsilon\). AEP gives probability tending to one to strings each having probability at most \(e^{-n(H-\varepsilon)}\). Hence correct-decoding probability on the typical set is at most \[ M_ne^{-n(H-\varepsilon)} \le e^{-n(H-\varepsilon-R+o(1))}\to0. \] Add the vanishing atypical probability.
Entropy proof of the weak converse
Proposition. If \(\epsilon_n\to0\), then \[ \liminf_{n\to\infty}\frac1n\log M_n\ge H(X). \]
Proof. Let \(\widehat X^n\) be the decoded sequence. Data processing gives \[ \log M_n\ge H(f_n(X^n))\ge I(X^n;\widehat X^n) =nH(X)-H(X^n\mid\widehat X^n). \] Fano bounds the final term by \(h_2(\epsilon_n)+\epsilon_n n\log|\mathcal X|\). Divide by \(n\).
Variable-length lossless coding
Theorem. The minimum expected length \(L^*\) of a binary prefix code satisfies \[ H(X)\le L^*<H(X)+1 \] in bits. For iid blocks, \[ \frac1nL_n^*\to H(X). \]
Fixed-length coding permits a small error and compresses nearly all mass into a typical set. Variable-length lossless coding has zero error and assigns shorter words to more probable strings. Both have the same asymptotic entropy rate.
Second-order source coding
Theorem. Let \(V=\operatorname{Var}\{-\log P(X)\}>0\). The minimum fixed-length code size with error at most \(\epsilon\in(0,1)\) obeys \[ \log M_n^*(\epsilon) = nH(X)+\sqrt{nV}\,\Phi^{-1}(1-\epsilon) -\frac12\log n+O(1) \] under standard nonlattice refinements; the first two terms hold more generally.
Proof outline. The optimal code retains the \(M\) most probable strings, equivalently those below an information-density threshold. The central limit theorem approximates the quantile of \(-\log P(X^n)\), giving the \(\sqrt{nV}\) term. Refined local-limit or saddlepoint analysis yields the logarithmic correction.
Sources with memory
For stationary ergodic sources, Shannon-McMillan-Breiman replaces the iid AEP and the threshold remains the entropy rate. For arbitrary sources, the operational threshold is the spectral sup-entropy rate from the information-spectrum page.
Arithmetic coding
Arithmetic coding represents a sequence by a subinterval whose length equals its model probability. It achieves code length approximately \(-\log P(x^n)\) plus a bounded implementation overhead, avoiding the one-bit-per-symbol rounding cost of separate Shannon codes. Under a mismatched model \(Q\), expected length increases by \(D(P^n\|Q^n)\).