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