媒体信号编码第4章.ppt

单击此处编辑母版标题样式,第,4,章熵保持编码,第,4,章熵保持编码,4.1,Huffman,编码,4.2,游程编码,4.3,Golomb,编码与通用变长码,4.4,算术编码,4.5,字典码,4.1,Huffman,编码,4.1.1,Huffman,码的构造,1.,最佳码和最佳编码定理,对于某一信源和某一码符号集来说，若有一个唯一可译码，其平均长度小于所有其它唯一可译码的平均长度，则该码称为紧致码，或称最佳码。变字长最佳编码定理：,在变字长编码中，对于概率大的信源符号编以短字长的码，对于概率小的符号编以长字长的码；如果码字长度严格按照所对应符号出现概率大小逆顺序排列，则平均码字长度一定小于其他任何符号顺序排列方法。,证明：设最佳排列方式的码字平均长度为，则其中,P,(,a,i,),为信源符号,a,i,的出现概率，,n,i,为给符号,a,i,编成的码字的长度，而,P,(,a,l,),P,(,a,s,),n,l,n,s,(,l,，,s,=1,2,m,),。如将,a,l,的码字与,a,s,的码字互换，其余码字不变，经过这样的互换以后，平均码字长度变为，则 应为加上两码字互换后与互换前的平均长度之差，即 因为,n,s,n,l,，,P,(,a,l,),P,(,a,s,),，所以。这就是说，是最短的。证毕。,2.,二元,Huffman,码编码步骤,(1),将信源消息符号按其出现的概率大小降序排列；,(2),取两个概率最小的符号分别配以,0,和,1,两个码元，并将这两个概率相加作为一个新符号的概率，与未分配的符号重新排队；,(3),对重排后的两个概率最小符号重复步骤,(2),的过程。,(4),不断继续上述过程，直到最后两个符号配以,0,和,1,为止。,(5),从最后一级开始，向前返回得到各个信源符号所对应的码元序列，即相应的码字。,图,4-1,霍夫曼编码示例,Huffman,编码码字本身和码长序列不是唯一的，但是平均码长是唯一的,。造成,Huffman,编码不唯一的原因主要有两个：每次对信源缩减时，赋予信源最后两个概率最小的符号，因为,0,和,1,可以是任意的，所以可以得到不同的编码但不会影响码字的长度；对信源进行缩减时，两个概率最小的符号合并后的概率与其他多个信源符号的概率相同时，这几者在缩减信源中进行概率排序时位置次序可以任意，因此会得到不同的,Huffman,码。此时，会影响码字的长度，一般将合并的概率放在上面，这样可获得较小的码方差。,由表,4-1,和表,4-2,可以看到，对同一个信源，由于信源符号缩减时排序的不同，造成了不同的码长。这两种码的平均码长分别为可见，虽然两种方法的,Huffman,码的码长不同，但平均码长还是一样的，因而编码效率也相同。在这种情况下，这两种码的质量可以根据码方差来衡量。,码方差越小，说明越接近等长码，因而质量越好。,码方差定义为根据式（,4-1,），可以计算表,4-1,和表,4-2,的码方差分别为,1.36,和,0.16,。因而编码方法二得到的码要优于编码方法一得到的码。由此得出，在,Huffman,编码过程中，为得到码方差最小的码，当重新排列缩减信源的概率分布时，应使合并的概率和尽量处于最高的位置，这样可使合并的信源符号重复编码次数减少，使得码的方差变小。,3.,r,元,Huffman,码,上面讨论的是二元,Huffman,码，它的编码方法同样可以推广到,r,元编码中来。不同的只是“合,2,为,1”,变为“合,r,为,1”,，即每次把,r,个概率最小的符号合并成一个新的信源符号，并分别用,0,、,1,、,、,r,1,等码元表示。为了充分利用短码，使,Huffman,码的平均码长为最短，,必须使最后一步的缩减信源有,r,个信源符号。,因此，对于,r,元编码，信源,X,的符号个数,q,必须满足,q,=(,r,1),+,r,(4-2),其中,表示缩减的次数，,r,1,为每次缩减所减少的信源符号个数。,对于二元码，信源,X,的信源符号个数,q,必须满足：,q,=,q,+2,因此，,q,为任意正整数时一定能找到一个,q,使式,q,=(,r,1),q,+,r,满足。而对于,r,元码，,q,为任意正整数时不一定能找到一个整数,q,使式,q,=(,r,1),q,+,r,满足。若,q,不满足式,q,=(,r,1),q,+,r时，则用虚设符号方法，增补一些概率为零的信源符号，即添加一些信源符号：,s,q,+1,s,q,+2,s,q,+,t,，并使它们对应的概率为零，即,p,q,+1,=,p,q,+2,=,p,q,+,t,=0,。此时，使得,q,+,t,满足式,q,+,t,=(,r,1),q,+,r,。另外，由于添设的信源符号的概率为,0,，因此对实际的,Huffman,编码过程没有影响。这样得到的,r,元,Huffman,码一定是紧致码。,【,例,4-3】,信源,X,有,6,种符号，输出概率为,0.32,、,0.22,、,0.18,、,0.16,、,0.08,和,0.04,，试用三元,Huffman,码编码该信源解,】,在本例中，,r,=3,，若取,q,=6,，则不能找到满足,q,=(,r,1),q,+,r,的整数,q,。因此必须采用虚设符号方法，添设,1,个概率为,0,的符号，使得,q,=7,，,q,=2,，从而满足式,q,=(,r,1),q,+,r,。,图,4-2,表,4-3,中三元,Huffman,码的码树,4.1.2 Huffman,在实际编码中的应用,在实际的语音图像压缩编码应用中，输入符号数一般还是非常多的。,JPEG,标准直流系数的理论动态范围在,-1024,1023,之间，而差分值,DIFF,的理论动态范围达到,-2047,2047,。码表需要,2,12,-1=4095,项。为此，,JPEG,采用将码字截断为“前缀码,(SSSS)+,尾码”的方法，对码表进行了简化。前缀码用来指明尾码的有效位数,(,设为,B,位,),，用标准的,Huffman,编码；尾码则直接用,B,位自然二进制码。当前缀码给定后，它为定长码。对于,8,位量化的图像，,SSSS,的范围为,0,11,，故其码表只需,12,项，如表,4-4,所示。根据,DIFF,的值由表,4-4,查出其前缀码字和尾码的位数,B,后，则可以按式,(4-3),得到,B,位尾码的码字。,按此规则，当,DIFF,非负时，尾码的最高位是“,1”,；而当,DIFF,为负数时，尾码的最高位应为“,0”,。解码时可据此来判断,DIFF的正负。当然，采用这种截断,Huffman,码的编码效率会比采用标准,Huffman,码的编码效率稍微差一点。,(4-3),表,4-4,JPEG,基本系统中,DC,系数的差分值的典型,Huffman,编码表,【,例,4-4】,对于静止图像的色度编码，设相邻两块的,DC,系数的差值,DIFF,为,37,或,-37,请给出对应的截断,Huffman,编码。,【,解,】,编码过程如下：当,DIFF=37,时,根据表,4-4,可知,37,在,32,63,范围内，因此色度码字的前缀码字为,111110,，尾码位数,B,为,6,；又根据式,(4-3),，可知,37,对应的,6,位二进制原码为,100101,；因此,DIFF=37,时对应的截断,Huffman,编码码字为,111110100101,。同理可得，当,DIFF=-37,时，前缀码字为,111110,，尾码位数,B,为,6,；,37,对应的,6,位二进制反码为,011010,；因此,DIFF,为,37,时对应的截断,Huffman,编码码字为,11111001 1010,。解码时，由前缀码,111110,可知尾码有,6,位，然后取,6,比特数据得到,100101,或,011010,。若为,100101,，最高位是,1,，立即可知,DIFF=(100101),2,=37,；若为,011010,，最高位是,0,，可知,DIFF=-(011010),2,=-(100101),2,=-37,。,4.2,游程编码,游程长度编码，简称游程编码,(Run-Length Coding,RLC),的基本思想是,将具有相同数值,(,或字符等,),的、连续出现的信源符号构成的符号串用其数值,(,或字符等,),及串的长度表示。以图像编码为例，灰度值相同的相邻像素的连续长度,(,像素数目,),称为连续的游程，又称游程长度，简称游程。如果给出了形成串的像素的灰度值及串长度，就能无失真地恢复出原来的数据流，如图,4-3,所示。,游程编码往往与其他编码方法结合使用。例如，在,MPEG,视频编码中，对图像块作完离散余弦变换和量化后，经,Z,字形扫描将“,0”,系数组织成“,0”,游程，作游程编码，再与非“,0”,系数结合组成二维事件,(RUN,，,Level),进行,Huffman,编码，其中，,RUN,代表“,0”,游程的长度，,Level,代表在该“,0”,游程后面的非“,0”,系数的数值。显然，平均游程长度越长，游程编码的效率越高。当平均游程长度很短时，游程编码的效率非常低。在图像的游程编码中，它只适合灰度等级比较少的图像，例如它特别适合二值图像。,4.2.1,二值图像的游程编码,二值图像是指仅有黑和白两个亮度值的图像,(,国际建议规定用“,1”,代表黑，“,0”,代表白,),。二值图像的应用非常普遍，如经扫描得到的气象图、工程图、地图及由文字组成的文件图像,(,黑白报纸、书籍等,),。二值图像是灰度图像的一个特例，它最经典的通信方式是传真。因此，二值图像压缩也往往指对数字传真机扫描文件的编码。此外，二值图像压缩还大量用于图文的光盘存储，而且传真本身也已经从图形、文字等二值图像发展到连续色调图片的传输。,在二值图像的游程编码中，游程符号集合,X=,黑，白,，每一扫描行均由交替出现的白像素游程,(,连续出现的白像素,),和黑像素游程,(,连续出现的黑像素,),组成。对不同长度的白游程和黑游程按其出现的概率的不同分别配以不同长度的码字，就是二值图像的,RLC,。由于,RLC,利用了多个像素间的相关性，故可得到较低的码率下限，每像素平均码长满足：其中,P,W,和,P,B,分别为白像素和黑像素出现的概率,l,W,和,l,B,分别为白游程长和黑游程长的平均像素数,(,平均长度,),，,h,WB,则为每个像素的熵值。,(4-4),在理想情况下，先分别统计出图像白游程长为,i,的概率,P,i,W,和黑游程长为,i,的概率,P,i,B,，然后根据,Huffman,编码原则按游程,(RL),出现概率分配码字，即可使平均码长接近,h,WB,。但在实际应用中，,RL,在行间、页间出现的概率都不相同，且为求得该概率，需要存储数据并做统计计算，难以实时实现。为此，,CCITT,的,T.4,建议推荐以,8,幅标准传真样张为统计样本，统计各种RL,出现的概率并以此编出,Huffman,表，称之为改进型,Huffman,编码,(MHC),，作为文件传真三类机一维编码的国际标准。实际编码过程中首先数,RL,长度、然后查表，可以实现实时编码。,MHC,码的平均编码效率可达,86.9%,，差错灵敏度低，它也基本上适合中文文件传真的样张。,为保证传真文件具有足够的清晰度，,CCITT,规定,ISO,的,A4,幅面,(210 mm297 mm),为可接受的输入文件的最小尺寸，对它的扫描分辨率应达到,1188(,或,2376),条扫描线，每条线标准采样,1728,点。根据统计，实际,RL,多在,0,63,之间，故,MHC,码表分为结尾码和组合基干码两种，如表,4-5,所示。具体编码规则如下：,RL=0,63,时，用相应的结尾码编码；,RL=64,1728,时，用“组合基干码,+,结尾码”编码。行结束时添加行同步码,EOL,。例如,RL(,黑,)=128,，编码为“,000011001000(,组合基干码,)+0000110111(,结尾码,)”,。,表,4-5,传真文件编码的,MH,码表,4.2.2,JPEG,图像量化系数的编码,JPEG(Joint Photographic Experts Group),是指由,ISO,和,IEC,两个组织机构联合组成的专家组，负责制定静态的数字图像数据压缩编码标准，其制定的标准也称,JPEG,标准。在实际的,JPEG,图像压缩编码标准中，图像量化系数的熵编码是结合了游程编码和,Huffman,编码。,JPEG,采用,88,的图像块，经离散余弦变换后得到,64,个系数。第,1,个系数称为直流系数，后,63,个系数称为交流系数，如图,4-4(a),和,(b),所示。,图,4-4,JPEG,图像系数二维到一维的过程,首先，利用,Z,形扫描将二维系数矩阵转换成一维系数矩阵，,Z,扫描过程如图,4-4(b),所示。扫描完成后二维系数矩阵与一维系数数组,ZZ(k),的对应关系如图,4-4(c),所示。,ZZ(0),为直流系数，对它的编码方法已经在,4.1.2,节中进行过介绍。其次，非零交流系数按“,NNNN/SSSS+,尾码”的编码方式编码，其中,4,位“,NNNN”,为当前非零值相对前一个非零交流系数的零游程计数，表示,ZRL=0,15,；而,4,位“,SSSS”+“,尾码”则用于编码当前非零值，其含义与直流系数编码类似，“,SSSS”,代表尾码的比特数。但这里将“,NNNN/SSSS”,组合为一个新的前缀码，然后用,Huffman,编码方法编码，其码表如表,4-6,所示。若,ZRL15,，则用“,NNNN/SSSS=1111/0000”,编码，再对,ZRL=ZRL-16,继续编码。若最后一个“零游程,/,非零值”只有零,游程，则直接发送块结束码字,EOB,，否则不需要发送,EOB,。最后，具体的交流系数编码步骤如下：根据,ZZ(k),的幅度范围,由表,4-6,查出尾码的位数,SSSS=B,。,表,4-6,交流系数的尾码编码比特数,计数非零交流系数前的零游程值,NNNN=ZRL,，由,NNNN/SSSS,从表,4-7,和表,4-8,中查出前缀码字。按式,(4-3),直接写出,B,位尾码的码字。,【,例,4-5】,某图像块的残差数据如下所示，,PRED=8,，,JPEG,编码过程如下：,(1)Z,形扫描：,ZZ(0)=12,，,ZZ(1)=5,，,ZZ(2)=-2,，,ZZ(4)=2,，,ZZ(8)=1,，,ZZ(31)=-1,。,(2)DC,系数编码：,DIFF=ZZ0)-PRED=12-8=4,。由表,4-4,知，,B=3,，前缀为,100,，尾码,DIF=100,，故编码为,101100,。,(3)AC,系数编码：第,1,个非零值,ZZ(1),与,ZZ(0),之间的,ZRL=0,，故,NNNN=0,；,ZZ(1)=5,，故,SSSS=3,；,NNNN/SSSS=0/3,。由表,4-7,知前缀码字为,100,，后缀码字为,101,，故,ZZ(1),的编码为,100101,。,同理，第,2,个非零值,ZZ(2),的,NNNN/SSSS=0/2,，故前缀码字为,01,，,2,的反码为,01,，因此编码为,0101,。同理，可得到,ZZ(4),的编码为“,11011,，,10”,，,ZZ(8),的编码为“,111010,，,1”,。,表,4-7,亮度交流系数码表,表,4-8,色度交流系数码表,ZZ(31)=-1,：由于,NNNN=31,8,1=2215,，故先编码,ZRL=16,，码字为“,11111111001”,；此后有,NNNN=22,16=6,，此时的,SSSS=1,，故,NNNN/SSSS=6/1,，前缀的编码为“,1111011”,，,1,的反码为,0,，后缀的编码为,0,，从而,ZZ(31),的编码为“,11111111001+1111011+0”,。此后无非零值，直接用,EOB,结束本块数据，编码为“,1010”,。原始码流需要,888=512 bit,，压缩后码流一共有,49 bit,，压缩比为,51249=10.451,。,4.3,Golomb,编码与通用变长码,4.3.1,一元码,一元码定义为非负整数,n,的一元码为,n-1,个,1,后跟,1,个,0,；或者为,n,1,个,0,后跟,1,个,1,。按此定义，整数,n,的一元码长度是,n,比特，如表,4-9,所示。,4.3.2,Golomb,编码,S.W.Golomb,在,1966,年提出一种编码方法，可以使服从几何分布的正整数数据流的平均码长最短，该方法无需使用,Huffman,编码算法，而是直接给出最佳变长码。设数据流中整数,n,出现的概率为,p,(,n,)=(1,p,),n,1,p,0,p,1 (4-5),求出满足下式的,b,值,(,一定存在,)(1,p,),b,+(1,p,),b,+1,1(1,p,),b,-1,+(1,p,),b,(4-6),得到,b,值后，就可以按“前缀码,+,尾码”的格式进行整数,n,的,Golomb,编码。具体步骤如下：,(1),如果,b,2,k,，前缀码是,q,+1,位一元码字，为下取整函数；尾码是对的余数,r,=,n,1,qb,的二进制编码，,r,0,1,b,1,，余数前个用比特编码，后面用 比特编码，且最高位为,1,。,(2),如果,b,=2,k,，前缀码产生规则同,b,2,k,时相同；尾码则直接用,n,的二进制表示的最低,k,位表示。这类特殊的,Golomb,码又叫做,G,(,k,),。,【,例,4-6】,给出,b,=3,，,4,，,5,时的,Golomb,码。,【,解,】,如果取,b,=3,，则可能的余数为,0,、,1,、,2,，第,1,个余数用,1,比特编码，后面余数用,2,比特编码，高位为,1,保持尾码的前缀性，因此余数与尾码的对应关系为,0,0,、,1 10,、,2 11,；而前缀码根据编码规则，对于,n,=1,2,，其前缀码的位数分别为,1,1,1,2,2,2,，,位。若取表,4-9,右边一列的一元码字，则分别为,1,1,1,01,01,01,，,。,表,4-10,b,=3,4,5,和,n,10,的,Golomb,码字,4.3.3,指数,Golomb,码与通用变长码,相同前缀的,Golomb,码的信息表达能力主要在于尾码。可是从表,4-10,可见，其尾码长度随,n,增长缓慢，因为它主要取决于,b,。而所谓指数,Golomb,码，可以让同一个前缀下的,Golomb,码字数呈指数级增长。本质上，指数,Golomb,码就是以,G,(0),码为前缀，再加上,q,+,m,位尾码,(,或称后缀,),，尾码事实上就,q,+,m,位二进制码。,q,就是,G,(0),码中“,0”,的个数,(,均取“,001”,形式的一元码,),，而,m,0,则为指数,Golomb,的阶数。此时，尾码增加,1,位，即m,增加,1,，码字数就可以翻一番。,指数,Golomb,码已经应用在视频编码中，如在我国制定的,AVS(,先进音视频编码系统,),标准中，就已经采用,m,阶指数,Golomb,码，如表,4-11,所示。指数,Golomb,码的优势在于硬件复杂度较低，可以根据闭合公式解析码字，无需查表；还可以根据整数,n,的分布灵活选取或自适应改变阶数,m,，以达到较好的压缩性能。对于指数哥伦布编码，当,m,和,q,确定后，其编码正整数,n,的范围为,2,q,+,m,2,m,2,q,+,m,+1,2,m,1,。,表,4-11,m,阶指数,Golomb,码表,由于,0,阶指数,Golomb,码的前缀码始终比其尾码多,1,位，如表,4-11,阶数为,0,时所示，因此可以把,q,位尾码嵌入到,q,+1,位前缀码中。这就是,ITU H.26L(H.264,建议前身,),甚低码率视频压缩算法采用的通用变长码,(UVLC),，如表,4-12,所示。可以看到，,UVLC,实质上就是一种前后缀交织的,0,阶指数,Golomb,码。,UVLC,码的优点在于：同等码长的,UVLC,码它不仅“异字头”，也是“异字尾”。因此，只要码长已知，如果正向译码出错，还可以反向译码。这样降低了码字的误码敏感性。,表,4-12,UVLC,码的结构,【,例,4-7】,设有一信源的消息符号集为,0,，,1,，,2,，,3,，,4,，,5,，其出现概率对称且单调下降，如图,4-5,所示。假设正负符号合在一起出现的概率为,0.38,，,0.32,，,0.16,，,0.08,，,0.04,，,0.02,。求此信息源的,UVLC,码和,Huffman,码。,图,4-5,对称单调下降概率分布,【,解,】,可以按照表,4-12,把这种符号映射到表,4-13,所示的,UVLC,码。采用,UVLC,编码的平均码字长度为,10.38+30.32+5(0.16+0.08)+7(0.04+0.02)=2.96 bit,表,4-13,此信源的,UVLC,码,该信源也可以采用,Huffman,编码，码表如,4-14,所示。采用,Huffman,编码的平均码字长度为,10.38+30.32+40.16+50.08+50.02+60.02+70.02=2.74 bit,表,4-14,此信源的,Huffman,码,按照符号的出现概率计算出这种信源熵值为比较起来，,Huffman,码平均码长,(2.74),更接近于信源熵值，,UVLC,码,(2.96),比,Huffman,码稍差，但,UVLC,码的编解码的复杂度比,Huffman,码低很多，实现更容易，因此在最新的视频编码标准,H.264,中，,UVLC,码也是熵编码的选择方案之一。,4.4,算术编码,4.4.1,算术编码的起源,:,香农编码,早在,1948,年，香农就提出将信源符号依其概率降序排序，用符号序列累计概率的二进制表示作为对信源的编码，并从理论上证明了它的优越性。香农编码方法归结如下：设信源符号集共有,L,个符号，按符号出现概率大小进行排列，则,P,(,x,1,),P,(,x,2,),P,(,x,L,),计算概率的累计分布,每一符号编码的码字长,n,i,，它是符合以下不等式的最小整数。,编码的方法：把,C,i,展开为二进小数，按照式,(4-8),取,n,i,位，当第,n,i,+1,位是,1,则进位，当第,n,i,+1,位是,0,则舍去，这个,n,i,位二进码就是符号,x,i,的编码,.,(4-8),(4-7),【,例,4-8】,已知四个符号的信源,x,1,，,x,2,，x,3,，,x,4,;,p,(,x,1,)=0.4,，,p,(,x,2,)=0.3,，,p,(,x,3,)=0.2,，,p,(,x,4,)=0.1,。试计算该信源的香农码。,【,解,】,根据香农码的计算步骤，可算得,C,1,=0,，,C,2,=0.4,，,C,3,=0.7,，,C,4,=0.9,，按前缀条件确定,n,1,=2,，,n,2,=2,，,n,3,=3,，,n,4,=4,。编成的香农码为,c,1,=00,，,c,2,=10,，,c,3,=110,，,c,4,=1111,。前述的,Huffman,编码比香农编码更接近于熵值，故现在一般都采用,Huffman,码。,4.4.2,算术编码的基本原理,设信源在第,i,时刻发出的符号为,x,i,，把信源从开始到第,n,时刻发出的符号序列记为,S,n,，则对于,Markov,信源，可以用条件概率,p,(,x,|,S,),来描述信源输出一个新的符号的概率，符号序列,S,n,的发生概率为,p,(,S,n,)=,P,(,x,1,),P,(,x,2,x,1,),P,(,x,n,x,1,x,n,1,)(4-10),在第,n,时刻，符号序列,S,n,由,n,个符号构成，由可能的各种符号序列构成概率之和，它满足：,(4-9),(4-11),例如，图,4-6,中给出了二元符号集合,0,，,1,在最初时刻生长出的符号序列,S,1,，,S,2,，,S,3及其可能构成的概率，假设序列中符号的出现概率是独立无关的，设,p,(0),p,(1),，,p,(0)=1/3,，,p,(1)=2/3,。,S1,就只有一个符号为,1,或,0,，其概率为,p,(1),或,p,(0),，把长度为,1,的间隔按,12,的比例分割，就是序列,S,1,的各种构成的概率。,S,2,有,4,种构成为,11,，,10,，,01,，,00,，其中,11,，,10,是由,S,1,为,1,时发展而成，在符号出现概率独立无关假定下,p,(,x,n,|,s,n,1,)=,p,(,x,n,),，所以,p,(11)=,p,(1),p,(1),，,p,(10)=,p,(1),p,(0),只要把,S,1,分割为,1,的那一段,p,(1),再按,12,的比例分割，就得到,S,2,为,11,和,10,时的概率,p,(11),和,p,(10),。同样把,S,1,为,0,的一段,P,(0),再按,12,的比例分割，就得到,S,2,为,01,和,00,时的概率,p,(01),和,p,(00),，显然,p,(11)+,p,(10)+,p,(01)+,p,(00)=1,，符合式,(4-11),，用此方法可以一步一步递推出,n,个符号序列,S,n,的各种可能构成的概率,p,(,S,n,),。,图,4-6,符号序列,S,n,出现的概率和算术编码,编码并不按单个符号编码，而按符号序列的发展对序列进行整体编码。借鉴香农用,n,个符号序列,S,n,出现的概率的累计分布,C,(,S,n,),，在区间,C,(,S,n,),，,C,(,S,n,)+,A,(,S,n,),选取一点，用其二进制小数表示编码，并把,C,(,S,n,),和,A,(,S,n,),的计算转换成递归运算。,A,(,S,n,),称为符号序列,S,n,编码可用空间或值域,(Range),，它的大小就是,p,(,S,n,),，即符号序列,S,n,的出现概率。设在上一时刻信息的符号序列为,S,，这一时刻信源发出符号,x,，序列发展成为新的序列,S,x,。递归计算序列,Sx,的累计分布函数,C,(,Sx,),和编码可用空间,A,(,Sx,),的递推公式如下：,(1),累计分布函数的递推：,C,(,Sx,)=,C,(,S,)+,A,(,S,),P,(,x,)(4-12),图,4-6,中，如果,x,=1,，有如果,x,=0,，有,C,(,S,0)=,C,(,S,)+,P,(0),A,(,S,)=,C,(,S,),(2),编码可用空间的递推：,A,(,Sx,)=,p,(,S,x,)=,p,(,x,),A,(,S,)(4-13),图,4-6,中，如果,x,=1,，有,如果,x,=0,，有,式,(4-13),中，,p,(,x,),为符号出现的概率，,P,(,x,),为符号,x,的累积概率，如式,(4-7),所示。对于图,4-6,，有初始条件为,C,(,)=0,，,A,(,)=1,和,P,(,)=0,，,p,(,)=1,。,可见，算术编码在传输任何符号,x,之前，信息的完整范围是,C,(,),，,C,(,)+,A,(,)=,0,，,1),。当处理符号,x,后区间宽度就依据,x,的出现概率,p,(,x,),变窄，大概率符号比小概率符号使区间变窄的范围要小。然后在区间,C,(,S,),，,C,(,S,)+,A,(,S,),找一代表点，对其值进行编码。符号序列越长，相应的子区间就越窄，编码表示该子区间所需的比特数也就越多。另外从上述迭代公式可知，符号串每一步新扩展的码字,C,(,Sx,),都是由原符号串的码字,C,(,S,),和新区间宽度,A,(,Sx,),的算术相加而得的，“算术码”一词由此得来。,【,例,4-9】,信源符号集,S,=,a,，,b,，,c,，,d,，,e,，,!,，其中前,5,个符号为实际信源符号，最后一个符号“！”用来表示编码结束。各概率和初始区间范围如表,4-15,所示，试编码字符串,dead,。,表,4-15,信源符号及其概率分布,【,解,】,编码过程如下：“,d,”,，,C,(,Sd,)=,C,(,)+,P,(,d,),A,(,)=0.4,A,(,Sd,)=,p,(,d,),A,(,)=0.3,区间,0.4,，,0.7),“,e,”,，,C,(,Se,)=,C,(,S,)+,P,(,e,)A,(,S,)=0.4+0.70.3=0.61,A,(,Se,)=,p,(,e,),A,(,S,)=0.20.3=0.06,区间,0.61,，,0.67),“,a,”,，,C,(,Sa,)=,C,(,S,)+,P,(,a,),A,(,S,)=0.61,A,(,Sa,)=,p,(,a,),A,(,S,)=0.20.06=0.012,区间,0.61,，,0.622),“,d,”,，,C,(,Sd,)=,C,(,S,)+,P,(,d,),A,(,S,)=0.61+0.40.012=0.6148,A,(,Sd,)=,p,(,d,),A,(,S,)=0.30.012=0.0036,区间,0.6148,0.6184),编码符号“,!”,后的区间为,0.61804,，,0.6184),，区间宽度,A,(,S,)=0.000 36,。解码器无需知道最终区间的两个端点值，只知道区间内的一个值就够了。比如知道值,0.6182,，解码端的过程如下：由于,0.6182,0.4,，,0.7),，故知道第,1,个符号为,d,；则下一个符号的区间范围应该为：,a,0.4,，,0.46),，,b,0.46,，,0.49),，,c,0.49,，,0.52),，,d,0.52,，,0.61),，,e,0.61,，,0.67),，,!,0.67,，,0.7),。由于,0.6182,0.61,，,0.67),，故知道第,2,个符号为,e,；以此类推，可以解码出符号,a,，,d,，！。当解码出！符号时，解码完成。,4.5,字典码,4.5.1,LZ,码的基本概念,字典编码起源于,20,世纪,70,年代末。,1977,年和,1978,年,以色列两位博士,J.Ziv,和,A.Lempel,陆续提出了两种不同但又有联系的关于文字数据压缩的论文，该文中的码习惯上简称为,LZ,码。,1984,年，,T.A.Welch,博士对,LZ78,算法加以改进，提出了所谓的,LZW,算法。至今，在处理文字数据压缩的问题时，,LZW,算法一直是被广泛使用。,设想我们要用计算机来储存以下一段,9,个字符的文字数据，即,ABBBABAAB,。如果每个字符都用,8,比特的,ASCII,码来储存，则需要,72,比特的内存。然而，如果该计算机拥有一个如表,4-19,中所示的字典,1,，借助该字典的信息，则仅需,10,比特的内存，亦即,AB,、,BB,、,AB,、,A,及,AB,等文字数据分别会先被编码成,10,、,11,、,10,、,00,及,10,等十个比特，然后再存入内存，其省下的储存空间高达,86%,。之后，如果一次以两个比特的方式来读取数据，然后通过同样的字典进行译码，则内存所储存的数据,1011100010,很快地就会被解读出原来的文字数据为,ABBBABAAB,。,表,4-19,计 算 机 字 典,通过上面的例子可以看到，与,Huffman,码正好形成鲜明对比的是：,LZ,码及后来的改进算法都是将变长的输入符号串映射成定长,(,或长度可预测,),的码字。,LZ,码按照几乎相等的出现概率编排输入符号串，从而使频繁出现的符号的串将比不常出现符号的串包含更多的符号。例如在一张将英文字母和符号串编码成,12,位码字的压缩字符串表中,(,如表,4-20,所示,),，不常用的字母如,Z,，独占一个,12,位码字；而常用的符号如空格,(,表,4-20,中用“空”表示,),和零，则以不同长度的长串表示,(,实用中字符串长度可大于,30),。如果输入一个长串，就会被替换成一个,12,位码字，此时压缩比自然很高。实际上，表,4-20,也就是,LZ,码使用的字典，所以,LZ,码也是基于字典的压缩编码算法。,表,4-20,一种,LZ,编码的字典,4.5.2,LZW,算法,由,T.A.Welch,在,1984,年提出的,LZW,算法，是,LZ,系列码中应用最广、变形最多的,LZ,码。,LZ,码系列算法的共同点是：分解输入流，使其成为长度各异的“短语”，并把它们存入“短语字典”，并给每个“短语”赋予一个码字,(,通常就是短语的字典索引,),。只要短语的码字长度小于短语的长度，就达到了压缩的目的。,LZW,编码算法独特的地方是先建立初始字典，再将输入流分解为短语词条，这个短语若不在初始字典内，就将其存入字典，这些新词条和初始字典共同构成编码器的字典。初始字典由信源符号集构成，每个符号是一个词条。比如在英文文本的压缩中，可以将扩展的,ASCII,码作为初始字典，使其成为字典的前,256,项，这样的初始字典足以应付普通的英文文本压缩。,LZW,算法将输入字符串映射成定长,(,通常为,12,位,),的码字。,LZW,码表,(,字典,),具有所谓的“前缀性”,表中任何一个字符串的前缀字符串也在表中。这也就是说，如果由某个字符串,S,和某个单字符,c,所组成的字符串,Sc,在表中，则,S,也在表中，其中,c,叫前缀串,S,的扩展字符。对码表作出这样的说明后，编码前可以将其初始化以包含所有的单字符。在压缩过程中，码表里面存放着编码器在压缩过程中已经遇到的字符串，它动态反映消息的统计特性。,LZW,使用的是“贪婪”分析算法，即依次检查各个字符，直到碰到码表中没有的字符串或者扫描完全部字符。除初始化码表外，其他码表项也是通过这种方法加入进码表中的。,LZW,编码算法流程如图,4-9,所示。,图,4-9,LZW,编码算法流程,【,例,4-12】,试对一个最简单的,2,字符串“,ABBBABAAB”,作,LZW,编码。,【,解,】,根据图,4-9,给出的,LZW,编码算法流程，可以得到如下的编码步骤：步骤,0,：将,A,及,B,字符存入字典里，也就是,A,及,B,字符之后分别会被编码成索引值,1,及,2,；并读入第一字符,A,，前缀串,S,=A,。步骤,1,：读入下一个字符,c,=B,，串,Sc,=AB,不在码表中，输出串,S,=A,在字典里的索引值,1,；并将新的字符串,AB,存入字典里，其索引值等于,3,；最后置,S,=B,。步骤,2,：读入下一个字符,c,=B,，串,Sc,=BB,不在码表中，输出串,S,=B,在字典里的索引值,2,；并将新的字符串,BB,存入字典里，其索引值等于,4,；最后置,S,=B,。,步骤,3,：读入下一个字符,c,=B,，串,Sc,=BB,已经在码表中，置,S,=BB,。步骤,4,：读入下一个字符,c,=A,，串,Sc,=BBA,不在码表中，输出串,S,=BB,在字典里的索引值,4,；并将新的字符串,BBA,存入字典里，其索引值等于,5,；最后置,S,=A,。步骤,5,：读入下一个字符,c,=B,，串,Sc,=AB,已经在码表中，置,S,=AB,。步骤,6,：读入下一个字符,c,=A,，串,Sc,=ABA,不在码表中，输出串,S,=AB,在字典里的索引值,3,；并将新的字符串,ABA,存入字典里，其索引值等于,6,；最后置,S,=A,。步骤,7,：读入下一个字符,c,=A,，串,Sc,=AA,不在码表中，输出串,S,=A,在字典里的索引值,1,；并将新的字符串,AA,存入字典里，其索引值等于,7,；最后置,S,=A,。,步骤,8,：读入下一个字符,c,=B,，串,Sc,=AB,已经在码表中，置,S,=AB,。步骤,9,：读入下一个字符,c,=,f,，输入已经穷尽，输出串,S,=AB,在字典里的索引值,3,，编码结束。该过程如表,4-21,所示。,表,4-21,字符串“,ABBBABAAB”,的,LZW,编码过程,LZW,的解码过程如下：步骤,1,：首先建立初始化码表,(,字典,),，它由信源的全部符号集构成,(,编码器和解码器的初始化码表要完全一样,),。步骤,2,：依序解码接收到的码字,(,字典索引值,),，如果可以根据目前字典里的内容进行译码，则译码出相对应的词条,I,。同时将,Ic,存入解码字典中，此时,c,未知，它是下一个从字典中读取的词条的首