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

信息论基础TheBasisofInformationTheory主题No4：哈夫曼编码和游程编码概述将原始数据进行压缩的方法就是压缩编码,压缩编码可分为“无失真压缩编码”和“有失真压缩编码”两种.“无失真压缩编码”应用在要求绝对正确地恢复原始数据的场合如计算机文件资料;“有失真压缩编码”主要应用在多媒体数据的压缩上如图像压缩等.基于信源的统计特性而产生的压缩编码方法统称“统计编码”,这些方法都是通过使用较短的代码来代替较长的,大量重复出现(概率较高的)的原始数据,从而达到压缩的目的.本章介绍的“哈夫曼编码”,“游程编码”,“基于字典的编码”,“算术编码”均为无失真压缩编码方法.变长编码在第二章中，我们已经学习了有关变长码的理论知识，现在介绍编码的具体实现方法。常用变长码的编码方法有三种：（2）费诺编码；（1）香农编码；（3）哈夫曼编码.(1)香农编码香农编码：根据信源中各个消息的概率直接计算出代码:ni取小于I(xi)+1的最大整数.香农编码方法简单，但不能保证得到的编码方案为最优方案。香农编码的例子消息符号符号概率p(xi)-

log2p(xi)码长X10.202.343X20.192.413X30.182.483X40.17

2.563X50.152.743X60.103.344x70.016.667例1：对下面离散信源进行香农编码：香农编码分析可求得该信源的信源熵：以及平均码长：由此得到该编码的平均信息传输率：(比特/符号)(码元/符号)(比特/码元时间)(2)费诺（Fano）编码费诺编码：将信源中的各个消息分成两组，尽可能使两组中各个消息的概率和相接近，然后对每组内的消息继续分组，直到每组只包含一个消息。通过分组过程得到各个消息的编码，但不能保证得到的编码方案为最优方案。费诺（Fano）编码的例子下面是对例1进行费诺编码：消息符号符号概率p(xi)第一次第二次第三次第四次码字码长x10.2000002x2

0.19100103x30.1810113x40.17

10102x50.15101103x6

0.101011104x70.01111114费若（Fano）编码分析同样可求得该信源的信源熵：以及平均码长：由此得到该编码的平均信息传输率：(比特/符号)(码元/符号)(比特/码元时间)（3）哈夫曼（Huffman）编码哈夫曼编码：将信源中的各个消息按概率排序，不断将概率最小的两个消息进行合并，直到合并为一个整体，然后根据合并的过程分配码字，得到各个消息的编码。该方法简单明了，并且可以保证最终的编码方案一定是最优编码方案。哈夫曼（Huffman）编码的例子下面是对例1进行哈夫曼编码：X6:0.10X7:0.010.11X5:0.15X4:0.17X3:0.18X2:0.19X1:0.200.260.350.390.611.00对应的编码如下：信源x1x2x3x4x5x6x7编码101100000101001100111码长2233344哈夫曼（Huffman）编码分析(码元/符号)得平均码长：(比特/码元时间)由此得到该编码的平均信息传输率：

哈夫曼编码的扩展我们介绍的哈夫曼编码方法是对具有多个独立消息的信源进行二进制编码,如果编码符号（码元）不是二进制的0和1,而是D进制，同样可以按照哈夫曼编码的方法来完成：只要将哈夫曼编码树由二叉树换成D叉树,每次合并的节点由两个改为D个,分配码元时,从左到右将0到D－1依次分配给各个路段,最后从根节点到各个叶节点（消息）读出编码结果即可.游程编码的基本原理很多信源产生的消息有一定相关性,往往连续多次输出同样的消息,同一个消息连续输出的个数称为游程(Run-Length).我们只需要输出一个消息的样本和对应重复次数,就完全可以恢复原来的消息系列.原始消息系列经过这种方式编码后,就成为一个个编码单元(如下图),其中标识码是一个能够和消息码区分的特殊符号.消息码标识码

游程长度该编码方式就称为游程编码(RLC).例如：有一个信源:经过游程编码，得到：BBBBBBBBBBXXXXXXXXJJJJJJJJJAAAAAAAAAAAAAAAAAUUUUUUUUUUUUUUUUUUUUB#10X#8J#9A#17U#20其中＃为标识码.游程编码用于二值图像的压缩图像在计算机中是用像素表示的,我们将一幅图像分成很多行,每行又分成很多像素,每个像素用亮度值和彩色数据表示.二值图像是指像素只有两种取值:0表示背景(底色),1表示前景(内容).如果二值图像完全采用按像素储存的方式来表示,需要的储存空间是非常大的.为了对二值图像进行压缩,需要对二值图像数据的统计特性进行分析,统计特性表明,二值图像中的黑白像素出现的概率相差很大;且同一种像素连续出现的概率也很大,即平均游程长度比较长,采用游程编码一定可以取得满意效果.文件传真压缩方法简介在二值图像的一行扫描像素中,黑白游程总是相间的,只要知道第一个游程的颜色,后面各个游程的颜色也就可以确定了.如果将第一个游程的颜色固定为白色,则所有第奇数个游程也是白色游程,而所有第偶数个游程必然是黑色游程.实际情况下,有可能第一个游程的颜色为黑色,我们就需要人为在他前面插入一个游程长度为零的白色游程,以满足“第一个游程的颜色固定为白色”的规定.在游程颜色已经规定后,游程编码时就可以将“消息码”和“标识码”省略,只保留游程长度数据即可.文件传真压缩方法具体流程主要利用终止码和形成码(见书本P43-44),一般A4的纸每行的像素为1728,具体编码规则如下:（1）当游程长度小于64时，直接用一个对应的终止码表示。（2）当游程长度在64到1728之间时，用一个形成码加一个终止码表示。例如:白游程为662时用640形成码(白)加22终止码(白)表示,即:011001110000011.黑游程为256时用256形成码(黑)加0终止码(黑)表示,即:0000010110110000110111.（3）每行开始必须为白游程,如果实际情况是从黑游程开始,就用一个长度为零的白游程作为开始.每行结束必须加一个同步码EOL.（4）每页文件必须以同步码EOL开始,连续6个EOL码表示文件传输结束.文件传真压缩的例子及压缩比例的计算如果某行扫描的结果如下表所示:白游程黑游程白游程黑游程