2018/10/22,1,信息论基础,杜春娟 ducjscnu.edu.cn QQ:22282998 Tel:31889581,2018/10/22,2,第三章 数据压缩和信源编码,最佳编码 香农码 费诺码 哈夫曼码 算术码 香农费诺码 自适应算术码 其他无失真信源编码方法,2018/10/22,3,唯一可译码的判断法 首先观察是否是非奇异码。若是奇异码，肯定不是唯一可译码； 其次，计算是否满足Kraft不等式。若不满足一定不是唯一可译码； 然后将码画成一棵树图，观察是否满足异前置码的树图的构造，若满足则是唯一可译码。 或用Sardinas和Patterson设计的判断法：计算分组码中所有可能的尾随后缀集合F,观察F中有没有包含任一码字，若无则为唯一可译码；若有则一定不是唯一可译码。集合F的构造：首先观察码C中最短的码字是否是其它码字的前缀。若是，将其所有可能的尾随后缀排列出。而这些尾随后缀又可能是某些码字的前缀，再将由这些尾随后缀产生的新的尾随后缀列出。然后再观察这些新的尾随后缀是否是某些码字的前缀，再将产生的尾随后缀列出。这样，首先获得由最短的码字能引起的所有尾随后缀。接着，按照上述将次短的码字等等，所有码字可能产生的尾随后缀全部列出。由此得到码C的所有可能的尾随后缀组成的集合F。,2018/10/22,4,练习：有一信源，它有六个可能的输出，其概率分布如下表所示，表中给出了对应的码A、B、C、D、E和F, 求这些码中哪些是唯一可译码； 求哪些码是即时码； 对所有唯一可译码求出其平均码长,2018/10/22,5,几种编码方法,1. 香农编码 2. 费诺编码 3. 哈夫曼编码,2018/10/22,6,最佳码:定义:能载荷一定的信息量，且码字的平均长度最短，可分离的变长码的码字集合.,最佳编码,2018/10/22,7,香农指出，选择每个码字的长度 K i满足下式I (xi ) K iI(xi)+1， 就可以得到这种码。这种编码方法称为香农编码。 编码方法如下： (1) 将信源消息符号按其出现的概率大小依次排列 p(x1)p(x2)p (xn) (2) 确定满足下列不等式的整数码长K i：(3) 为了编成唯一可译码，计算第i个消息的累加概率 (4) 将累加概率Pi变换成二进制数。 (5) 取Pi二进数的小数点后K i位即为该消息符号的二进制码字。,1.香农编码方法,2018/10/22,8,例1：设信源共7个符号消息，其概论和累加概率如图所示。以i4为例，log0.17K4 log0.17+12.56K4 3.56 则K43则累加概率P40.57,变换为二进制为：0.1001故第四个消息的编码码字为100 其他码字可类似求出，见下页图,1.香农编码方法,2018/10/22,9,香农编码过程,1.香农编码方法,2018/10/22,10,各码字之间至少有一位数字不同，故是唯一可译码； 7个码字都不是延长码，故是即时码 这里L1，m2 平均码长为： 平均信息传输率为：,1.香农编码方法,2018/10/22,11,香农码实用性如何？ 例2 设信源有3个符号，概率分布为（0.10.5, 0.4, 0.1） 根据香农编码方法求出各个符号的码长分别为：？ 码字分别为？,1.香农编码方法,2018/10/22,12,1.香农编码方法,计算得码长分别为（1，2，4） 概率分布分别为（0，10，1110） 但实际上直观可看出（0，10，11）是更短的码，也是惟一可译码 所以，由此可知，香农编码的冗余度稍大，实际应用价值不强，但由于它是从编码定理直接得来，具有理论意义 另外当 左边等号成立时，编码效率比较高,2018/10/22,13,2.费诺编码方法,编码过程如下： (1) 将信源消息符号按其出现的概率大小依次排列：p(x1)p(x2)p(xn)。(2) 将依次排列的信源符号按概率值分为两大组，使两个组的概率之和近于相同，并对各组赋予一个二进制码元“0”和“1”。(3) 将每一大组的信源符号进一步再分成两组，使划分后的两个组的概率之和近于相同，并又赋予两个组一个二进制符号“0”和“1”。(4) 如此重复，直至每个组只剩下一个信源符号为止。(5) 信源符号所对应的码字即为费诺码。,2018/10/22,14,2.费诺编码方法,例 3 对例1的信源进行费诺编码，过程见下页表 平均码长为：平均信息传输率为：显然费诺要比香农的平均码长小 消息的传输速率大，说明编码效率高。,2018/10/22,15,费诺编码过程,2.费诺编码方法,2018/10/22,16,3.哈夫曼编码方法,编码过程如下：(1) 将n个信源消息符号按其出现的概率大小依次排列，p(x1)p(x2)p(xn)(2) 取两个概率最小的字母分别配以0和1两码元，并将这两个概率相加作为一个新字母的概率，与未分配的二进符号的字母重新排队。(3) 对重排后的两个概率最小符号重复步骤(2)的过程。(4) 不断继续上述过程，直到最后两个符号配以0和1为止。(5) 从最后一级开始，向前返回得到各个信源符号所对应的码元序列，即相应的码字。,2018/10/22,17,3.哈夫曼编码方法,第一个码元01互换,2018/10/22,18,该哈夫曼码的平均码长为,信息传输速率,由此可见，哈夫曼码的平均码长最小，消息传输速率最大，编码效率最高。,2018/10/22,19,3.哈夫曼编码方法,哈夫曼编码方法得到的码并非是唯一的。造成非唯一的原因如下：每次对信源缩减时，赋予信源最后两个概率最小的符号，用0和1是可以任意的，所以可以得到不同的哈夫曼码，但不会影响码字的长度。 对信源进行缩减时，两个概率最小的符号合并后的概率与其它信源符号的概率相同时，这两者在缩减信源中进行概率排序，其位置放置次序是可以任意的，故会得到不同的哈夫曼码。此时将影响码字的长度，一般将合并的概率放在上面，这样可获得较小的码方差,2018/10/22,20,3.哈夫曼编码方法,例4 设有离散无记忆信源,使用哈夫曼编码有几种方式？,2018/10/22,21,2018/10/22,22,3.哈夫曼编码方法,哈夫曼码的平均码长相等, 编码效率也相等。 但是两种码的质量不完全相同, 可用码方差来表示：,2018/10/22,23,可见，第二种哈夫曼编码方法得到的码方差要比第一种哈夫曼编码方法得到的码方差小许多。故第二种哈夫曼码的质量要好。,哈夫曼码是用概率匹配方法进行信源编码。它有两个明显特点： 一是哈夫曼码的编码方法保证了概率大的符号对应于短码，概率小的符号对应于长码，充分利用了短码； 二是缩减信源的最后二个码字总是最后一位不同，从而保证了哈夫曼码是即时码,2018/10/22,24,香农-费诺-埃利斯编码,将香农编码中的累加概率换成修正累加概率即可得到相应的香农-费诺-埃利斯编码：(1) 计算出各个信源符号的修正累加概率(2) 按下式计算第i个消息的二元代码组的码长(3) 将累加概率 (十进制小数)变换成二进制小数根据码长 取小数点后 个二进制符号作为第i个消息的码字,2018/10/22,25,香农费诺码,P59 例3.4.1 例3.4.2,2018/10/22,26,算术编码,算术式编码是一种非分组码，无需计算出所有N长信源序列的概率分布及码表，可以直接对输入的信源符号序列编码输出。这种方法是由香农-费诺-埃利斯编码直接扩展得到的。算术式编码算法的中心思想是高效地计算n长信源符号序列x的分布概率p(x)和累积概率F(x)，然后用区间F(x)-p(x), F(x)中的一个值来作为x的码字。 假定信源是二进制的，并且分组的长度n已知。定义5.14 两个n长信源符号序列x和y，定义x大于y，当第一个使得 的i有 。,2018/10/22,27,自适应算术码,P64,2018/10/22,28,其他无失真信源编码方法,游程编码 是霍夫曼编码的一种改进和应用，主要用于黑白二值文件的传真数据压缩。 由于传真文件中连“0”和连“1”较多这些连“0”或连“1”的字符串称为游程对游程长度进行霍夫曼编码或其他的编码处理就可以达到压缩数据的目的。右 图是一幅1050黑白二值图像。 ,图 二值图像,2018/10/22,29,MH编码是一种实用的游程编码算法，应用于黑、白传真数据的压缩编码，根据不同的黑、白游程长度有两张结尾码表和两张组合码表其基本的编码规范为(1) 游程长度在063时，直接查表用相应的结尾码作为码字；(2) 游程长度在641728范围内时，用组合码加上结尾码作为相应的码字；(3) 每行的第一个游程规定为白游程(长度可以为零)，每行用一个结束码(EOL) 终止；(4) 在传输时，每页数据之前加一个结束码，每页尾部连续实用6个结束码。,2018/10/22,30,LZW码,LZW码也称基于字典的编码方法，它是定长码。 (1) 基于字典编码的基本原理计算机文件是以字节为单位组成的。LZW码是一种自适应变码，它的字典是直接由被压缩文件在编码过程中生成的。 (2) 字典的构成字典的容量为4096(04095),序号用12bit表示最后一个单词(第4095个单词)为空。 (3) 算法字典初始化动态数据初始化：初始化新单词存放位置指针P，将它指向字典的第一个空位置。,2018/10/22,31,如果文件再没有字符了，输出当前单词W的序号。编码结束。如果文件中还有字符，把当前单词W作为前缀，再从被压缩文件中读入一个字符CH，把CH作为尾字符，得到一个单词 。如果字典中已有 ，则将 看作当前单词W，返回。如果字典中没有 (发现一个新单词)，先将原单词W的序号输出，再加新单词 ，增加到字典中，然后把刚刚读入的字符CH作为当前单词W，返回。 (4) 适用文件类型不适合小文件的压缩(因为压缩编码初期，由于字典中的单词很少，字典对压缩效果的贡献也很少，主要是进行字典的扩充)，也不适合太大的文件(因字典容量有限，文件太大时字典满了，效率将受到制约)适合内容有明显单词结构的文件(如文本文件、程序文件)。,2018/10/22,32,(5) 译码字典初始化动态数据初始化如果压缩中已经没有码字，解码结束。否则继续读入一个码字。如果读入的码字是无效码字FFF，则解码结束，否则下一步。如果在字典中已经有该码字对应的单词，则采用递归算法，输出该单词的内容。并将单词的第一个有效字符作为尾字符，将已经记忆的前一个码字作为前缀，组成一个新单词，写入字典中，然后将当前码字记忆下来，返回；否则，首先在字典中生成新的单词，然后再输出这个单词，将新单词的码字记忆下来，返回。这时的新单词一定是首尾相同的单词。 (6) LZW编码算法的优化,2018/10/22,33,10进制 2进制 （小数）,(0.6875)10 = (0.1011)2,0.6875 2,1.3750, 整数部分为 1,0.375 2,0.750 2, 整数部分为 0,1.500, 整数部分为 1,0.500 2,1.0, 整数部分为 1 小数部分为 0,补充：,