台交大信息论 Lecture 6

课程主页：https://ocw.nctu.edu.tw/course_detail-c.php?bgid=8&gid=0&nid=612&pid=973

http://shannon.cm.nctu.edu.tw/it18.htm

老师主页：http://shannon.cm.nctu.edu.tw/

课程视频：https://www.youtube.com/playlist?list=PLj6E8qlqmkFsWS54o6gNWeDGXeI7c3eUd

这次回顾第六讲，这一讲主要介绍了信源编码定理，对应视频12。

离散无记忆源(DMS)

定义：

离散无记忆源(DMS)包含i.i.d随机变量序列$\left\{X_{n}\right\}_{n=1}^{\infty}$，即

$P_{X^{n}}\left(x_{1}, x_{2}, \ldots, x_{n}\right)=\prod_{i=1}^{n} P_{X}\left(x_{i}\right)$

$(n,M)$分块码

定义：

对于离散源$\left\{X_{n}\right\}_{n=1}^{\infty}$，分块长度为$n$，大小为$M$的$(n,M)$分块码的是指集合

$\mathcal{C}_{n}=\left\{c_{1}, c_{2}, \ldots, c_{M}\right\} \subseteq \mathcal{X}^{n}$

该集合是单词的$M$个重构。

说明：

$(n,M)$分块码可以用编码-解码函数$(f,g)$表示：

编码函数：$f: \mathcal{X}^{n} \rightarrow\{0,1\}^{k}$
解码函数：$g:\{0,1\}^{k} \rightarrow\left\{c_{1}, c_{2}, \ldots, c_{M}\right\}$

更一般的编码函数为

$f: \mathcal{X}^{n} \rightarrow\{0,1, \ldots, D-1\}^{k}$

对应的分块码称为D-ary块。

重构后，可以使用$k:=\left\lceil\log _{2} M\right\rceil$比特重新表示单词，所以数据压缩比（码率）为

$\frac{k}{n}=\frac{1}{n} \log _{2} M$

定理：渐近等分性质(AEP)

如果$\left\{X_{n}\right\}_{n=1}^{\infty}$是DMS，熵为$H(X)$，那么$\forall \delta >0$，

$\lim _{n \rightarrow \infty} \operatorname{Pr}\left\{\left|-\frac{1}{n} \log _{2} P_{X^{n}}\left(X_{1}, \ldots, X_{n}\right)-H(X)\right|>\delta\right\}=0$

证明：

记

$Y_n =-\log_2 P(X_n)$

那么

$\mathbb E[Y_n]= H(X)$

利用大数定律即可得到上述结论。

定理：AEP的推论

给定DMS$\left\{X_{n}\right\}_{n=1}^{\infty}$，熵为$H(X)$，$\forall \delta >0$，弱$\delta$典型集$\mathcal{F}_{n}(\delta)$满足如下性质。

如果$x^{n} \in \mathcal{F}_{n}(\delta)$，
$2^{-n(H(X)+\delta)} \leq P_{X^{n}}\left(x^{n}\right) \leq 2^{-n(H(X)-\delta)}$
对于充分大的$n$，$P_{X^{n}}\left(\mathcal{F}_{n}^{c}(\delta)\right)<\delta$
对于充分大的$n$，$\left|\mathcal{F}_{n}(\delta)\right|>(1-\delta) 2^{n(H(X)-\delta)}$；对于每个$n$，$\left|\mathcal{F}_{n}(\delta)\right| \leq 2^{n(H(X)+\delta)}$

证明：

典型集的定义如下：

$\mathcal{F}_{n}(\delta):=\left\{x^{n} \in \mathcal{X}^{n}:\left|-\frac{1}{n} \sum_{i=1}^{n} \log _{2} P_{X}\left(x_{i}\right)-H(X)\right|<\delta\right\}$

性质1的证明：

$\begin{aligned} \left|-\frac{1}{n} \sum_{i=1}^{n} \log _{2} P_{X}\left(x_{i}\right)-H(X)\right|<\delta &\Leftrightarrow\\ \left|-\frac{1}{n} \log _{2} P_{X^{n}}\left(x^{n}\right)-H(X) \right|<\delta &\Leftrightarrow \\ H(X)-\delta<-\frac{1}{n} \log _{2} P_{X^{n}}\left(x^{n}\right)<H(X)+\delta \end{aligned}$

