信息论 第4章(哈夫曼编码和游程编码).ppt

概 述 变长编码 (1)香农编码 香农编码的例子 香农编码分析 (2)费诺（Fano）编码 费诺（Fano）编码的例子 费若（Fano）编码分析 （3）哈夫曼（Huffman）编码 哈夫曼（Huffman）编码的例子 哈夫曼（Huffman）编码分析 哈夫曼编码的扩展 游程编码的基本原理 游程编码用于二值图像的压缩 文件传真压缩方法简介 文件传真压缩方法具体流程 文件传真压缩的例子及压缩比例的计算 * * 信息论基础 The Basis of Information Theory 主题No4：哈夫曼编码和游程编码 将原始数据进行压缩的方法就是压缩编码,压缩编码可分为“无失真压缩编码”和“有失真压缩编码”两种.“无失真压缩编码”应用在要求绝对正确地恢复原始数据的场合如计算机文件资料;“有失真压缩编码”主要应用在多媒体数据的压缩上如图像压缩等. 基于信源的统计特性而产生的压缩编码方法统称“统计编码”,这些方法都是通过使用较短的代码来代替较长的,大量重复出现(概率较高的)的原始数据,从而达到压缩的目的.本章介绍的“哈夫曼编码”,“游程编码”,“基于字典的编码”,“算术编码”均为无失真压缩编码方法. 在第二章中，我们已经学习了有关变长码的理论知识，现在介绍编码的具体实现方法。常用变长码的编码方法有三种： （2）费诺编码； （1）香农编码； （3）哈夫曼编码. 香农编码：根据信源中各个消息的概率直接计算出代码:ni取小于I(xi)+1的最大整数. 香农编码方法简单，但不能保证得到的编码方案为最优方案。 7 6.66 0.01 x7 4 3.34 0.10 X6 3 2.74 0.15 X5 3 2.56 0.17? X4 3 2.48 0.18 X3 3 2.41 0.19 X2 3 2.34 0.20 X1 码长 - log2 p(xi) 符号概率p(xi) 消息符号 例1：对下面离散信源进行香农编码： 可求得该信源的信源熵： 以及平均码长： 由此得到该编码的平均信息传输率： (比特/符号) (码元/符号) (比特/码元时间) 费诺编码：将信源中的各个消息分成两组，尽可能使两组中各个消息的概率和相接近，然后对每组内的消息继续分组，直到每组只包含一个消息。 通过分组过程得到各个消息的编码，但不能保证得到的编码方案为最优方案。 下面是对例1进行费诺编码： 1111 1110 110 10 011 010 00 码字 1 0 第一次 1 0 1 0 第二次 1 0 1 0 第三次 4 1 0.01 x7 4 0 ?0.10 x6 3 0.15 x5 2 0.17? x4 3 0.18 x3 3 ?0.19 x2 2 0.20 x1 码长 第四次 符号概率p(xi) 消息符号 同样可求得该信源的信源熵： 以及平均码长： 由此得到该编码的平均信息传输率： (比特/符号) (码元/符号) (比特/码元时间) 哈夫曼编码：将信源中的各个消息按概率排序，不断将概率最小的两个消息进行合并，直到合并为一个整体，然后根据合并的过程分配码字，得到各个消息的编码。 该方法简单明了，并且可以保证最终的编码方案一定是最优编码方案。 下面是对例1进行哈夫曼编码： X6:0.10 X7:0.01 0.11 X5:0.15 X4:0.17 X3:0.18 X2:0.19 X1:0.20 0.26 0.35 0.39 0.61 1.00 对应的编码如下： 4 4 3 3 3 2 2 码长 0111 0110 010 001 000 11 10 编码 x7 x6 x5 x4 x3 x2 x1 信源 (码元/符号) 得平均码长： (比特/码元时间) 由此得到该编码的平均信息传输率： 我们介绍的哈夫曼编码方法是对具有多个独立消息的信源进行二进制编码,如果编码符号（码元）不是二进制的0和1,而是D进制，同样可以按照哈夫曼编码的方法来完成：只要将哈夫曼编码树由二叉树换成D叉树,每次合并的节点由两个改为D个,分配码元时,从左到右将0到D－1依次分配给各个路段,最后从根节点到各个叶节点（消息）读出编码结果即可. 很多信源产生的消息有一定相关性,往往连续多次输出同样的消息,同一个消息连续输出的个数称为游程(Run-Length).我们只需要输出一个消息的样本和对应重复次数,就完全可以恢复原来的消息系列.原始消息系列经过这种方式编码后,就成为一个个编码单元(如下图),其中标识码是一个能够和消息码区分的特殊符号. 游程长度 标识码 消息码 该编码方式就称为游程编码(RLC). 例如：有一个信源: 经过游程编码，得到： BBBBBBBBBB