编码理论 第二版 教学课件 作者 田丽华 第1-5章第3章.ppt

《编码理论 第二版 教学课件 作者 田丽华 第1-5章第3章.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第3章　无失真信源编码方法3.1霍夫曼码和其他编码方法3.2算术编码3.3游程编码3.4通用编码3.1　霍夫曼码及其他编码方法3.1.1二元霍夫曼码1952年霍夫曼提出了一种构造最佳码的方法，它是一种逐个符号的编码方法。所得的码字是异前置码的变长码，其平均码长最短，是最佳变长码，又称霍夫曼码，二元霍夫曼码编码步骤如下：(1)将n元信源U的各个符号ui按概率分布p（ui）以递减次序排列起来。(2)将两个概率最小的信源符号合并成一个新符号，新符号的值为两个信源符号值的和，从而得到只包含n－1个符号的新信源，称为U信源的缩减信源U1

2、。(3)把缩减信源U1的符号仍按概率大小以递减次序排列，然后将其中两个概率最小的符号合并成一个符号，这样又形成了n－2个符号的缩减信源U2。(4)依次继续下去，直至信源最后只剩下１个符号为止。　(5)将每次合并的两个信源符号分别用0和1码符号表示。　(6)从最后一级缩减信源开始，向前返回，就得出各信源符号所对应的码符号序列，即得各信源符号对应的码字。［例3-1］离散无记忆信源对应的霍夫曼编码如图3－1所示。信源熵：(比特/信源符号)平均码长：(码符号/信源符号)编码效率：图3－1例3－1霍夫曼编码【例3－2】　离散无记忆信源的两种

3、霍夫曼编码如图3－2所示。图3－2例3－2的两种霍夫曼编码图3-3中（a）、（b)所示两种方案的霍夫曼编码平均码长都为(码符号/信源符号)信源熵：(比特/信源符号)编码效率：图3－3例3－2对应的霍夫曼树两种码有相同的平均码长，有相同的编码效率，但每个信源符号的码长却不相同，其均方差也不同。下面分别计算两种码的均方差σ2，即(方法a方差)(方法b方差)可见，方法（a）的方差比方法（b）的方差要小许多。方法(a）的具体编码原则是把合并后的概率总是放在其他相同概率的信源符号之上（或之左）;方法（b)的编码原则是把合并后的概率放在其他相

4、同概率的信源符号之下（或之右）。从上面的分析可以看出，方法（a)要优于方法（b)。可见，霍夫曼码得到的码并非是惟一的。因为对缩减信源的两个概率最小的符号，可以任意的用0和1码，所以可得到不同的码，但它们只是码字具体结构不同，而其码长不变，平均码长也不变，因此没有本质区别。另外，若当缩减信源中缩减合并后的符号的概率与其他信源符号概率相同时，从编码方法上来说，对等概率的符号哪个放在上面、哪个放在下面是没有区别的，但得到的码是不同的。对这两种不同的码，它们的码长各不同，然而平均码长是相同的。在编码中，对等概率消息，若将新合并的消息排列到

5、上支路，可以证明它将缩短码长的方差，即编出的码更接近等长码；同时可使合并的元素重复编码次数减少，使短码得到充分利用。3.1.2m元霍夫曼码前面讨论的二元霍夫曼码的编码方法可以推广到m元编码中，不同的只是每次把概率最小的m个符号合并成一个新的信源符号，并分别用0，1，…，m－1等码元来表示。　　为了使短码得到充分利用，使平均码长最短，必须使最后一步的缩减信源有m个信源符号。因此，对于m元编码，信源U的符号个数n必须满足：n＝（m－1）Q＋m（3-1）式中：n—信源符号个数；m—进制数（码元数）；Q—缩减次数。对于二元码，总能找到一

6、个Q满足式（3－1）。但对于m元码，n为任意正整数时不一定能找到一个Q满足式（3－1），此时，可以人为地增加一些概率为零的符号，以满足式（3－1），然后取概率最小的m个符号合并成一个新符号（结点），并把这些符号的概率相加作为该结点的概率，重新按概率由大到小顺序排队，再取概率最小的m个符号（结点）合并；如此下去直至树根。下面给出m元霍夫曼的编码步骤：　　(1)验证所给n是否满足式（3－1），若不满足该式，可以人为地增加一些概率为零的符号，以使最后一步有m个信源符号。　　(2)将信源符号按概率递减次序排列，取概率最小的m个符号合并

7、成一个新结点，并分别用0，1，…，m－１给各分支赋值,把这些符号的概率相加作为该新结点的概率。　　(3)将新结点和剩下结点重新排队，重复步骤（2），如此下去直至树根。　　(4)取树根到叶子（信源符号对应结点）的各树枝上的值，得到各符号码字。【例3－3】　已知信源其三元霍夫曼编码如图3-4所示.，四元霍夫曼编码如图（3-5）所示。图3-4例3-3三元霍夫曼编码图3－5例3－3四元霍夫曼编码信源熵：(比特/信源符号)两种编码的平均码长分别为：因为lb3＝1.58(比特/信源符号),lb4＝2(比特/信源符号)，所以它们的编码效率分

8、别为：可见，要发挥霍夫曼编码的优势，一般情况下，信源符号集的元数应远大于码元数。对例3－3，若编五元码，只能对每个信源符号赋予一个码数，等于没有编码，当然也无压缩可言。那么，什么样的编码能获得最佳的压缩效果呢？下面将讨论这个问题。3.1.4　香农编