台交大信息论 Lecture 8

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

前缀码的例子

霍夫曼编码：最优变长码

引理1

令$\mathcal C$是最优二元前缀码，码长为$\ell_i,i=1,\ldots,M$，其信源为$\mathcal{X}=\left\{a_{1}, \ldots, a_{M}\right\}$，符号概率为$p_{1}, \ldots, p_{M}$。不失一般性，假设

$$p_{1} \geq p_{2} \geq p_{3} \geq \cdots \geq p_{M}$$

并且概率相同的符号按照码长递减顺序排列，即如果

$$p_{i}=p_{i+1}=\cdots=p_{i+s}$$

我们有

$$\ell_{i} \leq \ell_{i+1} \leq \cdots \leq \ell_{i+s}$$

那么如下性质成立。

1. 概率高的信源符号有更短的码长，即$p_{i}>p_{j} \Rightarrow \ell_i\le \ell_j$，$i,j=1,\ldots,M$。
2. 概率最小的两个信源有相同的码长：$\ell_{M-1}=\ell_{M}$。
3. 对于长度为$\ell_{M}$的码字，除了最后一个字符不同，其余均相同。

证明：

1.

如果$p_{i}>p_{j},\ell_i >\ell_j$，那么交换符号$i,j$的编码，得到$\mathcal{C}^{\prime}$，注意到

$$\begin{aligned} \bar{\ell}\left(\mathcal{C}^{\prime}\right)-\bar{\ell}(\mathcal{C}) &=p_{i} \ell_{j}+p_{j} \ell_{i}-\left(p_{i} \ell_{i}+p_{j} \ell_{j}\right) \\ &=\left(p_{i}-p_{j}\right)\left(\ell_{j}-\ell_{i}\right) \\ &<0 \end{aligned}$$

这就与$\mathcal C$的定义相矛盾。

2.

如果$p_{M-1} > p_M$，那么由1可得

$$\ell_{M-1} \leq \ell_{M}$$

如果$p_{M-1}=p_M$，那么根据编码的规则可得

$$\ell_{M-1} \leq \ell_{M}$$

如果$\ell_{M-1}<\ell_{M}$，那么可以删掉码字$M$的最后一个字符得到新的编码$\mathcal C’$，由前缀码的定义可得$\mathcal C’$也是前缀码，但是平均码长小于$\mathcal C$，这就与$\mathcal C$矛盾。

3.

对于长度为$\ell_{M}$的码字，如果不存在只有最后一个字符的不同的两个码字，那么可以删掉所有长度为$\ell_M$的码字的最后一个字符，得到新的前缀码$\mathcal C’$，该前缀码的平均码长小于$C$的平均码长，这就产生了矛盾。

引理(霍夫曼)

考虑符号为$\mathcal{X}=\left\{a_{1}, \ldots, a_{M}\right\}$的信源，符号概率$p_{1}, \ldots, p_{M}$满足

$$p_{1} \geq p_{2} \geq \cdots \geq p_{M}$$

考虑构造简化源符号$\mathcal Y$，方法如下：将两个概率最小的源符号$ a_ {M-1} $和$ a_ {M} $合并为符号$a_{M-1,M}$，其概率为$p_{M-1}+p_{M}$。假设$C’$为由$f^{\prime}: \mathcal{Y} \rightarrow\{0,1\}^{\star}$生成的最优编码（信源为$\mathcal Y$）。现在构造信源$\mathcal X$的编码$\mathcal{C}, f: \mathcal{X} \rightarrow\{0,1\}^{\star}$：

• $a_{1}, a_{2}, \cdots, a_{M-2}$的码字不变：

  $$f\left(a_{1}\right)=f^{\prime}\left(a_{1}\right), f\left(a_{2}\right)=f^{\prime}\left(a_{2}\right), \cdots, f\left(a_{M-2}\right)=f^{\prime}\left(a_{M-2}\right)$$

• $a_{M-1},a_M$的码字如下：

  $$\begin{aligned} f\left(a_{M-1}\right)&=\left[f^{\prime}\left(a_{M-1, M}\right) 0\right]\\ f\left(a_{M}\right)&=\left[f^{\prime}\left(a_{M-1, M}\right) 1\right] \end{aligned}$$

那么编码$\mathcal C$是信源$\mathcal X$的最优编码。

霍夫曼编码算法

1. 重复应用以上引理，直到剩下带有两个符号的简化源。 此源的最佳二进制前缀码由码字$0$和$1$组成。
2. 然后向后进行，为每个简化源构建（如上述引理所述）最佳代码，直到到达原始源为止。

Shannon-Fano-Elias编码

假设$\mathcal{X}=\{1, \ldots, M\}$，并且对所有$x \in \mathcal{X}$，都有$P_{X}(x)>0$。

定义

$$\begin{aligned} F(x)&:=\sum_{a \leq x} P_{X}(a) \\ \bar{F}(x)&:=\sum_{a<x} P_{X}(a)+\frac{1}{2} P_{X}(x) \end{aligned}$$

编码器：对于任意$x \in \mathcal{X}$，将$\bar{F}(x)$用二进制表示，即

$$\bar{F}(x)=. c_{1} c_{2} \ldots c_{k} \ldots$$

然后选择小数部分的前$k$个元素作为编码，即

$$\left(c_{1}, c_{2}, \ldots, c_{k}\right)$$

其中

$$k:=\left\lceil\log _{2}\left(1 / P_{X}(x)\right)\right\rceil+1$$

解码器：给定码字$\left(c_{1}, \ldots, c_{k}\right)$，按照$\{1,2, \ldots, M\}$的顺序计算$F(.)$，直到满足

$$F(x) \geq . c_{1} \ldots c_{k}$$

那么$x$是原始符号。

