算术编码-课件

1计算机应用技术

张志林

算数编码无失真编码1ppt课件算术编码特点非分组码，它是从全序列出发，考虑符号之间的依赖关系。经香农-费诺-埃利斯编码推广而来的，直接对信源符号序列进行编码输出。即时码，信源符号序列对应的累积概率区间是不重叠的。肯定也可以唯一译码。不必预先定义概率模型,自适应模式具有独特的优点;信源符号概率接近时,建议使用算术编码,这种情况下其效率高于Huffman编码(约5%)。JPEG扩展系统采用。无失真编码22ppt课件算术编码特点算术编码并不是将单个信源符号映射成一个码字，而是把整个信源表示为实数线上0到1之间的一个区间,其长度等于该序列的概率。在该区间内选择一个代表性的小数，转换为二进制作为实际的编码输出消息序列中的每个元素都要用来压缩这个区间消息序列中元素越多，所得到的区间就越小，当区间变小时，就需要更多的位数来表示这个区间无失真编码33ppt课件算术编码的编码过程从信源符号全序列出发，将各信源序列依累积概率分布函数的大小映射到［０,１］区间,将［０,１］区间分成许多互不重叠的小区间。此时每个符号序列均有一个小区间与之对应，因而可在小区间内取点来代表该符号序列。无失真编码44ppt课件无失真编码5算术编码应用（1）采用固定模式符号概率分配如下：

字符:

aeiou

概率:0.20.30.10.20.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为编码字符分配的间隔高端。5ppt课件无失真编码6算术编码应用（1）初始high=1,low=0,range=high-low,一个字符编码后新的low和high按下式计算：

low=low+range×rangelow；high=low+range×rangehigh。(1)在第一个字符e被编码时,e的rangelow=0.2,rangehigh=0.5,因此:

low=0+1×0.2=0.2high=0+1×0.5=0.5range=high-low=0.5-0.2=0.3

此时分配给e的范围为［0.2,0.5)6ppt课件无失真编码7(2)第二个字符a编码时使用新生成范围[0.2,0.5),a的rangelow=0,rangehigh=0.2,因此:

low=0.2+0.3×0=0.2high=0.2+0.3×0.2=0.26range=0.06

范围变成[0.2,0.26)7ppt课件无失真编码8(3)对下一个字符i编号,i的rangelow=0.5，rangehigh=0.6,range=0.06,则：

low=0.2+0.06×0.5=0.23high=0.2+0.06×0.6=0.236结果：用[0.23,0.236)表示数据串eai,如果解码器知道最后范围是[0.23,0.236),它马上可解得一个字符为e,然后依次得到唯一解a、i,最终得到eai8ppt课件

算术编码过程表示91e0.5ea0.260.2360.80.60.50.20uoieauoieauoieauoiea0.20.20.23eai无失真编码9ppt课件无失真编码10算术编码应用（2）10ppt课件无失真编码算术编码设定初值high=1.0low=0length=high-low=1.0对符号序列中每一个输入的信源符号进行编码，计算high,low及length的新值high=low+length×symbol_high(c)low=low+length×symbol_low(c)1111ppt课件无失真编码算术编码符号定义等号右边的low和length分别为前面已编码符号序列所对应编码区间的下界和区间长度等号左边的low和high分别为输入待编码符号后所对应的当前区间的下界和上界symbol_high(c):当前输入符号c的上界symbol_low(c):当前输入符号c的下界length:“当前区间”的区间长度，length=high-low1212ppt课件无失真编码13算数编码过程表示（图）13ppt课件无失真编码算术编码—编码过程根据每个符号出现的概率将半开区间[0,1)分成四个区域[0,0.2)[0.2,0.4)[0.4,0.8)[0.8,1)对输入的第一个符号a1编码symbol_high(a1)=0.2symbol_low(a1)=0high=0+1.0×0.2=0.2low=0+1.0×0=0输入第一个符号a1后，编码区间由[0,1)变为[0,0.2)，当前区间长度length=0.2-0=0.2对输入的符号序列a1a2进行编码symbol_high(a2)=0.4symbol_low(a2)=0.2high=0+0.2×0.4=0.08low=0+0.2×0.2=0.04输入第二个符号a2后，编码区间由[0,0.2)变为[0.04,0.08)，当前区间长度length=0.08-0.04=0.041414ppt课件无失真编码算术编码—编码过程输入第三个符号a3后，对序列a1a2a3进行编码,编码区间为[0.056,0.072)输入第四个符号a3后,对序列a1a2a3a3进行编码,编码区间为[0.0624,0.0688)输入第五个符号a4后,对序列a1a2a3a3a4进行编码,编码区间为[0.06752,0.0688)在区间[0.06752,0.0688)内的任何数字都可以表示消息a1a2a3a3a4,例0.067521515ppt课件无失真编码算术编码—编码过程1616ppt课件无失真编码算术编码—译码过程通过查看哪一个信源符号拥有已编码消息所落入的数值范围，找到消息中的第一个信源符号，0.06752在[0,0.2)之间，所以第一个符号为a1从编码数值中消去第一个符号a1的影响，即首先减去a1的所在区间的下界值，然后除以a1对应区间的宽度，即

(0.06752-0)/0.2=0.3376查表找到该结果0.3376落入哪一个符号对应的数值范围，得到第二个符号a2重复上述过程直至解出整个符号流1717ppt课件无失真编码算术编码—译码过程1818ppt课件无失真编码算术编码总结算术编码对整个消息只产生一个码字，这个码字是在间隔[0,1)中的一个实数，因此译码器在接收到这个实数的所有位之前不能进行译码算术编码是一种对，如果有一位发生错误就会导致错误很敏感的编码方法整个消息译错实际编码是用