台交大信息论 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}$,即

$(n,M)$分块码

定义:

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

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

说明:

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

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

更一般的编码函数为

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

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

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

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

证明:

那么

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

定理:AEP的推论

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

  1. 如果$x^{n} \in \mathcal{F}_{n}(\delta)$,

  2. 对于充分大的$n$,$P_{X^{n}}\left(\mathcal{F}_{n}^{c}(\delta)\right)<\delta$

  3. 对于充分大的$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)}$

证明:

典型集的定义如下:

性质1的证明:

性质2的证明:

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

其中

性质3的证明:

利用性质1可得

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

定理:香农信源编码定理

给定整数$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}$,该序列有如下性质

    并且对于充分大的$n$,

    其中$P_{e}\left(\mathcal{C}_{n}\right)$表示分块码$\mathcal{E}_{n}$的解码错误率。

    备注:由$\varepsilon$的任意性,这等价于

  • Strong converse part:对于任意$0<\varepsilon < 1$以及任意D-ary分块码$\left\{\mathcal{C}_{n}=\left(n, M_{n}\right)\right\}_{n=1}^{\infty}$序列,该序列有如下性质

    对于充分大的的$n$,

    备注:由$\varepsilon$的任意性,这等价于

证明:

Forward part:

  • 不失一般性,只证明$D=2$的情形。

  • 给定$0<\varepsilon<1$,固定$0<\delta<\varepsilon$,选择$n>2 / \delta$。

  • 给定典型集$\mathcal{F}_{n}(\delta / 2)$,定义如下映射

    那么根据AEP定理的推论,对于$n>2\delta$,我们有

    从而

    根据AEP定理的推论第二部分,对于充分大的$n$,下式成立

    取$n$充分大并且$n>2/\delta$,那么

Strong Converse Part:

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

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

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

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

这推出

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

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

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

推广

熵率

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

这里假设极限存在。

引理

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

证明:

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

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

证明:

所以

AEP定理的推广

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

香农信源编码定理的推广

给定整数$D>1$,如果$\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}$,该序列有如下性质

    并且对于充分大的$n$,

    其中$P_{e}\left(\mathcal{C}_{n}\right)$表示分块码$\mathcal{E}_{n}$的解码错误率。

    备注:由$\varepsilon$的任意性,这等价于

  • Strong converse part:对于任意$0<\varepsilon < 1$以及任意D-ary分块码$\left\{\mathcal{C}_{n}=\left(n, M_{n}\right)\right\}_{n=1}^{\infty}$序列,该序列有如下性质

    对于充分大的的$n$,

    备注:由$\varepsilon$的任意性,这等价于

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

冗余

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

  1. 信源分布不均匀导致的源冗余:

  2. 源存储器带来的源冗余

  3. 全部冗余为两者相加

本文标题:台交大信息论 Lecture 6

文章作者:Doraemonzzz

发布时间:2020年07月20日 - 18:06:00

最后更新:2020年08月02日 - 11:54:06

原始链接:http://doraemonzzz.com/2020/07/20/台交大信息论 Lecture 6/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。