= Solution
For an IID finite-alphabet source $Q$ and a fixed rate $H(Q)<R<\log_2|\mathcal A|$, let $P_e^*(n,R)$ be the smallest probability that a block is not represented by a fixed-to-fixed code having at most $2^{nR}$ codewords. The <fixed-rate source-coding error exponent> theorem states
$$
\lim_{n\to\infty}-\frac1n\log_2P_e^*(n,R)
=D^*(R,Q),
\qquad
D^*(R,Q)=\min_{P:H(P)\geq R}D(P\|Q).
$$
For the direct part, encode all type classes whose empirical entropy is at most $R-\delta_n$, where $\delta_n\downarrow0$ and $n\delta_n-|\mathcal A|\log_2(n+1)\to\infty$. Since a type class has at most $2^{nH(P)}$ sequences and there are at most $(n+1)^{|\mathcal A|}$ types, this codebook has at most $2^{nR}$ entries for large $n$. An error can occur only when $H(\widehat P_n)>R-\delta_n$. The <method of types> bounds its probability by
$$
(n+1)^{|\mathcal A|}
2^{-n\inf_{P:H(P)>R-\delta_n}D(P\|Q)}.
$$
Taking the lower limit of the exponent and using compactness and continuity gives at least $D^*(R,Q)$, proving achievability.
Back to article page
