多媒体编码与通信-熵编码课件.pptx
多媒体编码与通信多媒体编码与通信111111第二章 熵编码技术n熵编码概述n信息熵理论nHuffman编码n指数哥伦布编码n算术编码n基于上下文的熵编码n自适应熵编码n其他无损编码方法熵编码概述n熵编码是针对统计冗余的压缩编码方法n熵编码的理论基础是shannon的信息熵理论，所以被叫做熵编码n熵编码是无损编码n熵编码是压缩编码中最重要的一种编码方法，是各种编解码方案中都要采用的编码方法信息熵理论假设无记忆信息源 M=mi,miS,i=0.N-1符号表 S=sk，k=0.K-1符号sk出现的概率为pk，k=0.K-1符号sk的信息量为 h(sk)=-log2(pk)信息熵理论符号出现的概率越小，所包含的信息量越大。经过理论分析和实践检验，证明概率的倒数的对数是最符合概率和信息量之间关系的（2.26，9.58）信息源的信息量是构成它的所有符号的信息量的和，即(M)=h(m0)+h(mN-1)信息熵理论信息源的熵是构成它的所有符号的平均信息量H(M)=(h(m0)+h(mN-1)/N =(-pklog(pk)当所有符号出现的概率相同时，信息源的熵最大当对数以2为底时，(M)是编码信息源所需的最小位数，而H(M)是每个符号的平均位数信息熵理论M=AAAAAAAAAAAAAAABBBBBBBCCCCCCDDDDDDEEEEEhuffman编码Shannon-Fano算法根据出现概率从大到小将符号排成一列将符号列分成上下两部分，使两部分的概率之和尽量接近上半部分标0，下半部分标1对所分的两部分重复上述步骤，直到所有分组都只包含一个符号huffman编码huffman算法寻找概率最小的两个符号将概率最小的两个符号连接成一个新符号，新符号的概率为原来的两个符号的概率之和用新符号替换原来的两个符号重复上述步骤，直到符号集中只剩下一个符号哈夫曼编码过程演示A1A1A2A2A3A3A4A4A5A5A6A6A7A70.230.230.210.210.180.180.150.150.130.130.070.070.030.03 1 1 0 00.100.101 1 0 00.230.23 1 1 0 00.330.33 1 1 0 00.440.44 1 1 0 00.560.560 0 1 11 1编码编码编码编码 01 01 00 00 111 111 110 110 101 1011001100110001000huffman编码ASCII码(定长码)l39 x 8=312Shannon-Fano算法l15x2+7x2+6x2+6x3+5x3=89huffmann算法l15x1+7x3+6x3+6x3+5x3=87理论最小值l85.25指数哥伦布码nExponential-Golomb code=Exp-Golomb code nHuffmann码的局限只适用于有限符号集需要传送或保存码表n指数哥伦布码的优点可以对无限符号集编码不需要传送或保存码表指数哥伦布码阶数码字结构CodeNum取值范围k=0100 1 x0120 0 1 x1 x0360 0 0 1 x2 x1 x0714.k=11 x0010 1 x1 x0250 0 1 x2 x1 x06130 0 0 1 x3 x2 x1 x01429.k=21 x1 x0030 1 x2 x1 x04110 0 1 x3 x2 x1 x012270 0 0 1 x4 x3 x2 x1 x02859.指数哥伦布码n指数哥伦布码的局限通常不是最优的，只有概率分布合适的时候是0阶指数哥伦布码总共用了109位1阶指数哥伦布码总共用了112位需要根据符号的概率分布选择合适的阶数算数编码的由来nHuffman码和指数哥伦布码的码字必须是整数个bit，这就造成了大多数情况下huffman码无法达到理论极限，甚至距离理论极限很远。n例如，如果一个符号的概率是1/3，则该符号的编码位数最优是1.6左右，而huffman码却只能为其设计1位或2位的码字。n当一个符号的概率特别高时，例如大于0.9，则最优码长是0.15位，而huffman码只能是1位，比最优码长长6倍n当符号集中只有两个符号时（例如二值图像），huffman码几乎失去作用。解决这个问题的方法是将若干个相连的符号打包，从而产生一个较大的符号集，然后再应用huffman编码。算数编码的基本思想n一个由服从已知概率分布的符号集中的符号组成的符号串（假设长度为N）实际上是一个事件，这个事件发生的概率可以计算出来。n假设所有长度为N的事件共有K个，它们的概率之和为1。n把这些事件按照某种规则排成一列，在0，1）上为每个事件分配一个区间Lk,Hk），区间长度等于第k个事件的概率，那么得到一个0，1）的分割n用一个落入某区间的值，就可以指示该区间对应的事件发生了，这就是算术编码的基本思想算数编码的编码算法pi是第i个符号的概率，i=0.K-1C0=0,Ck=p0+.+pk-1,k=1.KI(m)是符号m在符号集中的索引Low=0;High=1;range=High Low;for(n=0;nN;n+)/有N个符号需要编码 High=Low+CI(mn)+1*range;Low =Low+CI(mn)*range;range=High Low;寻找一个值寻找一个值v v，使得，使得 Low=v Low=v 且且 v+d=Highv+d=High且用二进制表示时且用二进制表示时v v的有效的有效位数最少。其中位数最少。其中d d是是v v的最低有效位表示的值。例如的最低有效位表示的值。例如v v为为8 8位时位时d d就是就是1/2561/256算数编码的解码算法pi是第i个符号的概率，i=0.K-1C0=0,Ck=p0+.+pk-1,k=1.Kb0,b1,是待解码bit串Di=Ci;/动态区间For(n=0;nN;n+)/已知有已知有N N个符号需要解码个符号需要解码 读入码流，直到直到v,v+d)v,v+d)落入某个区间落入某个区间Dk,Dk+1)Dk,Dk+1)解码得到符号集中索引为k的符号 range=Dk+1 Dk;D0=Dk;Di=D0+Ci*range;其中其中d d是是v v的最低有效位表示的值。的最低有效位表示的值。算数编码的终止码流的终止因为算术编码器输出的比特串是作为一个很长的码流的一部分，为了不受后续bit的影响，必须要求low=v and v+d=high解码过程的终止已知要解码的符号的个数在符号集中增加结束符号EOB算数编码的区间放大n浮点数的精度是有限的，当待编码的符号串很长时，会出现range过小的情况n解决的方法是每编码一个符号都对区间进行放大n解码过程也进行同样的放大，以保证编解码所得的区间一致算数编码的整数实现n浮点数运算复杂，为了降低复杂度，发明了用定点运算实现的算术编码器和解码器n定点的算术编码器和解码器一定包含区间放大算数编码举例n符号集A,B,C，概率0.8,0.1,0.1，分割0,0.8,0.9,1n符号串AAAAA AAABC符号十进制low十进制high二进制low二进制high输出bitA00.8011100A00.64010111A00.512010010A00.4096011011A00.32768000010A00.262144011011A00.2097152001111A00.16777216010011B0.1342177280.1509949941110000111C0.14931726740.15099499411001001110010011001基于上下文的熵编码n考虑了符号的条件概率，即根据已经出现的符号调整下一个符号出现的概率n基于上下文的熵编码可以有效的提高编码效率，具体提高多少和符号的相关性有关n基于上下文的熵编码可以和huffman、指数哥伦布、算术编码等结合使用自适应熵编码n在事先不知道符号的概率分布的情况下，或者不愿意使用固定的码表和概率表的时候，可以使用自适应熵编码技术n自适应熵编码就是一边编码一边统计，根据统计结果动态生成概率表和变长码表n自适应熵编码可以和huffmann、指数哥伦布、算术编码等结合n自适应熵编码和基于上下文的熵编码不同其他无损编码方法n游程编码(run-length coding)n字典压缩静态方法与自适应方法Jacob ziv;Abraham Lempel;Terry WelchLZ77 LZ78 LZW ZIP ARJ RARnMMR一种二值图像压缩方法用于传真机学习并没有结束，希望继续努力学习并没有结束，希望继续努力Thanks for listening,this course is expected to bring you value and help为方便学习与使用课件内容，课件可以在下载后自由编辑
