Fixed-length lossless source coding at the entropy rate

Let ${\epsilon }_n=n^{-1\mathrm{/}4}$ and $T_n=T_n({\epsilon }_n)$. Put $M_n=\mathrm{\mid }{T}_n\mathrm{\mid }+1$ and $k_n=\lceil {\log }_2{M}_n\rceil$. Fix $a_0\in A$, possible since $A$ is nonempty, and assign distinct binary strings of length $k_n$ to the words in $T_n$ plus one unused string. Encode each typical word by its assigned string and every other word by the unused string; decode assigned strings to their typical words and all other strings to $a_0^n$. This defines maps on all of $A^n$, and every typical word is decoded correctly.

For any length-$n$ code, let $C_n=\{x^n\in A^n:g_n(f_n(x^n))=x^n\}$ be its correctly decoded set. Each binary message has only one decoder output, so $\mathrm{\mid }{C}_n\mathrm{\mid }\le 2^{k_n}$. For any $\gamma >0$, every $x^n\in C_n\cap T_n(\gamma )$ has $p^n(x^n)\le e^{-n(H(p)-\gamma )}$. Therefore $1-e_n=\mathbb{P}(X^n\in C_n)\le {\delta }_n(\gamma )+\mathrm{\mid }{C}_n\mathrm{\mid }{e}^{-n(H(p)-\gamma )}\le {\delta }_n(\gamma )+e^{n(R_n-H(p)+\gamma )}\mathrm{.}$ Here [F1] supplies the number of messages, [F2] the source law, [F3] the product law, [F4]–[F6] the log, entropy and typical-set conventions, and [F7] the error-tail notation.

The error is at most ${\delta }_n({\epsilon }_n)\le V(p)\mathrm{/}(n{\epsilon }_n^2)=V(p)\mathrm{/}\sqrt{n}$ by [F7]. For each $a$ with $p(a)>0$, $p(a)\le 1$, and [F4] gives $\ln p(a)\le \ln 1=0$; hence each summand $-p(a)\ln p(a)$ in [F5] is nonnegative and $H(p)\ge 0$. Thus $M_n\le e^{n(H(p)+{\epsilon }_n)}+1\le 2e^{n(H(p)+{\epsilon }_n)}$. Since $k_n=\lceil {\log }_2{M}_n\rceil$, $k_n\ln 2\le \ln M_n+\ln 2$, so $R_n\le H(p)+n^{-1\mathrm{/}4}+2\ln 2\mathrm{/}n$. These bounds prove the achievability claims.

Suppose $\rho :=\mathrm{lim\hspace{0.17em}sup}{R}_n<H(p)$. Since $\ln 2>\ln 1=0$ by [F4] and $k_n\ge 0$ by [F1], all rates are nonnegative. The finite sum in [F5] has finitely many finite terms, so $H(p)$ and then $\rho$ are finite reals. Choose $\gamma =(H(p)-\rho )\mathrm{/}4>0$. Eventually $R_n\le \rho +\gamma =H(p)-3\gamma$. Then step 1.2 gives $1-e_n\le {\delta }_n(\gamma )+e^{-2n\gamma }\to 0$ by [F7], so $e_n\to 1$.

Suppose instead that $e_n\to 0$ but $L:=\mathrm{lim\hspace{0.17em}inf}{R}_n<H(p)$. Since $\ln 2>\ln 1=0$ by [F4] and $k_n\ge 0$ by [F1], all rates are nonnegative. The finite sum in [F5] has finitely many finite terms, so $H(p)$ and $L$ are finite reals. Take $\gamma =(H(p)-L)\mathrm{/}4>0$. Infinitely many $n$ satisfy $R_n\le L+\gamma =H(p)-3\gamma$. Along those indices, step 1.2 and [F7] give $1-e_n\le {\delta }_n(\gamma )+e^{-2n\gamma }\to 0$, contradicting $e_n\to 0$. Hence $\mathrm{lim\hspace{0.17em}inf}{R}_n\ge H(p)$.