第4章无损数据压缩 初始编码间隔[0,0.5][0.5,0.75)[0.75,0.875)[0.875,1) 输入序列为xn:a2,a1,a3…。它的编码过程如图4-04所示,现说明如下。 输入第1个符号是x=a2,可知i=2,定义初始间隔l=,)=[∑P,∑P [0.5,0.75],由此可知d1=0.25,左右边界的二进制数分别表示为:L=0.5=0.1(B),R 0.75=0.11(B)。按照步骤2,1=V1,发送1。因a2≠v2’因此转到步骤3。 输入第2个字符x2=a1,=1,它的子间隔l2=[2)=+d∑p-1, 1+d∑P)=[0.5,0.625),由此可得d2=0.125。左右边界的二进制数分别表示为:L 0.5=0.100…(B),R=0.101…(B)。按照步骤2,l2=V2=0,发送0,而u3和v3不相 同,因此在发送0之后就转到步骤3 输入第3个字符,x3=a3,i=3,它的子间隔3=[2,n)=[l2+d2∑P1 l2+d2∑p,)=[0.59375,0.609375),由此可得d3=0.015625。左右边界的二进制数分别 表示为:L=0.59375=0.10011(B),R=0.609375=0.100111(B。按照步骤2, l4=V4=1,53=V5=1,但6和v不相同,因此在发送011之后转到步骤3。 发送的符号是:10011…。被编码的最后的符号是结束符号。 符号 a1 十进制0 05 075、08751.0 进制00 0.1 0110.11110 符号 2 1 十进制05 0625 0.68750.718750.75 进制01 0.101 0.l0ll0.101l10.11 符号 I a2“12“2a1 十进制0 0.56250.593750.6093750.625 进制0.1 0.1001 0.100110.1001110.101 图4-04算术编码概念 就这个例子而言,算术编码器接受的第1位是“1”,它的间隔范围就限制在[0.5,1) 但在这个范围里有3种可能的码符a2,a3和a4,因此第1位没有包含足够的译码信息。在 接受第2位之后就变成“10”,它落在[0.5,0.75)的间隔里,由于这两位表示的符号都指向 a2开始的间隔,因此就可断定第一个符号是a2。在接受每位信息之后的译码情况如下表 4-08所示。第4章 无损数据压缩 6 初始编码间隔 [0, 0.5] [0.5, 0.75) [0.75, 0.875) [0.875, 1) 输入序列为 xn : a2 ,a1 ,a3 , 。它的编码过程如图4-04所示，现说明如下。 输入第1个符号是 1 a2 x = ，可知 i = 2 ，定义初始间隔 I1 = [l 1 ,r1 ) = [ = − i i pi 1 1 ，= i i i p 1 ] ＝[0.5, 0.75]，由此可知 d1 = 0.25 ，左右边界的二进制数分别表示为：L＝0.5=0.1(B)，R ＝0.75＝0.11(B) 。按照步骤2， 1 1 u = v ，发送1。因 2 2 u  v ，因此转到步骤3。 输入第 2 个字符 2 a1 x = ， i =1 ，它的子间隔 I 2 = [l 2 ,r2 ) = [l 1 + = − i i d pi 1 1 1 ， = + i i d pi l 1 1 1 )＝[0.5, 0.625)，由此可得 2 d =0.125。左右边界的二进制数分别表示为：L ＝0.5=0.100 … (B)，R＝0.101… (B)。按照步骤2，u2 = v2 = 0 ，发送0，而 3 u 和 3 v 不相 同，因此在发送0之后就转到步骤3。 输入第3个字符， 3 a3 x = ， i = 3 , 它的子间隔 I 3 = [I 3 ,r3 ) = [ = + − i i d pi l 1 2 2 1 , = + i i d pi l 1 2 2 )＝[0.59375, 0.609375)，由此可得 3 d =0.015625。左右边界的二进制数分别 表示为： L ＝0.59375=0.10011 (B)，R ＝0.609375=0.100111 (B)。按照步骤2，u3 = v3 = 0 ， u4 = v4 =1，u5 = v5 =1 ，但 6 u 和 6 v 不相同，因此在发送011之后转到步骤3。 … 发送的符号是：10011…。被编码的最后的符号是结束符号。 图4-04 算术编码概念 就这个例子而言，算术编码器接受的第1位是“1”，它的间隔范围就限制在[0.5, 1)， 但在这个范围里有3种可能的码符 a2 , 3 a 和 a4，因此第1位没有包含足够的译码信息。在 接受第2位之后就变成“10”，它落在[0.5, 0.75)的间隔里，由于这两位表示的符号都指向 a2 开始的间隔，因此就可断定第一个符号是 a2 。在接受每位信息之后的译码情况如下表 4-08所示