Shannon Coding Theorem

NAVIGATION

Home

Research

Bookshelf

Garden

FIND ME ON

GitHub

Home

Research

Bookshelf

Garden

ℹ

Shannon Coding Theorem

Theorem (Shannon Fixed-Length Lossless Source Coding Theorem for DMS)

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:

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}$
“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 \text{ achievable}\}$ where $R \text{ achievable}\iff \forall\epsilon>0, \ \exists\mathcal{C_{n}}\text{ s.t. } \begin{array} \ \limsup_{n\to\infty} \frac{k}{n}\le R \text{ and} \\ P_e<\epsilon \text{ for n sufficiently large}\end{array}$

Remark

For a non-empty set $A$ (with finite infimum), to show that $\vec a=\inf A$ , one needs to show that

Forward Part: $\forall\delta>0,\exists a_{0} \in A \mbox{ s.t. } a_{0}<\inf A+\delta$
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$ ).

Theorem (Shannon’s VLC Lossless Source Coding Theorem for DMS)

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:

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.
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)$

Cor ((Achievability of Entropy for DMS))

For any $n\ge1$ , $\exists$ a $D$ -ary $n$ -th order prefix code $f:\mathcal{X}^{n}\to\{0,1,\cdots,D-1\}^*$ for a DMS $\{X_{i}\}$ with alphabet $\mathcal{X}$ with average code rate: $H_{D}(X)\le\bar R_n<H_{D}(X)+ \frac{1}{n}$

Theorem (Shannon’s VLC Lossless Source Coding Theorem for Stationary Sources)

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:

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.
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})$

Cor ((Achievability of Source Entropy for Stationary Source))

For any $n\ge1$ , $\exists$ a $D$ -ary $n$ -th order prefix code $f:\mathcal{X}^{n}\to\{0,1,\cdots,D-1\}^{*}$ for a stationary source $\{X_i\}$ with alphabet $\mathcal{X}$ with avg code rate $\frac{1}{n}H_{D}(X^{n})\le\bar R_{n}< \frac{1}{n}H_{D}(X^{n}) + \frac{1}{n}$ as $n\to\infty$ , $\bar R_{n}\to H(\mathcal{X})$ .

Linked from

Stationary & Ergodic Source