《推荐算术编码》由会员分享，可在线阅读，更多相关《推荐算术编码（20页珍藏版）》请在金锄头文库上搜索。
1、1 计算机应用技术计算机应用技术 张志林张志林 算数编码算数编码无失真编码无失真编码算术编码特点非分组码，它是从全序列出发，考虑符号之间的依赖关系。经香农-费诺-埃利斯编码推广而来的，直接对信源符号序列进行编码输出。即时码，信源符号序列对应的累积概率区间是不重叠的。肯定也可以唯一译码。不必预先定义概率模型,自适应模式具有独特的优点;信源符号概率接近时,建议使用算术编码,这种情况下其效率高于Huffman编码(约5%)。JPEG扩展系统采用。2算术编码特点算术编码并不是将单个信源符号映射成一个码字，而是把整个信源表示为实数线上0到1之间的一个区间,其长度等于该序列的概率。在该区间内选择一个代表性
2、的小数，转换为二进制作为实际的编码输出消息序列中的每个元素都要用来压缩这个区间消息序列中元素越多，所得到的区间就越小，当区间变小时，就需要更多的位数来表示这个区间3算术编码的编码过程从信源符号全序列出发，将各信源序列依累积概率分布函数的大小映射到,区间,将,区间分成许多互不重叠的小区间。此时每个符号序列均有一个小区间与之对应，因而可在小区间内取点来代表该符号序列。45算术编码算术编码应用应用（1）采用固定模式符号概率分配如下：采用固定模式符号概率分配如下： 字符字符: a e i o u 概率概率: 0.2 0.3 0.1 0.2 0.2 范围范围:0,0.2) 0.2,0.5) 0.5,0.
3、6)0.6,0.8)0.8,1.0)编码数据串为编码数据串为eai。令令high间隔的高端间隔的高端, low为低端，为低端，range为间隔的长度为间隔的长度, rangelow为编码字符分配的为编码字符分配的间隔低端间隔低端, rangehigh为编码字符分配的间隔高端。为编码字符分配的间隔高端。6算术编码算术编码应用应用（1）初始初始high=1,low=0, range=high-low, 一个字符编码后新的一个字符编码后新的low和和high按下式计算：按下式计算： low=low+rangerangelow； high=low+rangerangehigh。(1) 在第一个字符在第
4、一个字符e被编码时被编码时, e的的rangelow=0.2, rangehigh=0.5, 因此因此: low=0+10.2=0.2 high=0+10.5=0.5 range=high-low=0.5-0.2=0.3 此时分配给此时分配给e的范围为的范围为0.2, 0.5)7(2)(2)第二个字符第二个字符a编码时使用新生成范使用新生成范围0.2,0.5),0.2,0.5),a的的rangelow=0, rangehigh=0.2, 因此因此: :low=0.2+0.30=0.2 high=0.2+0.30.2=0.26 range=0.06 范范围变成成0.2,0.26)0.2,0.26
5、)8(3)(3)对下一个字符下一个字符i编号号,i的的rangelow=0.5，rangehigh=0.6,range=0.06, 则：low=0.2+0.060.5=0.23 high=0.2+0.060.6=0.236结果：用果：用0.23,0.236)0.23,0.236)表示数据串表示数据串eai,如果解如果解码器知道最器知道最后范后范围是是0.23,0.236),0.23,0.236),它它马上可解得一个字符上可解得一个字符为e, 然后然后依次得到唯一解依次得到唯一解a、i, 最最终得到得到eai91e 0.5ea 0.26 0.2360.80.60.50.20uoieauoieau
6、oieauoiea 0.2 0.2 0.23eai无失真编码10算术编码算术编码应用应用（2）算术编码设定初值high=1.0low=0length=high-low=1.0对符号序列中每一个输入的信源符号进行编码，计算high,low及length的新值high=low+lengthsymbol_high(c)low=low+lengthsymbol_low(c)11算术编码符号定义等号右边的low和length分别为前面已编码符号序列所对应编码区间的下界和区间长度等号左边的low和high分别为输入待编码符号后所对应的当前区间的下界和上界symbol_high(c): 当前输入符号c的上界
7、symbol_low(c):当前输入符号c的下界length: “当前区间”的区间长度，length=high-low1213算数编码过程表示（图）算数编码过程表示（图）算术编码编码过程根据每个符号出现的概率将半开区间0,1)分成四个区域0,0.2) 0.2,0.4) 0.4,0.8) 0.8,1)对输入的第一个符号a1编码symbol_high(a1)=0.2 symbol_low(a1)=0high=0+1.00.2=0.2 low=0+1.00=0输入第一个符号a1后，编码区间由0,1)变为0,0.2)，当前区间长度length=0.2-0=0.2对输入的符号序列a1a2进行编码symb
8、ol_high(a2)=0.4 symbol_low(a2)=0.2high=0+0.20.4=0.08 low=0+0.20.2=0.04输入第二个符号a2后，编码区间由0,0.2)变为0.04,0.08)，当前区间长度length=0.08-0.04=0.0414算术编码编码过程输入第三个符号a3后，对序列a1a2 a3进行编码,编码区间为0.056,0.072)输入第四个符号a3后,对序列a1a2a3a3进行编码,编码区间为0.0624,0.0688)输入第五个符号a4后,对序列a1a2a3a3 a4进行编码,编码区间为0.06752,0.0688)在区间0.06752,0.0688)内
9、的任何数字都可以表示消息a1a2a3a3a4,例0.0675215算术编码编码过程16算术编码译码过程通过查看哪一个信源符号拥有已编码消息所落入的数值范围，找到消息中的第一个信源符号，0.06752在0,0.2)之间，所以第一个符号为a1从编码数值中消去第一个符号a1的影响，即首先减去a1的所在区间的下界值，然后除以a1对应区间的宽度，即(0.06752-0)/0.2=0.3376查表找到该结果0.3376落入哪一个符号对应的数值范围，得到第二个符号a2重复上述过程直至解出整个符号流17算术编码译码过程18算术编码总结算术编码对整个消息只产生一个码字，这个码字是在间隔0,1)中的一个实数，因此译码器在接收到这个实数的所有位之前不能进行译码算术编码是一种对，如果有一位发生错误就会导致错误很敏感的编码方法整个消息译错实际编码是用硬件或计算机软件实现，采用递推公式进行编码。算术编码在性能上有很多的优点，如所需的参数少，无很大的码表，主要针对信源概率未知或非平稳情况。在实际应用中还要考虑计算精度、存储量、近似值中Q的选择等问题，随着这些问题的解决，它正在进入实用阶段，但要扩大应用范围或进一步提高性能，降低造价，还需进一步改进。1920谢谢！谢谢！
