算术编码.ppt

1 计算机应用技术 算数编码无失真编码1 1算术编码特点非分组码，它是从全序列出发，考虑符号之间的依赖关系。经香农-费诺-埃利斯编码推广而来的，直接对信源符号序列进行编码输出。即时码，信源符号序列对应的累积概率区间是不重叠的。肯定也可以唯一译码。不必预先定义概率模型,自适应模式具有独特的优点;信源符号概率接近时,建议使用算术编码,这种情况下其效率高于Huffman编码(约5%)。JPEG扩展系统采用。无失真编码22 2算术编码特点算术编码并不是将单个信源符号映射成一个码字，而是把整个信源表示为实数线上0到1之间的一个区间,其长度等于该序列的概率。在该区间内选择一个代表性的小数，转换为二进制作为实际的编码输出消息序列中的每个元素都要用来压缩这个区间消息序列中元素越多，所得到的区间就越小，当区间变小时，就需要更多的位数来表示这个区间无失真编码33 3算术编码的编码过程 从信源符号全序列出发，将各信源序列依累积概率分布函数的大小映射到,区间,将,区间分成许多互不重叠的小区间。此时每个符号序列均有一个小区间与之对应，因而可在小区间内取点来代表该符号序列。无失真编码44 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)0.6,0.8)0.8,1.0)编码数据串为编码数据串为eai。令令high间隔的高端间隔的高端,low为低端，为低端，range为间隔的长度为间隔的长度,rangelow为编码字符分配的为编码字符分配的间隔低端间隔低端,rangehigh为编码字符分配的间隔高端。为编码字符分配的间隔高端。5 5无失真编码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+10.5=0.5 range=high-low=0.5-0.2=0.3 此时分配给此时分配给e的范围为的范围为0.2,0.5)6 6无失真编码7(2)(2)第二个字符第二个字符a a编码时使用新生成范围编码时使用新生成范围0.2,0.5),0.2,0.5),a a的的rangelow=0,rangehigh=0.2,rangelow=0,rangehigh=0.2,因此因此:low=0.2+0.3low=0.2+0.30=0.20=0.2 high=0.2+0.3 high=0.2+0.30.2=0.260.2=0.26 range=0.06 range=0.06 范围变成范围变成0.2,0.26)0.2,0.26)7 7无失真编码8(3)(3)对下一个字符对下一个字符i i编号编号,i i的的rangelow=0.5rangelow=0.5，rangehigh=0.6,range=0.06,rangehigh=0.6,range=0.06,则：则：low=0.2+0.06low=0.2+0.060.5=0.230.5=0.23 high=0.2+0.06 high=0.2+0.060.6=0.2360.6=0.236结果：用结果：用0.23,0.236)0.23,0.236)表示数据串表示数据串eai,eai,如果解码器知道最后如果解码器知道最后范围是范围是0.23,0.236),0.23,0.236),它马上可解得一个字符为它马上可解得一个字符为e,e,然后依次然后依次得到唯一解得到唯一解a a、i,i,最终得到最终得到eaieai8 8 算术编码过程表示算术编码过程表示91e 0.5ea 0.26 0.2360.80.60.50.20uoieauoieauoieauoiea 0.2 0.2 0.23eai无失真编码9 9无失真编码10算术编码应用（算术编码应用（2）1010无失真编码算术编码设定初值high=1.0low=0length=high-low=1.0对符号序列中每一个输入的信源符号进行编码，计算high,low及length的新值high=low+lengthsymbol_high(c)low=low+lengthsymbol_low(c)1111 11无失真编码算术编码符号定义等号右边的low和length分别为前面已编码符号序列所对应编码区间的下界和区间长度等号左边的low和high分别为输入待编码符号后所对应的当前区间的下界和上界symbol_high(c):当前输入符号c的上界symbol_low(c):当前输入符号c的下界length:“当前区间”的区间长度，length=high-low121212无失真编码13算数编码过程表示（图）算数编码过程表示（图）1313无失真编码算术编码编码过程根据每个符号出现的概率将半开区间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进行编码symbol_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.04141414无失真编码算术编码编码过程输入第三个符号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.06752151515无失真编码算术编码编码过程161616无失真编码算术编码译码过程通过查看哪一个信源符号拥有已编码消息所落入的数值范围，找到消息中的第一个信源符号，0.06752在0,0.2)之间，所以第一个符号为a1从编码数值中消去第一个符号a1的影响，即首先减去a1的所在区间的下界值，然后除以a1对应区间的宽度，即 (0.06752-0)/0.2=0.3376查表找到该结果0.3376落入哪一个符号对应的数值范围，得到第二个符号a2重复上述过程直至解出整个符号流171717无失真编码算术编码译码过程181818无失真编码算术编码总结算术编码对整个消息只产生一个码字，这个码字是在间隔0,1)中的一个实数，因此译码器在接收到这个实数的所有位之前不能进行译码算术编码是一种对，如果有一位发生错误就会导致错误很敏感的编码方法整个消息译错实际编码是用硬件或计算机软件实现，采用递推公式进行编码。算术编码在性能上有很多的优点，如所需的参数少，无很大的码表，主要针对信源概率未知或非平稳情况。在实际应用中还要考虑计算精度、存储量、近似值中Q的选择等问题，随着这些问题的解决，它正在进入实用阶段，但要扩大应用范围或进一步提高性能，降低造价，还需进一步改进。19191920谢谢！2020此课件下载可自行编辑修改，供参考！感谢您的支持，我们努力做得更好！21