台交大信息论 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）是映射

$\begin{equation}f: \mathcal{X}^{n} \rightarrow \mathcal{B}^{*}\end{equation}$

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

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

$\begin{equation}\mathcal{C}=f\left(\mathcal{X}^{n}\right)=\left\{f\left(x^{n}\right) \in \mathcal{B}^{*}: x^{n} \in \mathcal{X}^{n}\right\}\end{equation}$

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

考虑取值于有限集合$\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

$\begin{equation}f: \mathcal{X}^{n} \rightarrow\{0,1, \cdots, D-1\}^{*}\end{equation}$

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

$\begin{equation}\bar{\ell}:=\sum_{x^{n} \in \mathcal{X}^{n} } P_{X^{n} }\left(x^{n}\right) \ell\left(c_{x^{n} }\right)\end{equation}$

平均码率为

$\begin{equation}\bar{R}_{n}:=\frac{\bar{\ell} }{n}=\frac{1}{n} \sum_{x^{n} \in \mathcal{X}^{n} } P_{X^{n} }\left(x^{n}\right) \ell\left(c_{x^{n} }\right)\end{equation}$

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}$。那么如下不等式成立

$\begin{equation}\sum_{m=1}^{M} D^{-\ell_{m} } \leq 1\end{equation}$

证明：

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

$c_{1} c_{2} c_{3} \ldots c_{N}$

长度分别为

$\ell\left(\boldsymbol{c}_{1}\right), \ell\left(\boldsymbol{c}_{2}\right), \ldots, \ell\left(\boldsymbol{c}_{N}\right)$

考虑

$\left(\sum_{c_{1} \in \mathcal{C} } \sum_{c_{2} \in \mathcal{C} } \cdots \sum_{c_{N} \in \mathcal{C} } D^{-\left[\ell\left(c_{1}\right)+\ell\left(c_{2}\right)+\cdots+\ell\left(c_{N}\right)\right]}\right)= \left(\sum_{c \in \mathcal{C} } D^{-\ell(\boldsymbol{c})}\right)^{N}=\left(\sum_{m=1}^{M} D^{-\ell_{m} }\right)^{N}$

另一方面，令

$i=\ell\left(\boldsymbol{c}_{1}\right)+\ell\left(\boldsymbol{c}_{2}\right)+\cdots+\ell\left(\boldsymbol{c}_{N}\right)$

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

$\left(\sum_{m=1}^{M} D^{-\ell_{m} }\right)^{N}=\sum_{i=1}^{L N} A_{i} D^{-i} \le \sum_{i=1}^{L N} D^{i} D^{-i}=L N$

其中

$L:=\max _{c \in \mathcal{C} } \ell(c)$

这可以推出

$\sum_{m=1}^{M} D^{-\ell_{m} } \leq(L N)^{1 / N}$

令$N\to \infty$可得

$\begin{equation}\sum_{m=1}^{M} D^{-\ell_{m} } \leq 1\end{equation}$

唯一可解码变长码的下界

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

证明：

$\begin{aligned} \bar{R}_{n}-H_{D}(X) &=\frac{1}{n} \sum_{x^{n} \in \mathcal{X}^{n} } P_{X^{n} }\left(x^{n}\right) \ell\left(\boldsymbol{c}_{x^{n} }\right)-\frac{1}{n} H_{D}\left(X^{n}\right) \\ &=\frac{1}{n}\left[\sum_{x^{n} \in \mathcal{X}^{n} } P_{X^{n} }\left(x^{n}\right) \ell\left(\boldsymbol{c}_{x^{n} }\right)-\sum_{x^{n} \in \mathcal{X}^{n} }\left(-P_{X^{n} }\left(x^{n}\right) \log _{D} P_{X^{n} }\left(x^{n}\right)\right)\right] \\ &=\frac{1}{n} \sum_{x^{n} \in \mathcal{X}^{n} } P_{X^{n} }\left(x^{n}\right) \log _{D} \frac{P_{X^{n} }\left(x^{n}\right)}{D^{-\ell\left(c_{x^{n} }\right)} } \\ & \geq \frac{1}{n}\left[\sum_{x^{n} \in \mathcal{X}^{n} } P_{X^{n} }\left(x^{n}\right)\right] \log _{D} \frac{\left[\sum_{x^{n} \in \mathcal{X}^{n} } P_{X^{n} }\left(x^{n}\right)\right]}{\left[\sum_{x^{n} \in \mathcal{X}^{n} } D^{-\ell\left(c_{x} n\right)}\right]}\\ &=-\frac{1}{n} \log \left[\sum_{x^{n} \in \mathcal{X}^{n} } D^{-\ell\left(\boldsymbol{c}_{x^{n} }\right)}\right] \\ &\ge 0 \end{aligned}$

总结

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

前缀码

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

前缀码的Kraft不等式

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

证明：

第一部分：

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

第二部分：

令

$\begin{aligned} n_{i}&=\left|\left\{m: \ell_{m}=i\right\}\right|\\ \ell_{\max }&=\max _{1 \leq m \leq M} \ell_{m} \end{aligned}$

那么由Kraft不等式可得

$n_{1} 2^{-1}+n_{2} 2^{-2}+\cdots+n_{\ell_{\max } } 2^{-\ell_{\max } } \leq 1$

这推出

