台交大信息论 Lecture 7

课程主页: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

这次回顾第七讲,这一讲主要介绍了用于无损压缩的变长码,对应视频13。

无损压缩的变长码

这部分讨论无损压缩的变长码。

非奇异编码和唯一可解码编码

  • 非奇异
    • 用变长码字对所有源字进行编码。
  • 唯一可解码编码
    • 码字的拼接(无标点机制)是可唯一解码的。
变长码的定义

考虑取值于有限集合$\mathcal X$的离散源$\begin{equation}\left\{X_{n}\right\}_{n=1}^{\infty}\end{equation}$以及取值于$\begin{equation}\mathcal{B}=\{0,1, \cdots, D-1\}\end{equation}$的$D$-ary块,其中$D>1$是整数。给定整数$n\ge 1$,那么$D$-ary的$n$阶变长码(VLC)是映射

该映射将长度为$n$的源码映射到$\mathcal{B}^{*}$中的$D$-ary码字,其中$c\in \mathcal B^{\star}$等价于存在$l\ge 1$,使得$c\in \mathcal B^l$。

VLC的码块$\mathcal C$是所有码字集合:

平均码长以及平均码率的定义

考虑取值于有限集合$\mathcal X$的离散源$\begin{equation}\left\{X_{n}\right\}_{n=1}^{\infty}\end{equation}$,对应分布为$P_{X^{n} }\left(x^{n}\right), x^{n} \in\mathcal X^n$,$\mathcal C$是其$D$-ary的$n$阶VLC

令$\ell\left(\boldsymbol{c}_{x^{n} }\right)$是码字$\begin{equation}\boldsymbol{c}_{x^{n} }=f\left(x^{n}\right)\end{equation}$的长度,那么$\mathcal C$的平均码长为

平均码率为

Kraft-McMillan不等式

考虑取值于有限集合$\mathcal X$的离散源$\begin{equation}\left\{X_{n}\right\}_{n=1}^{\infty}\end{equation}$,$\mathcal C$是其$D$-ary的$n$阶VLC。令$M$是$\mathcal C$中码字数量,对应的码字长度为$\begin{equation}\ell_{1}, \ell_{2}, \ldots, \ell_{M}\end{equation}$。那么如下不等式成立

证明:

假设我们使用$\mathcal C$去编码$N$个源码$\left(x_{i}^{n} \in \mathcal{X}^{n},i=1, \cdots, N\right)$;得到序列

长度分别为

考虑

另一方面,令

$A_i$为长度为$i$的$c_{1} c_{2} c_{3} \ldots c_{N}$数量,那么

其中

这可以推出

令$N\to \infty$可得

唯一可解码变长码的下界

离散无记忆源$\left\{X_{n}\right\}_{n=1}^{\infty}$的唯一可解码变长码的平均码率的下界为$H_{D}(X)$。

证明:

总结

  1. 唯一可解码$\Rightarrow$Kraft-Mcmillan不等式成立
  2. 唯一可解码$\Rightarrow$VLC的平均码率下界为熵

前缀码

前缀码是一种特殊的唯一可解码编码,其特点是任何一个编码都不是另一个编码的前缀,其可用树表示:

前缀码的Kraft不等式

前缀码满足Kraft不等式;反之,如果码长$\ell_{m}, m=1, \ldots, M$满足Kraft不等式,那么存在对应的前缀码。

证明:

第一部分:

利用前缀码可以唯一解码即可。

第二部分:

那么由Kraft不等式可得

这推出

因此

这说明$n_i$不大于第$i$层的最大可选前缀码数量,从而可以生成对应的前缀码。

推论

可以将唯一可解码的编码映射成长度一致的前缀码。

证明:

唯一可解码性$\Rightarrow$Kraft不等式成立$\Rightarrow$存在对应的前缀码

下界的可达性

考虑无记忆的离散源$\left\{X_{n}\right\}_{n=1}^{\infty}$

  1. 唯一可解码变长码的平均码率的下界为$H_{D}(X)$。

  2. 存在前缀码满足如下条件

证明:

只需证明第二点,选择

那么

求和可得

满足Kraft不等式,从而可以找到对应的前缀码。

另一方面

这推出

将上述那内容总结即可得到如下定理。

无损变长码信源编码定理

考虑无记忆的离散源$\left\{X_{n}\right\}_{n=1}^{\infty}$,分布为$P_{X}$,熵为$H_{D}(X)$,那么

  1. 对于任意$\varepsilon >0$,存在前缀码

    其平均编码率$\bar{R}_{n}$满足

    其中$n$充分大。

  2. 对于每个唯一可解码的编码

    其平均编码率$\bar{R}_{n}$满足

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

文章作者:Doraemonzzz

发布时间:2020年08月01日 - 14:33:00

最后更新:2020年08月02日 - 12:07:46

原始链接:http://doraemonzzz.com/2020/08/01/台交大信息论 Lecture 7/

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