性质2的证明：

利用切比雪夫不等式，对于$n>\sigma_{X}^{2} / \delta^{3}$

$P_{X^{n}}\left(\mathcal{F}_{n}^{c}(\delta)\right)=P_{X^{n}}\left\{x^{n} \in \mathcal{X}^{n}:\left|-\frac{1}{n} \log _{2} P_{X^{n}}\left(x^{n}\right)-H(X)\right|>\delta\right\} \leq \frac{\sigma_{X}^{2}}{n \delta^{2}}<\delta$

其中

$\sigma_{X}^{2}:=\operatorname{Var}\left[-\log _{2} P_{X}(X)\right]$

性质3的证明：

利用性质1可得

$1 \geq \sum_{x^{n} \in \mathcal{F}_{n}(\delta)} P_{X^{n}}\left(x^{n}\right) \geq \sum_{x^{n} \in \mathcal{F}_{n}(\delta)} 2^{-n(H(X)+\delta)}=\left|\mathcal{F}_{n}(\delta)\right| 2^{-n(H(X)+\delta)}$

利用性质1和性质2可得，对于$n \geq \sigma_{X}^{2} / \delta^{3}$

$1-\delta<1-\frac{\sigma_{X}^{2}}{n \delta^{2}} \leq \sum_{x^{n} \in \mathcal{F}_{n}(\delta)} P_{X^{n}}\left(x^{n}\right) \leq \sum_{x^{n} \in \mathcal{F}_{n}(\delta)} 2^{-n(H(X)-\delta)}=\left|\mathcal{F}_{n}(\delta)\right| 2^{-n(H(X)-\delta)}$

定理：香农信源编码定理

给定整数$D>1$，考虑熵为$H_D(X)$的DMS$\left\{X_{n}\right\}_{n=1}^{\infty}$，那么如下性质成立。

Forward part（可达性）：对于任意$0<\varepsilon < 1$，存在$0<\delta<\varepsilon$以及D-ary分块码序列$\left\{\mathcal{C}_{n}=\left(n, M_{n}\right)\right\}_{n=1}^{\infty}$，该序列有如下性质
$\limsup _{n \rightarrow \infty} \frac{1}{n} \log _{D} M_{n} \leq H_{D}(X)+\delta$
并且对于充分大的$n$，
$P_{e}\left(\mathcal{C}_{n}\right)<\varepsilon$
其中$P_{e}\left(\mathcal{C}_{n}\right)$表示分块码$\mathcal{E}_{n}$的解码错误率。

备注：由$\varepsilon$的任意性，这等价于
$\limsup _{n \rightarrow \infty} P_{e}\left(\mathcal{C}_{n}\right)=0$
Strong converse part：对于任意$0<\varepsilon < 1$以及任意D-ary分块码$\left\{\mathcal{C}_{n}=\left(n, M_{n}\right)\right\}_{n=1}^{\infty}$序列，该序列有如下性质
$\limsup _{n \rightarrow \infty} \frac{1}{n} \log _{D} M_{n}<H_{D}(X)$
对于充分大的的$n$，
$P_{e}\left(\mathcal{E}_{n}\right)>1-\varepsilon$
备注：由$\varepsilon$的任意性，这等价于
$\limsup _{n \rightarrow \infty} P_{e}\left(\mathcal{C}_{n}\right)=1$

证明：

Forward part：

