Given integer $D\ge2$, consider a DMS $\{X_i\}_{i=1}^\infty$ with alphabet $\mathcal{X}$, pmf $p_X$ and source entropy $$H_D(X)=-\sum\limits_{a\in\mathcal{X}}p_X(a)\log_Dp_X(a)=(log_D2)H(X)$$then the following results hold: 1. Forward Part (Achievability): For any $\epsilon\in(0,1)$ and $0<\delta<\epsilon$, there exists a sequence of $(K,n)$ D-ary fixed-length codes $\mathcal{C}_n$ for the source such that $$H_D(X)<\limsup_{n\to\infty} \frac{k}{n}\le H_D(X)+\delta$$ and $$P_e(\mathcal{C}_n)<\epsilon \mbox{ for n sufficiently large}$$ 2. “Strong” Converse Part: For any $\epsilon\in(0,1)$ and any sequence of $(K,n)$ D-ary fixed-length codes $\mathcal{C}_n$ for the source with $$\limsup_{n\to\infty} \frac{k}{n}<H_D(X)$$ we have that $$P_e(\mathcal{C}_n)>1-\epsilon \mbox{ for n sufficiently large}$$ ## Conclusion $$H_D(X)=\inf\{R:R \mbox{ achievable}\}$$ where R \mbox{ achievable}\iff \forall\epsilon>0, \ \exists\mathcal{C_{n}}\mbox{ s.t. } \begin{array} \ \limsup_{n\to\infty} \frac{k}{n}\le R \mbox{ and} \\ P_e<\epsilon \mbox{ for n sufficiently large}\end{array} [!rmk] For a non-empty set $A$ (with finite infimum), to show that $\vec a=\inf A$, one needs to show that 1. Forward Part: $\forall\delta>0,\exists a_{0} \in A \mbox{ s.t. } a_{0}<\inf A+\delta$ 2. Converse Part: $\forall a\in A, a\ge \inf A$ ## Intuition The theorem shows that for a DMS, its source entropy $H_D(X)$ is the “smallest” compression rate for which there exists D-ary block codes for the source with asymptotically vanishing error probability (i.e. $\lim_{n\to\infty}P_e=0$).

Given integer $D\ge2$, consider a DMS $\{X_i\}_{i=1}^{\infty}$ with alphabet $\mathcal{X}$, pmf $p_X$, and source entropy $$H_D(X)=-\sum\limits_{a\in\mathcal{X}}p_{X}(a)\log_{D}p_{X}(a)=(\log_{D}2)H(X)$$Then the following results hold: 1. Forward Part (Achievability) For any $\epsilon\in(0,1)$, there exists a sequence of $D$-ary $n$-th order prefix (hence UD) VLCs $$f:\mathcal{X}^n\to\{0,1,\cdots,D-1\}^*$$for the source with average code rate satisfying $$\bar R_n<H_{D}(X)+\epsilon$$for $n$ sufficiently large. 2. Converse Part Every $D$-ary $n$-order UD VLC $$f_{n}:\mathcal{X}^{n}\to\{0,1,\cdots,D-1\}^{*}$$for the source has an average code rate $$\bar R_{n\ge}H_{D}(X)$$

Given integer $D\ge2$, consider a stationary source $\{X_i\}_{i=1}^{\infty}$ with alphabet $\mathcal{X}$, pmf $p_X$, and source entropy rate $$H_D(\mathcal{X})=\lim_{n\to\infty} \frac{1}{n}H_{D}(X^{n})$$Then the following results hold: 1. Forward Part (Achievability) For any $\epsilon\in(0,1)$, there exists a sequence of $D$-ary $n$-th order prefix (hence UD) VLCs $$f:\mathcal{X}^n\to\{0,1,\cdots,D-1\}^*$$for the source with average code rate satisfying $$\bar R_n<H_{D}(\mathcal{X})+\epsilon$$for $n$ sufficiently large. 2. Converse Part Every $D$-ary $n$-order UD VLC $$f_{n}:\mathcal{X}^{n}\to\{0,1,\cdots,D-1\}^{*}$$for the source has an average code rate $$\bar R_{n\ge}H_{D}(\mathcal{X})$$