多媒体编码与通信-熵编码

多媒体编码与通信赵海武上海大学通信学院networkmultimedia@126.com111111第二章熵编码技术熵编码概述信息熵理论Huffman编码指数哥伦布编码算术编码基于上下文的熵编码自适应熵编码其他无损编码方法熵编码概述熵编码是针对统计冗余的压缩编码方法熵编码的理论基础是shannon的信息熵理论，所以被叫做熵编码熵编码是无损编码熵编码是压缩编码中最重要的一种编码方法，是各种编解码方案中都要采用的编码方法信息熵理论假设无记忆信息源

M={mi},mi∈S,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={AAAAAAAAAAAAAAABBBBBBBCCCCCCDDDDDDEEEEE}huffman编码Shannon-Fano算法根据出现概率从大到小将符号排成一列将符号列分成上下两部分，使两部分的概率之和尽量接近上半部分标0，下半部分标1对所分的两部分重复上述步骤，直到所有分组都只包含一个符号huffman编码huffman算法寻找概率最小的两个符号将概率最小的两个符号连接成一个新符号，新符号的概率为原来的两个符号的概率之和用新符号替换原来的两个符号重复上述步骤，直到符号集中只剩下一个符号哈夫曼编码过程演示A1A2A3A4A5A6A70.03100.10100.23100.33100.44

1

00.56011编码010011111010110011000huffman编码ASCII码(定长码)39x8=312Shannon-Fano算法15x2+7x2+6x2+6x3+5x3=89huffmann算法15x1+7x3+6x3+6x3+5x3=87理论最小值85.25指数哥伦布码Exponential-Golombcode=Exp-GolombcodeHuffmann码的局限只适用于有限符号集需要传送或保存码表指数哥伦布码的优点可以对无限符号集编码不需要传送或保存码表指数哥伦布码阶数码字结构CodeNum取值范围k=01001x01～2001x1x03～60001x2x1x07～14............k=11x00～101x1x02～5001x2x1x06～130001x3x2x1x014～29............k=21x1x00～301x2x1x04～11001x3x2x1x012～270001x4x3x2x1x028～59............指数哥伦布码指数哥伦布码的局限通常不是最优的，只有概率分布合适的时候是0阶指数哥伦布码总共用了109位1阶指数哥伦布码总共用了112位需要根据符号的概率分布选择合适的阶数算数编码的由来Huffman码和指数哥伦布码的码字必须是整数个bit，这就造成了大多数情况下huffman码无法达到理论极限，甚至距离理论极限很远。例如，如果一个符号的概率是1/3，则该符号的编码位数最优是1.6左右，而huffman码却只能为其设计1位或2位的码字。当一个符号的概率特别高时，例如大于0.9，则最优码长是0.15位，而huffman码只能是1位，比最优码长长6倍当符号集中只有两个符号时（例如二值图像），huffman码几乎失去作用。解决这个问题的方法是将若干个相连的符号打包，从而产生一个较大的符号集，然后再应用huffman编码。算数编码的基本思想一个由服从已知概率分布的符号集中的符号组成的符号串（假设长度为N）实际上是一个事件，这个事件发生的概率可以计算出来。假设所有长度为N的事件共有K个，它们的概率之和为1。把这些事件按照某种规则排成一列，在[0，1）上为每个事件分配一个区间[Lk,Hk），区间长度等于第k个事件的概率，那么得到一个[0，1）的分割用一个落入某区间的值，就可以指示该区间对应的事件发生了，这就是算术编码的基本思想算数编码的编码算法pi是第i个符号的概率，i=0..K-1C[0]=0,C[k]=p0+..+pk-1,k=1..KI(m)是符号m在符号集中的索引Low=0;High=1;range=High–Low;for(n=0;n<N;n++)//有N个符号需要编码{High=Low+C[I(mn)+1]*range;Low=Low+C[I(mn)]*range;range=High–Low;}寻找一个值v，使得Low<=v且v+d<=High且用二进制表示时v的有效位数最少。其中d是v的最低有效位表示的值。例如v为8位时d就是1/256算数编码的解码算法pi是第i个符号的概率，i=0..K-1C[0]=0,C[k]=p0+..+pk-1,k=1..K{b0,b1,…}是待解码bit串D[i]=C[i];//动态区间For(n=0;n<N;n++)//已知有N个符号需要解码{

读入码流，直到[v,v+d)落入某个区间[D[k],D[k+1])

解码得到符号集中索引为k的符号

range=D[k+1]–D[k];D[0]=D[k];D[i]=D[0]+C[i]*range;}其中d是v的最低有效位表示的值。算数编码的终止码流的终止因为算术编码器输出的比特串是作为一个很长的码流的一部分，为了不受后续bit的影响，必须要求low<=vandv+d<=high解码过程的终止已知要解码的符号的个数在符号集中增加结束符号EOB算数编码的区间放大浮点数的精度是有限的，当待编码的符号串很长时，会出现range过小的情况解决的方法是每编码一个符号都对区间进行放大解码过程也进行同样的放大，以保证编解码所得的区间一致算数编码的整数实现浮点数运算复杂，为了降低复杂度，发明了用定点运算实现的算术编码器和解码器定点的算术编码器和解码器一定包含区间放大算数编码举例符号集{A,B,C}，概率{0.8,0.1,0.1}，分割{0,0.8,0.9,1}符号串AAAAAAAABC符号十进制low十进制high二进制low二进制high输出bitA00.801100110011001100A00.6401010001111010111A00.51201000001100010010A00.409600110100011011011A00.3276800101001111100010A00.26214400100001100011011A00.209715200011010110101111A00.1677721600010101011110011B0.1342177280.15099499400100010010111000010011010100111C0150994994001001100011100100100110101001110010011001基于上下文的熵编码考虑了符号的条件概率，即根据已经出现的符号调整下一个符号出现的概率基于上下文的熵编码可以有效的提高编码效率，具体提高多少和符号的相关性有关基于上下文的熵编码可以和huffman、指数哥伦布、算术编码等结合使用自适应熵编码在事先不知道符号的概率分布的情况下，或者不愿意使用固定的码表和概率表的时候，可以使用自适应熵编码技术自适应熵编码就是一边编码一边统计，根据统计结果动态生成概率表和变长码表自适应熵编码可以和huffmann、指数哥伦布、算术编码等结合自适应熵编码和基于上下文的熵编