不失一般性，只证明$D=2$的情形。
给定$0<\varepsilon<1$，固定$0<\delta<\varepsilon$，选择$n>2 / \delta$。
给定典型集$\mathcal{F}_{n}(\delta / 2)$，定义如下映射
$\left\{\begin{array}{l} x^{n} \rightarrow \text { binary index of } x^{n}, \text { if } x^{n} \in \mathcal{F}_{n}(\delta / 2) \\ x^{n} \rightarrow \text { all-zero codeword, } \text { if } x^{n} \notin \mathcal{F}_{n}(\delta / 2) \end{array}\right.$
那么根据AEP定理的推论，对于$n>2\delta$，我们有
$\begin{aligned} M_{n} &=\left|\mathcal{F}_{n}(\delta / 2)\right|+1 \\ &\le 2^{n(H(X)+\delta / 2)}+1\\ &<2 \cdot 2^{n(H(X)+\delta / 2)}\\ &<2^{n \delta / 2} \cdot 2^{n(H(X)+\delta / 2)}\\ &=2^{n(H(X)+\delta)} \end{aligned}$
从而
$\limsup _{n \rightarrow \infty} \frac{1}{n} \log _{D} M_{n} \leq H_{D}(X)+\delta$
根据AEP定理的推论第二部分，对于充分大的$n$，下式成立
$P_{X^{n}}\left(\mathcal{F}_{n}^{c}(\delta / 2)\right)<\frac{\delta}{2}$
取$n$充分大并且$n>2/\delta$，那么
$P_{e}\left(\mathcal{C}_{n}\right) \leq P_{X^{n}}\left(\mathcal{F}_{n}^{c}(\delta / 2)\right)<\delta \leq \varepsilon$

Strong Converse Part：

对于任意满足如下条件的分块码序列$\left\{\mathcal{C}_{n}\right\}_{n=1}^{\infty}$

$\limsup _{n \rightarrow \infty} \frac{1}{n} \log _{2}\left|\mathcal{C}_{n}\right|<H(X)$

令$\mathcal S_n$为源符号通过$\mathcal{C}_{n}$编码系统正确解码的信源符号，那么

$\left|\mathcal{S}_{n}\right|=\left|\mathcal{C}_{n}\right|$

这一点可以通过下图得到：

选择充分小的$\delta$，使其满足$\varepsilon / 2>\delta>0$，那么由上确界的定义可得

$\left(\exists N_{0}\right)\left(\forall n>N_{0}\right) \quad \frac{1}{n} \log _{2}\left|\mathcal{S}_{n}\right|=\frac{1}{n} \log _{2}\left|\mathcal{C}_{n}\right|<H(X)-2 \delta$

这推出

$\left|\mathcal{S}_{n}\right|<2^{n(H(X)-2 \delta)}$

利用AEP推论的性质2，我们得到

$\left(\exists N_{1}\right)\left(\forall n>N_{1}\right) \quad P_{X^{n}}\left(\mathcal{F}_{n}^{c}(\delta)\right)<\delta$

取$n>N:=\max \left\{N_{0}, N_{1}, \log _{2}(2 / \varepsilon) / \delta\right\}$，我们有

$\begin{aligned} 1-P_{e}\left(\mathcal{C}_{n}\right) &=\sum_{x^{n} \in \mathcal{S}_{n}} P_{X^{n}}\left(x^{n}\right) \\ &=\sum_{x^{n} \in \mathcal{S}_{n} \cap \mathcal{F}_{n}^{c}(\delta)} P_{X^{n}}\left(x^{n}\right)+\sum_{x^{n} \in \mathcal{S}_{n} \cap \mathcal{F}_{n}(\delta)} P_{X^{n}}\left(x^{n}\right) \\ & \leq P_{X^{n}}\left(\mathcal{F}_{n}^{c}(\delta)\right)+\left|\mathcal{S}_{n} \cap \mathcal{F}_{n}(\delta)\right| \cdot \max _{x^{n} \in \mathcal{F}_{n}(\delta)} P_{X^{n}}\left(x^{n}\right) \\ &<\delta+\left|\mathcal{S}_{n}\right| \cdot \max _{x^{n} \in \mathcal{F}_{n}(\delta)} P_{X^{n}}\left(x^{n}\right) \\ &<\frac{\varepsilon}{2}+2^{n(H(X)-2 \delta)} \cdot 2^{-n(H(X)-\delta)} \\ &=\frac{\varepsilon}{2}+2^{-n \delta} \\ &<\varepsilon \end{aligned}$

这等价于，对于$n>N$，我们有

$P_{e}\left(\mathcal{C}_{n}\right)>1-\varepsilon$

推广

熵率

信源$\left\{X_{n}\right\}_{n=1}^{\infty}$的熵率用符号$H(\mathcal{X})$表示，定义为

$H(\mathcal{X}):=\lim _{n \rightarrow \infty} \frac{1}{n} H\left(X^{n}\right)$

这里假设极限存在。

引理

对于平稳信源$\left\{X_{n}\right\}_{n=1}^{\infty}$，条件熵$H\left(X_{n} \mid X_{n-1}, \ldots, X_{1}\right)$不降且有下界，所以如下极限存在

$\lim _{n \rightarrow \infty} H\left(X_{n} \mid X_{n-1}, \ldots, X_{1}\right)$

证明：

$\begin{aligned} H\left(X_{n} \mid X_{n-1}, \ldots, X_{1}\right) & \leq H\left(X_{n} \mid X_{n-1}, \ldots, X_{2}\right) \\ &=H\left(X_{n}, \cdots, X_{2}\right)-H\left(X_{n-1}, \cdots, X_{2}\right) \\ &=H\left(X_{n-1}, \cdots, X_{1}\right)-H\left(X_{n-2}, \cdots, X_{1}\right) \\ &=H\left(X_{n-1} \mid X_{n-2}, \ldots, X_{1}\right) \end{aligned}$

定理：平稳信源的熵率总存在

平稳信源$\left\{X_{n}\right\}_{n=1}^{\infty}$的熵率总存在，等于

$H(\mathcal{X})=\lim _{n \rightarrow \infty} H\left(X_{n} \mid X_{n-1}, \ldots, X_{1}\right)$

证明：

$\frac{1}{n} H\left(X^{n}\right)=\frac{1}{n} \sum_{i=1}^{n} H\left(X_{i} \mid X_{i-1}, \ldots, X_{1}\right)$

所以

$H(\mathcal{X})=\lim_{n\to \infty} \frac 1 n H(X^n) = \lim_{n\to \infty} H\left(X_{i} \mid X_{i-1}, \ldots, X_{1}\right)$

AEP定理的推广

如果$\left\{X_{n}\right\}_{n=1}^{\infty}$是平稳遍历信源，那么

$-\frac{1}{n} \log _{2} P_{X^{n}}\left(X_{1}, \ldots, X_{n}\right) \stackrel{\text {a.s.}}{\longrightarrow} H(\mathcal{X})$

香农信源编码定理的推广

给定整数$D>1$，如果$\left\{X_{n}\right\}_{n=1}^{\infty}$是平稳遍历信源，熵率为

$H_{D}(\mathcal{X}):=\lim _{n \rightarrow \infty} \frac{1}{n} H_{D}\left(X^{n}\right)$

那么如下性质成立。

Forward part（可达性）：对于任意$0<\varepsilon < 1$，存在$0<\delta<\varepsilon$以及D-ary分块码序列$\left\{\mathcal{C}_{n}=\left(n, M_{n}\right)\right\}_{n=1}^{\infty}$，该序列有如下性质
$\limsup _{n \rightarrow \infty} \frac{1}{n} \log _{D} M_{n} \leq H_{D}(\mathcal{X})+\delta$
并且对于充分大的$n$，
$P_{e}\left(\mathcal{C}_{n}\right)<\varepsilon$
其中$P_{e}\left(\mathcal{C}_{n}\right)$表示分块码$\mathcal{E}_{n}$的解码错误率。

备注：由$\varepsilon$的任意性，这等价于
$\limsup _{n \rightarrow \infty} P_{e}\left(\mathcal{C}_{n}\right)=0$
Strong converse part：对于任意$0<\varepsilon < 1$以及任意D-ary分块码$\left\{\mathcal{C}_{n}=\left(n, M_{n}\right)\right\}_{n=1}^{\infty}$序列，该序列有如下性质
$\limsup _{n \rightarrow \infty} \frac{1}{n} \log _{D} M_{n}<H_{D}(\mathcal{X})$
对于充分大的的$n$，
$P_{e}\left(\mathcal{E}_{n}\right)>1-\varepsilon$
备注：由$\varepsilon$的任意性，这等价于
$\limsup _{n \rightarrow \infty} P_{e}\left(\mathcal{C}_{n}\right)=1$

备注：不可约有限状态马尔可夫链满足遍历性。

冗余

信源可以被压缩，只有当其有冗余。

信源分布不均匀导致的源冗余：
$\rho_{d}:=\log _{2}|\mathcal{X}|-H\left(X_{1}\right)$
源存储器带来的源冗余
$\rho_{m}:=H\left(X_{1}\right)-H(\mathcal{X})$
全部冗余为两者相加
$\rho_{t}:=\rho_{d}+\rho_{m}=\log _{2}|\mathcal{X}|-H(\mathcal{X})$