= Fixed-rate source-coding error exponent
Let $Q$ be a nonuniform <probability mass function> with positive mass on an <alphabet> of size $m\geq2$. For <independent and identically distributed> source words, let $\epsilon_n^*(R)$ be the smallest reconstruction-error <probability> using at most $\lfloor2^{nR}\rfloor$ messages. In the nontrivial interval $H_2(Q)<R<\log_2m$,
$$
\lim_{n\to\infty}-n^{-1}\log_2\epsilon_n^*(R)
=\min_{P:H_2(P)\geq R}D_2(P\Vert Q).
$$
Both <Shannon entropy> and <Kullback-Leibler divergence> here use base-two <logarithms>.
The <method of types> gives a direct proof.<Information Theory and Statistics: A Tutorial by Imre Csiszár and Paul C. Shields>[Section 2.1, Lemmas 2.1–2.3, printed pp. 429–431: cardinalities and product-law masses of type classes]{ref} Encode all words of types with <Shannon entropy> at most $R-\delta$; their total <cardinality> fits the budget for large $n$, since there are only polynomially many types. Their complement has the <relative entropy> exponent above as $\delta\downarrow0$. Conversely a <type class> of <Shannon entropy> greater than $R$ has exponentially more words than the code can reconstruct. Its words are equiprobable, so almost all its <probability> is lost. Minimizing that <relative entropy> gives the matching converse.
At $R\geq\log_2m$ every possible word fits, so the error is zero and its exponent is infinite. Substituting that boundary rate into the displayed minimum would incorrectly give a finite answer. If using <natural logarithms> for the error exponent, multiply the base-two value by $\log 2$.
Back to article page