下面证明解码的正确性。

证明：

对于任意$a \in[0,1]$，令$[a]_k$表示删除$a$第$k$位之后的全部比特所产生的数。那么

$$\bar{F}(x)-[\bar{F}(x)]_{k}<\frac{1}{2^{k} }$$

因为

$$k=\left\lceil\log _{2}\left(1 / P_{X}(x)\right)\right\rceil+1 \geq \log _{2}\left(1 / P_{X}(x)\right)+1$$

那么对$x \in\{1,2, \ldots, M\}$，我们都有

$$\begin{aligned} \frac{1}{2^{k} } & \leq \frac{1}{2} P_{X}(x) \\ &=\left[\sum_{a<x} P_{X}(a)+\frac{P_{X}(x)}{2}\right]-\sum_{a \leq x-1} P_{X}(a) \\ &=\bar{F}(x)-F(x-1) \end{aligned}$$

因此

$$F(x-1)=\left[F(x-1)+\frac{1}{2^{k} }\right]-\frac{1}{2^{k} } \leq \bar{F}(x)-\frac{1}{2^{k} }<[\bar{F}(x)]_{k}$$

此外

$$F(x)>\bar{F}(x) \geq[\bar{F}(x)]_{k}$$

这说明$x$是满足如下条件的第一个元素

$$F(x) \geq[\bar{F}(x)]_{k}=. c_{1} c_{2} \ldots c_{k}$$

平均码长：

$$\begin{aligned} \bar{\ell} &=\sum_{x \in \mathcal{X} } P_{X}(x)\left\lceil\log _{2} \frac{1}{P_{X}(x)}\right\rceil+1 \\ &<\sum_{x \in \mathcal{X} } P_{X}(x) \log _{2} \frac{1}{P_{X}(x)}+2 \\ &=(H(X)+2) \text { bits. } \end{aligned}$$

Fano编码

Fano编码：Fano编码是根据以下算法生成的：

1. 以不增概率的顺序排列符号。
2. 将有序符号列表分为两部分，左部分的总概率尽可能接近右部分的总概率。
3. 将$0$分配给列表的左侧，将$1$分配给列表的右侧。
4. 将步骤2和步骤3递归应用到两个部分中的每个部分，细分为更多部分，并将位添加到码字中，直到每个符号都是该部分的单个成员。

例子：

Shannon编码

和Shannon-Fano-Elias编码类似，不过将概率按照非增的顺序排列，然后取

$$k:=\left\lceil\log _{2}\left(1 / P_{X}(x)\right)\right\rceil$$

注意Kraft不等式在此时同样满足：

$$\sum_{x \in \mathcal{X} } 2^{-\left\lceil\log _{2} \frac{1}{P_{X}(x)}\right\rceil} \leq \sum_{x \in \mathcal{X} } 2^{-\log _{2} \frac{1}{P_{X}(x)} }=\sum_{i=1}^{M} P_{X}(x)=1$$

之前的编码均假设概率已知，后续将介绍概率未知的编码方法。

自适应Huffman编码

令信源符号为$\mathcal{X}:=\left\{a_{1}, \ldots, a_{M}\right\}$，定义

$$N\left(a_{i} | x^{n}\right):=a_i出现在x_{1}, x_{2}, \ldots, x_{n}的次数$$

$a_i$当且频率为

$$\frac{N\left(a_{i} | x^{n}\right)}{n}$$

令$c_{n}\left(a_{i}\right)$为关于如下分布的Huffman码字

$$\left[\frac{N\left(a_{1} | x^{n}\right)}{n}, \frac{N\left(a_{2} | x^{n}\right)}{n}, \cdots, \frac{N\left(a_{J} | x^{n}\right)}{n}\right]$$

概率的更新方法如下，假设$x_{n+1}=a_{j}$，那么

$$\begin{aligned} \frac{N\left(a_{j} \mid x^{n+1}\right)}{n+1}&=\frac{n \times\left[N\left(a_{j} \mid x^{n}\right) / n\right]+1}{n+1} \\ \frac{N\left(a_{i} \mid x^{n+1}\right)}{n+1}&=\frac{n \times\left[N\left(a_{i} \mid x^{n}\right) / n\right]}{n+1} \text { for } i \neq j \end{aligned}$$

定义3.37（同级属性）

如果前缀码的编码树满足以下条件，则称该前缀代码具有同级属性：

1. 编码树中的每个节点（根节点除外）都有一个同级(sibling)（即编码树已饱和），并且
2. 可以按概率的降序列出节点，每个节点与其同级相邻。

观测：前缀码是Huffman码当且仅当其满足同级属性。

来看一个具体例子：

Lempel-Ziv编码

编码器：

1. 将输入序列解析为以前从未出现过的字符串。
2. 令$ L $为已解析源的不同字符串数。然后，我们需要$ \log _ {2} L $比特来索引这些字符串（从$1$开始）。每个字符串的码字由其前缀的索引与源字符串中的最后一位连接在一起。（注意用全$0$表示空字符串）

例子：

假设输入序列为$1011010100010$。

步骤1：

将其解析为

$$1,0,11,01,010,00,10$$

步骤2：

我们需要$\left\lfloor\log _{2}(L)\right\rfloor+1=3$比特来索引这些字符，结果如下：

$$\begin{array}{ccccccc} \text{parsed source }:&1 & 0 & 11 & 01 & 010 & 00 & 10 \\ \text{index }:&001 & 010 & 011 & 100 & 101 & 110 & 111 \end{array}$$

所以码字为：

$$(000,1)(000,0)(001,1)(010,1)(100,0)(010,0)(001,0)$$

定理

Lempel-Ziv算法渐近地达到了任何平稳的遍历源（统计量未知）的熵率。