算术编码+及译码原理.docVIP

算术编码与译码原理： 1、编码过程算术编码方法是将被编码的一则消息或符号串（序列）表示成0和1之间的一个间隔（Interval），即对一串符号直接编码成[0,1]区间上的一个浮点小数。符号序列越长，编码表示它的间隔越小，表示这一间隔所需的位数就越多。信源中的符号序列仍然要根据某种模式生成概率的大小来减少间隔。可能出现的符号概率要比不太可能出现的符号减少范围小，因此，只正加较少的比特位。在传输任何符号串之前，0符号串的完整范围设为[0,1]。当一个符号被处理时，这一范围就依据分配给这一符号的那一范围变窄。算术编码的过程，实际上就是依据信源符号的发生概率对码区间分割的过程。举例说明如下：假设一则消息“static_tree”具有如下的概率分布：?????????????字符 ??????????????????概率?????---------------------------------------------------------------????????????＿（space） ????????????0.1?????????????a ?????????????????????0.1?????????????e ?????????????????????0.3?????????????r ?????????????????????0.1?????????????s ?????????????????????0.1?????????????t ?????????????????????0.3下面用算术编码方法给该消息编码。一旦字符的概率已知，就沿着“概率线”为每一个单独的符号设定一个范围，哪一个被设定到哪一段范围并不重要，只要编码和解码都以同样方式进行就可以，这里所用的6个字符被分配的范围（range）如下：?????字符 ????????????概率 ????????????范围???＿(space) ?????????0.1 ???????????0≤r0.1??????a ??????????????0.1 ???????????0.1≤r0.2??????e ??????????????0.3 ???????????0.2≤r0.5??????r ??????????????0.1 ???????????0.5≤r0.6??????s ??????????????0.1 ???????????0.6≤r0.7??????t ??????????????0.3 ???????????0.7≤r1.0?????----------------------------------------------------------------??????????对“state_tree”的算术编码过程为：（1）初始化时，被分割的范围range=high-low=[0,1）,下一个范围的低、高端分别由下式计算：?????????????Low=low + range×range low?????????????High=low + range×range high其中等号右边的low为上一个被编码字符的范围低；range low和range high分别为被编码符号已给定的字符出现概率范围的low和high。（2） 对消息第一字符s编码：s的range low=0.6，?s的range high=0.7因此，下一个区间的low和high为：????????????????Low=low + range×range low=0+1×0.6=0.6????????????????High=low + range×range high=0+1×0.7=0.7??????????????????Range=high-low=0.7-0.6=0.1??????????????????S将区间[0,1）=[0.6,0.7）??????(3)对第二个字符t编码，使用的新生范围为[0.6,0.7），因为t的range low=0.7,range high=1.0,因此下一个low,high分别为???????????????????Low=0.6+0.1×0.7＝0.67???????????????????High=0.6+0.1×1.0＝0.70???????????????????Range=0.7-0.67=0.03???????????????????t将[0.6,0.7）=[0.67,0.70）???????(4)对第三个字符a编码，在新生成的[0.67,0.70）中进行分割，因为a的range low=0.10,range high=0.2,因此下一