$\begin{array}{l} n_{1} 2^{-1} \leq 1 \\ n_{1} 2^{-1}+n_{2} 2^{-2} \leq 1 \\ \cdots \\ n_{1} 2^{-1}+n_{2} 2^{-2}+\cdots+n_{\ell \max } 2^{-\ell_{\max } } \leq 1 \end{array}$

因此

$\begin{array}{l} n_{1} \leq 2 \\ n_{2} \leq 2^{2}-n_{1} 2^{1} \\ \cdots \\ n_{\ell_{\max } } \leq 2^{\ell_{\max } }-n_{1} 2^{\ell_{\max }-1}-\cdots-n_{\ell_{\max }-1} 2^{1} \end{array}$

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

推论

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

证明：

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

下界的可达性

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

唯一可解码变长码的平均码率的下界为$H_{D}(X)$。
存在前缀码满足如下条件
$\bar{R}_{n}:=\frac{1}{n} \sum_{x^{n} \in \mathcal{X}^{n} } P_{X^{n} }\left(x^{n}\right) \ell\left(c_{x^{n} }\right) \leq H_{D}(X)+\frac{1}{n}$

证明：

只需证明第二点，选择

$\ell\left(\boldsymbol{c}_{x^{n} }\right)=\left\lfloor-\log _{D} P_{X^{n} }\left(x^{n}\right)\right\rfloor+1 \ge -\log _{D} P_{X^{n} }\left(x^{n}\right)$

那么

$D^{-\ell\left(\boldsymbol{c}_{ {x}^{n} }\right)} \leq P_{X^{n} }\left(x^{n}\right)$

求和可得

$\sum_{x^{n} \in \mathcal{X}^{n} } D^{-\ell\left(c_{x^{n} }\right)} \leq 1$

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

另一方面

$\ell\left(\boldsymbol{c}_{x^{n} }\right)=\left\lfloor-\log _{D} P_{X^{n} }\left(x^{n}\right)\right\rfloor+1 \le -\log _{D} P_{X^{n} }\left(x^{n}\right)+1$

这推出

$\begin{aligned} \sum_{x^{n} \in \mathcal{X}^{n} } P_{X^{n} }\left(x^{n}\right) \ell\left(c_{x^{n} }\right) & \leq \sum_{x^{n} \in \mathcal{X}^{n} }\left[-P_{X^{n} }\left(x^{n}\right) \log _{D} P_{X^{n} }\left(x^{n}\right)\right]+\sum_{x^{n} \in \mathcal{X}^{n} } P_{X^{n} }\left(x^{n}\right) \\ &=H_{D}\left(X^{n}\right)+1\\ &=n H_{D}(X)+1 \end{aligned}$

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

无损变长码信源编码定理

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

对于任意$\varepsilon >0$，存在前缀码
$f: \mathcal{X}^{n} \rightarrow\{0,1, \cdots, D-1\}^{*}$
其平均编码率$\bar{R}_{n}$满足
$\bar{R}_{n} \leq H_{D}(X)+\varepsilon$
其中$n$充分大。
对于每个唯一可解码的编码
$f: \mathcal{X}^{n} \rightarrow\{0,1, \cdots, D-1\}^{*}$
其平均编码率$\bar{R}_{n}$满足
$\bar{R}_{n} \geq H_{D}(X)$

推广

信源的推广

上述定理对平稳信源依然成立，只要将$H_D(X)$替换为

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

损失函数的推广

$\begin{equation}f: \mathcal{X}^{n} \rightarrow\{0,1, \cdots, D-1\}^{*}\end{equation}$

令$\ell\left(\boldsymbol{c}_{x^{n} }\right)$是码字$\begin{equation}\boldsymbol{c}_{x^{n} }=f\left(x^{n}\right)\end{equation}$的长度，定义损失函数

$L_{n}(t):=\frac{1}{t} \log _{D}\left(\sum_{x^{n} \in \mathcal{X}^{n}} P_{X^{n}}\left(x^{n}\right) D^{t \cdot \ell\left(c_{x^{n}}\right)}\right)$

如果$t\to 0$，那么
$L_{n}(t) \rightarrow \sum_{x \in \mathcal{X}} P_{X}(x) \ell\left(c_{x}\right)=\bar{\ell}$
如果$t\to \infty$，那么
$L_{n}(t) \rightarrow \max _{x \in \mathcal{X}} \ell\left(\boldsymbol{c}_{x}\right)$

指数损失下的无损变长码信源编码定理

考虑无记忆的离散源$\left\{X_{n}\right\}_{n=1}^{\infty}$，分布为$P_{X}$，瑞利熵为

$H_{\alpha}(X)=\frac{1}{1-\alpha} \log _{D}\left(\sum_{x \in \mathcal{X}} P_{X}^{\alpha}(x)\right)$

固定$t>0$，令$\alpha=\frac 1 {1+t}$，那么如下事实成立

对于任意$\varepsilon >0$，存在前缀码
$f: \mathcal{X}^{n} \rightarrow\{0,1, \cdots, D-1\}^{*}$
其平均编码率满足
$\frac{1}{n} L_{n}(t) \leq H_{\alpha}(X)+\varepsilon$
其中$n$充分大。
对于每个唯一可解码的编码
$f: \mathcal{X}^{n} \rightarrow\{0,1, \cdots, D-1\}^{*}$
其平均编码率$\bar{R}_{n}$满足
$\frac{1}{n} L_{n}(t) \geq H_{\alpha}(X)$