第一章 绪论 第二章 离散信源及信息测度 第三章 离散信道及其信道容量 第四章 连续信源和波形信道 第五章 无失真信源编码定理 第六章 有噪信道编码 第七章 限失真信源编码 第八章 无失真信源编码 第九章 纠错编码
第八章 无失真信源编码
8.1 Huffman码
Huffman码是效率比较高的变长无失真信源编码方法。
编码方法
-
将信源符号按概率从大到小顺序排列，令：
p(s_1)\geq p(s_2)\geq\cdots\geq p(s_q)
-
给两个概率最小的信源符号s_{n-1}和s_n各分配一个码元”0“和”1“，并将这两个信源符号合并成一个新符号，并用这两个最小的概率之和作为新符号的概率，结果的到一个只包含(n-1)个信源符号的新信源。称为信源的第一次缩减信源，用S_1表示。
-
将缩减信源S_1的符号仍按概率从大到小排列，重复步骤2，得到只含(n-2)个符号的缩减信源S_2。
-
重复上述步骤，直至缩减信源只剩两个符号为止，此时所剩两个符号的概率之和必为1。然后从最后一级缩减信源开始，依编码路径向前返回，就得到各信源符号所对应的码字。
-
动态实例
设单符号离散信源如下，要求对信源编二进制哈夫曼码。
\begin{bmatrix}S\\P(S)\end{bmatrix}=\begin{bmatrix}s_1&s_2&s_3&s_4&s_5&s_6&s_7\\ 0.20&0.19&0.18&0.17&0.15&0.10&0.01\end{bmatrix}
最终的编码结果如下：
信源符号
s_1
s_2
s_3
s_4
s_5
s_6
s_7
码字
10
11
000
001
010
0110
0111
Huffman编码结果不唯一
- 每次对缩减信源两个概率最小的符号分配“0“或“1”码元是任意的，所以可得到不同的码字。不同的码元分配，得到的具体码字不同，但码长l_i不变，平均码长也不变，所以没有本质区别；
- 缩减信源时，若合并后的概率与其他概率相等，这几个概率的次序可任意排列，编出的码都是正确的，但得到的码字不相同。不同的排列方法得到的码长也不相同。
r进制Huffman码
二进制霍夫曼码很容易推广到进制的情况。
-
编码过程中构成缩减信源时，每次都将概率最小的个符号合并，并分别用码符号表示；
-
为充分利用短码，使平均码长最短，必须使最后一次缩减信源有r个信源符号。
-
当信源符号数q=r+\theta\cdot(r-1)，则可以进行完全缩减。
-
当符号个数不满足上述条件时，则最后一次缩减时最好有个信源符号，目的是为了充分利用短码。方法是补充一些概率为0的符号。
-
动态实例
对离散无记忆信源进行三进制编码：
\begin{bmatrix}S\\ P(S)\end{bmatrix}=\begin{bmatrix}s_1&s_2&s_3&s_4&s_5&s_6&s_7&s_8\\ 0.4&0.2&0.1&0.1&0.05&0.05&0.05&0.05\end{bmatrix}
最终的编码结果如下：
信源符号
s_1
s_2
s_3
s_4
s_5
s_6
s_7
s_8
码字
1
00
02
20
21
22
010
011
-
Huffman码是紧致码；
-
提高Huffman码编码效率的方法：N次扩展。
习题
判断对错：
- Huffman码是一种无失真信源编码方法。
- Huffman编码结果唯一，不会因为不同的码元分配而改变码长。
- Huffman编码是紧致码，可以充分利用短码，以获得最短平均码长。
- Huffman编码只能应用于二进制码。
-
答案
1-对、2-错、3-对、4-错
第三四小问改成仅求出N=2时的紧致码。
-
答案
对单符号离散无记忆信源编三进制哈夫曼码。并求平均码长和编码效率。
\begin{bmatrix}S\\P(S)\end{bmatrix}=\begin{bmatrix}s_1&s_2&s_3&s_4&s_5&s_6&s_7&s_8\\0.4&0.2&0.1&0.1&0.05&0.05&0.05&0.05\end{bmatrix}
-
答案
评论区