,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,#,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2020/10/26,#,多媒体编码与通信,111111,多媒体编码与通信,1,第二章 熵编码技术,熵编码概述,信息熵理论,Huffman,编码,指数哥伦布编码,算术编码,基于上下文的熵编码,自适应熵编码,其他无损编码方法,第二章 熵编码技术熵编码概述,2,熵编码,概述,熵编码是针对统计冗余的压缩编码方法,熵编码的理论基础是,shannon,的信息熵理论，所以被叫做熵编码,熵编码是无损编码,熵编码是压缩编码中最重要的一种编码方法，是各种编解码方案中都要采用的编码方法,熵编码概述熵编码是针对统计冗余的压缩编码方法,3,信息熵,理论,假设无记忆信息源,M=m,i,m,i,S,i=0.N-1,符号表,S=s,k,，,k=0.K-1,符号,s,k,出现的概率为,p,k,，,k=0.K-1,符号,s,k,的信息量为,h(s,k,)=-log,2,(p,k,),信息熵理论假设无记忆信息源,4,信息熵,理论,符号出现的概率越小，所包含的信息量越大。经过理论分析和实践检验，证明概率的倒数的对数是最符合概率和信息量之间关系的（,2.26,，,9.58,）,信息源的信息量是构成它的所有符号的信息量的和，即,(M)=h(m,0,)+,+h(m,N-1,),信息熵理论符号出现的概率越小，所包含的信息量越大。经过理论分,5,信息熵,理论,信息源的熵是构成它的所有符号的平均信息量,H(M)=(h(m,0,)+,+h(m,N-1,)/N,=,(,-p,k,log(p,k,),当所有符号出现的概率相同时，信息源的熵最大,当对数以,2,为底时，,(M),是编码信息源所需的最小位数，而,H(M),是每个符号的平均位数,信息熵理论信息源的熵是构成它的所有符号的平均信息量,6,信息熵,理论,M=,AAAAAAAA,AAAAAAA,BBBBBBB,CCCCCC,DDDDDD,EEEEE,信息熵理论M=,7,huffman,编码,Shannon-Fano,算法,根据出现概率从大到小将符号排成一列,将符号列分成上下两部分，使两部分的概率之和尽量接近,上半部分标,0,，下半部分标,1,对所分的两部分重复上述步骤，直到所有分组都只包含一个符号,huffman编码Shannon-Fano算法,8,huffman,编码,huffman,算法,寻找概率最小的两个符号,将概率最小的两个符号连接成一个新符号，新符号的概率为原来的两个符号的概率之和,用新符号替换原来的两个符号,重复上述步骤，直到符号集中只剩下一个符号,huffman编码huffman算法,9,哈夫曼编码过程演示,A1,A2,A3,A4,A5,A6,A7,0.23,0.21,0.18,0.15,0.13,0.07,0.03,1,0,0.10,1,0,0.23,1,0,0.33,1,0,0.44,1,0,0.56,0,1,1,编码,01,00,111,110,101,1001,1000,哈夫曼编码过程演示A10.23 1 00.101 00.23,10,huffman,编码,ASCII,码,(,定长码,),39 x 8=312,Shannon-Fano,算法,15x2+7x2+6x2+6x3+5x3=89,huffmann,算法,15x1+7x3+6x3+6x3+5x3=87,理论最小值,85.25,huffman编码ASCII码(定长码),11,指数哥伦布,码,Exponential-Golomb code=Exp-Golomb code,Huffmann,码的局限,只适用于有限符号集,需要传送或保存码表,指数哥伦布码的优点,可以对无限符号集编码,不需要传送或保存码表,指数哥伦布码Exponential-Golomb code,12,指数哥伦布,码,阶数,码字结构,CodeNum,取值范围,k=0,1,0,0 1 x,0,1,2,0 0 1 x,1,x,0,3,6,0 0 0 1 x,2,x,1,x,0,7,14,.,.,k=1,1 x,0,0,1,0 1 x,1,x,0,2,5,0 0 1 x,2,x,1,x,0,6,13,0 0 0 1 x,3,x,2,x,1,x,0,14,29,.,.,k=2,1 x,1,x,0,0,3,0 1 x,2,x,1,x,0,4,11,0 0 1 x,3,x,2,x,1,x,0,12,27,0 0 0 1 x,4,x,3,x,2,x,1,x,0,28,59,.,.,指数哥伦布码阶数码字结构CodeNum取值范围k=010,13,指数哥伦布,码,指数哥伦布码的局限,通常不是最优的，只有概率分布合适的时候是,0,阶指数哥伦布码总共用了,109,位,1,阶指数哥伦布码总共用了,112,位,需要根据符号的概率分布选择合适的阶数,指数哥伦布码指数哥伦布码的局限,14,算数,编码的由来,Huffman,码和指数哥伦布码的码字必须是整数个,bit,，这就造成了大多数情况下,huffman,码无法达到理论极限，甚至距离理论极限很远。,例如，如果一个符号的概率是,1/3,，则该符号的编码位数最优是,1.6,左右，而,huffman,码却只能为其设计,1,位或,2,位的码字。,当一个符号的概率特别高时，例如大于,0.9,，则最优码长是,0.15,位，而,huffman,码只能是,1,位，比最优码长长,6,倍,当符号集中只有两个符号时（例如二值图像），,huffman,码几乎失去作用。解决这个问题的方法是将若干个相连的符号打包，从而产生一个较大的符号集，然后再应用,huffman,编码。,算数编码的由来Huffman码和指数哥伦布码的码字必须是整数,15,算数,编码的基本思想,一个由服从已知概率分布的符号集中的符号组成的符号串（假设长度为,N,）实际上是一个事件，这个事件发生的概率可以计算出来。,假设所有长度为,N,的事件共有,K,个，它们的概率之和为,1,。,把这些事件按照某种规则排成一列，在,0,，,1,）上为每个事件分配一个区间,L,k,H,k,），区间长度等于第,k,个事件的概率，那么得到一个,0,，,1,）的分割,用一个落入某区间的值，就可以指示该区间对应的事件发生了，这就是算术编码的基本思想,算数编码的基本思想一个由服从已知概率分布的符号集中的符号组成,16,算数,编码的编码,算法,p,i,是第,i,个符号的概率，,i=0.K-1,C0=0,Ck=p,0,+.+,p,k-1,k=1.K,I(m),是符号,m,在符号集中的索引,Low=0;High=1;range=High Low;,for(n=0;nN;n+)/,有,N,个符号需要编码,High=Low+CI(m,n,)+1*range;,Low =Low+CI(m,n,)*range;,range=High Low;,寻找一个值,v,，使得,Low=v,且,v+d=High,且用二进制表示时,v,的有效位数最少。其中,d,是,v,的最低有效位表示的值。例如,v,为,8,位时,d,就是,1/256,算数编码的编码算法pi是第i个符号的概率，i=0.K-1,17,算数,编码的解码,算法,p,i,是第,i,个符号的概率，,i=0.K-1,C0=0,Ck=p,0,+.+,p,k-1,k=1.K,b,0,b,1,是待解码,bit,串,Di=Ci;/,动态区间,For(n=0;nN;n+)/,已知有,N,个符号需要解码,读入码流，,直到,v,v+d),落入某个区间,Dk,Dk+1),解码得到符号集中索引为,k,的符号,range=Dk+1 Dk;,D0=Dk;,Di=D0+Ci*range;,其中,d,是,v,的最低有效位表示的值。,算数编码的解码算法pi是第i个符号的概率，i=0.K-1,18,算数,编码的终止,码流的终止,因为算术编码器输出的比特串是作为一个很长的码流的一部分，为了不受后续,bit,的影响，必须要求,low=v and v+d=high,解码过程的终止,已知要解码的符号的个数,在符号集中增加结束符号,EOB,算数编码的终止码流的终止,19,算数,编码的区间,放大,浮点数的精度是有限的，当待编码的符号串很长时，会出现,range,过小的情况,解决的方法是每编码一个符号都对区间进行放大,解码过程也进行同样的放大，以保证编解码所得的区间一致,算数编码的区间放大浮点数的精度是有限的，当待编码的符号串很长,20,算数,编码的整数,实现,浮点数运算复杂，为了降低复杂度，发明了用定点运算实现的算术编码器和解码器,定点的算术编码器和解码器一定包含区间放大,算数编码的整数实现浮点数运算复杂，为了降低复杂度，发明了用定,21,算数,编码举例,符号集,A,B,C,，概率,0.8,0.1,0.1,，分割,0,0.8,0.9,1,符号串,AAAAA AAABC,符号,十进制,low,十进制,high,二进制,low,二进制,high,输出,bit,A,0,0.8,0,11100,A,0,0.64,0,10111,A,0,0.512,0,10010,A,0,0.4096,0,11011,A,0,0.32768,0,00010,A,0,0.262144,0,11011,A,0,0.2097152,0,01111,A,0,0.16777216,0,10011,B,0.134217728,0.150994994,11100,00111,C,0.1493172674,0.150994994,11001,00111,0010011001,算数编码举例符号集A,B,C，概率0.8,0.1,22,基于上下文的熵编码,考虑了符号的条件概率，即根据已经出现的符号调整下一个符号出现的概率,基于上下文的熵编码可以有效的提高编码效率，具体提高多少和符号的相关性有关,基于上下文的熵编码可以和,huffman,、指数哥伦布、算术编码等结合使用,基于上下文的熵编码考虑了符号的条件概率，即根据已经出现的符号,23,自,适应熵编码,在事先不知道符号的概率分布的情况下，或者不愿意使用固定的码表和概率表的时候，可以使用自适应熵编码技术,自适应熵编码就是一边编码一边统计，根据统计结果动态生成概率表和变长码表,自适应熵编码可以和,huffmann,、指数哥伦布、算术编码等结合,自适应熵编码和基于上下文的熵编码不同,自适应熵编码在事先不知道符号的概率分布的情况下，或者不愿意使,24,其他无损编码方法,游程编码,(run-length coding),字典压缩,静态方法与自适应方法,Jacob ziv;Abraham Lempel;Terry Welch,LZ77 LZ78 LZW ZIP ARJ RAR,MMR,一种二值图像压缩方法,用于传真机,其他无损编码方法游程编码(run-length codin,25,学习并没有结束，希望继续努力,Thanks for listening,this course is expected to bring you value and help,为方便学习与使用课件内容，课件可以在下载后自由编辑,学习并没有结束，希望继续努力,26,