数据压缩与信源编码第4讲算术编码

1、数据压缩与信源编码第4讲 算术编码Arithmetic Coding西安电子科技大学 电子工程学院主讲 ：林三虎算术编码的提出vHuffman编码是最佳变长码，但仍包含冗余信息。编码是最佳变长码，但仍包含冗余信息。符号a1a2a3a4a5概率0.20.40.20.10.1Huffman编码10011011101111Huffman编码平均码长编码平均码长=0.2*2+0.4*1+0.2*3+0.1*4+0.1*4=2.2bits信源的熵信源的熵Huffman编码冗余度编码冗余度=Huffman编码平均码长编码平均码长-信源的熵信源的熵=0.078bits/symbolsymbolbitaPaP

2、aiaPAHiiii/122. 2)(log)()()()(算术编码的提出v为什么为什么Huffman编码不能达到理论上的极限？编码不能达到理论上的极限？符号a1a2a3a4a5概率0.20.40.20.10.1信息量bit2.321.322.323.323.32Huffman编码10011011101111Huffman编码的问题在于每个符号的编码长度只能为整数，编码的问题在于每个符号的编码长度只能为整数，而信息论告诉我们，对每个符号的最佳编码长度为其信息而信息论告诉我们，对每个符号的最佳编码长度为其信息量。量。能否用小数个二进制位来进行编码呢？能否用小数个二进制位来进行编码呢？行！这就是算

3、术编码。行！这就是算术编码。1948年，香农提出了算术编码的基年，香农提出了算术编码的基本思想，并证明了其优越性。本思想，并证明了其优越性。算术编码的主要步骤v算术编码主要步骤算术编码主要步骤10将当前区间定义为将当前区间定义为0,1)。算术编码的主要步骤v算术编码主要步骤算术编码主要步骤SWIM空格空格10.50.40.20.10把当前区间分割为长度正把当前区间分割为长度正比于符号概率的子区间。比于符号概率的子区间。示例示例1：对输入序列：对输入序列”SWISS MISS”进行压缩进行压缩符号SWIM空格频率51211概率0.50.10.20.10.1算术编码的主要步骤v算术编码主要步骤算术

4、编码主要步骤SWIM空格空格10.50.40.20.10为输入的符号选择一个子区为输入的符号选择一个子区间，将其定义为新的当前区间。间，将其定义为新的当前区间。示例示例1：对输入序列：对输入序列”SWISS MISS”进行压缩进行压缩第一个字符为第一个字符为S，对应区间为，对应区间为0.5,1.0)，将其作为当前区间，按，将其作为当前区间，按照概率进行分割照概率进行分割10.50.5+0.5*0.1=0.550.5+0.5*0.2=0.60.5+0.5*0.4=0.70.5+0.5*0.5=0.75算术编码的主要步骤v算术编码主要步骤算术编码主要步骤SWIM空格空格10.750.70.60.5

5、50.5为输入的符号选择一个子区为输入的符号选择一个子区间，将其定义为新的当前区间。间，将其定义为新的当前区间。示例示例1：对输入序列：对输入序列”SWISS MISS”进行压缩进行压缩第二个字符为第二个字符为W，对应区间为，对应区间为0.7,0.75)，将其作为当前区间，将其作为当前区间，按照概率进行分割按照概率进行分割0.70.750.7+0.05*0.1=0.7050.7+0.05*0.2=0.710.7+0.05*0.4=0.720.7+0.05*0.5=0.725算术编码的主要步骤v算术编码主要步骤算术编码主要步骤SWIM空格空格为输入的符号选择一个子区为输入的符号选择一个子区间，将

6、其定义为新的当前区间。间，将其定义为新的当前区间。示例示例1：对输入序列：对输入序列”SWISS MISS”进行压缩进行压缩第三个字符为第三个字符为I，对应区间为，对应区间为0.7,0.75)，将其作为当前区间，将其作为当前区间，按照概率进行分割按照概率进行分割0.70.750.7050.710.720.7250.710.720.71+0.01*0.1=0.7110.71+0.01*0.2=0.7120.71+0.01*0.4=0.7140.71+0.01*0.5=0.715算术编码的主要步骤v算术编码主要步骤算术编码主要步骤将当前区间定义为0,1)。把当前区间分割为长度正比于符号概率的子区间

7、。为输入的符号选择一个子区间，将其定义为新的当前区间。重复两步，知道所有符号输入完成。以当前区间中的任意一个数字作为输入符号序列的编码。SWIM空格空格0.70.750.7050.710.720.7250.710.720.71+0.01*0.1=0.7110.71+0.01*0.2=0.7120.71+0.01*0.4=0.7140.71+0.01*0.5=0.715算术编码的示例1示例示例1：对输入序列：对输入序列”SWISS MISS”进行压缩进行压缩符号下限上限S0.51.0W0.70.75I0.710.72S0.7150.72S0.71750.72空格0.71750.71775M0.7

8、175250.71755I0.7175300.717535S0.71753250.717535S0.717533750.717535算术编码的示例1示例示例1：对输入序列：对输入序列”SWISS MISS”进行压缩进行压缩输入序列输入序列”SWISS MISS”对应区间为对应区间为输入序列输入序列”SWISS MISS”包含包含10个字符，个字符， 0.717534只包含只包含6个十进制数字，数码缩短，完成数据压缩。个十进制数字，数码缩短，完成数据压缩。算术编码基本过程可以用下面两个式子迭代来完成算术编码基本过程可以用下面两个式子迭代来完成)()(XHighRangeOldLowOldHigh

9、OldLowNewHigh)()(XLowRangeOldLowOldHighOldLowNewLow0.71753375, 0.717535)选择该区间中任意一个数字可代表该输入序列，如选择该区间中任意一个数字可代表该输入序列，如0.717534。算术编码的示例1示例示例1：对压缩序列：对压缩序列0.717534进行解码进行解码0.717534在在0.5,1)范围内，因此第一个符号为范围内，因此第一个符号为S。435068. 05 . 0/ )5 . 0717534. 0(0.435068在在0.4,0.5)范围内，因此第二个符号为范围内，因此第二个符号为W。35068. 01 . 0/ )

10、4 . 0435068. 0(0.35068在在0.2,0.4)范围内，因此第三个符号为范围内，因此第三个符号为I。7534. 02 . 0/ )2 . 035068. 0(0.7534在在0.5,1.0)范围内，因此第四个符号为范围内，因此第四个符号为S。SWIM空格空格10.50.40.20.10算术编码的示例1示例示例1：对压缩序列：对压缩序列0.717534进行解码进行解码5068. 05 . 0/ )5 . 07534. 0(0.5068在在0.5,1.0)范围内，因此第五个符号为范围内，因此第五个符号为S。0136. 05 . 0/ )5 . 05068. 0(0.0136在在0.

11、0,0.1)范围内，因此第六个符号为空格。范围内，因此第六个符号为空格。136. 01 . 0/ )0 . 00136. 0(0.136在在0.1,0.2)范围内，因此第七个符号为范围内，因此第七个符号为M。SWIM空格空格10.50.40.20.10算术编码的示例1示例示例1：对压缩序列：对压缩序列0.717534进行解码进行解码8 . 02 . 0/ )2 . 036. 0(0.8在在0.5,1.0)范围内，因此第九个符号为范围内，因此第九个符号为S。6 . 05 . 0/ )5 . 08 . 0(0.6在在0.5,1.0)范围内，因此第十个符号为范围内，因此第十个符号为S。36. 01

12、. 0/ ) 1 . 0136. 0(0.36在在0.2,0.4)范围内，因此第八个符号为范围内，因此第八个符号为I。RangeXLowRangeCodeCode/)(解码过程可以用下式来表示解码过程可以用下式来表示SWIM空格空格10.50.40.20.10算术编码的示例1问题问题1：第十个符号：第十个符号S解码出来以后，数值为解码出来以后，数值为0.6，如，如何知道码流解码已经结束？何知道码流解码已经结束？6 . 05 . 0/ )5 . 08 . 0(0.6在在0.5,1.0)范围内，因此第十个符号为范围内，因此第十个符号为S。解答解答1：在编码过程中记录码流的长度，添加在压缩：在编码过

13、程中记录码流的长度，添加在压缩码流的前面进行存储码流的前面进行存储/传送。解码时首先获得码流传送。解码时首先获得码流长度，当解码到指定长度时结束。长度，当解码到指定长度时结束。解答解答2：人为添加一个概率非常小的字符：人为添加一个概率非常小的字符EOF在原始在原始码流的最后一起编码，当解码出现码流的最后一起编码，当解码出现EOF的时候结的时候结束。束。算术编码的示例2示例示例2：对输入序列：对输入序列”SWIS”进行压缩进行压缩符号SWIEOF频率5111概率0.40.20.20.2区间0.6,1.0)0.4,0.6)0.2,0.4)0.0,0.2)符号下限上限S0.61.0W0.6+0.4*

14、0.4=0.760.6+0.4*0.6=0.84I0.76+0.2*0.08=0.7760.76+0.4*0.08=0.792S0.776+0.016*0.6=0.78560.792EOF0.7856+0.0064*0=0.78560.7856+0.0064*0.2=0.78688算术编码的示例2示例示例2：对输入序列：对输入序列”SWIS”进行压缩进行压缩符号SWIEOF频率5111概率0.40.20.20.2区间0.6,1.0)0.4,0.6)0.2,0.4)0.0,0.2)符号下限上限S0.61.0W0.6+0.4*0.4=0.760.6+0.4*0.6=0.84I0.76+0.2*0.

15、08=0.7760.76+0.4*0.08=0.792S0.776+0.016*0.6=0.78560.792EOF0.7856+0.0064*0=0.78560.7856+0.0064*0.2=0.78688可以选择可以选择0.7856或者或者0.786作为输出作为输出算术编码的示例2示例示例2：对压缩序列：对压缩序列0.786进行解码进行解码0.786在在0.6,1)范围内，因此第一个符号为范围内，因此第一个符号为S。465. 04 . 0/ )6 . 0786. 0(0.465在在0.4,0.6)范围内，因此第二个符号为范围内，因此第二个符号为W。325. 02 . 0/ )4 . 04

16、65. 0(0.325在在0.2,0.4)范围内，因此第三个符号为范围内，因此第三个符号为I。625. 02 . 0/ )2 . 0325. 0(0.625在在0.6,1.0)范围内，因此第四个符号为范围内，因此第四个符号为S。0.125在在0,0.2)范围内，因此第五个符号为范围内，因此第五个符号为EOF，解码结束。，解码结束。125. 04 . 0/ )6 . 0625. 0(SWIEOF10.60.40.20整数算术编码在算术编码中，当前区间的下限在算术编码中，当前区间的下限LOW和上限和上限HIGH随着码流长随着码流长度的增大，将变的无限长。而实际上，双精度的实数也只有度的增大，将变的

17、无限长。而实际上，双精度的实数也只有16位有效数字，更长精度的数无法表示。位有效数字，更长精度的数无法表示。比如一个比如一个1MB的文件被压缩成的文件被压缩成100KB，即当前区间需要用，即当前区间需要用100KB长的数来表示，而两个这样的数进行加减乘除都需要很长的数来表示，而两个这样的数进行加减乘除都需要很长的时间。长的时间。因此，一个实用的方案应当采用有限长度的整数运算。因此，一个实用的方案应当采用有限长度的整数运算。即使有一种方法能够表示足够长的数据精度，两个很长的数进即使有一种方法能够表示足够长的数据精度，两个很长的数进行运算，花费的时间也无法承受。行运算，花费的时间也无法承受。整数算

18、术编码早在早在1948年，香农就提出了算术编码的基本思想。年，香农就提出了算术编码的基本思想。1960年，年，Peter Elias提出了算术编码的概念，但他发现实际提出了算术编码的概念，但他发现实际当中根本无法实现。当中根本无法实现。直到直到1976年，年，R. Pasco和和J. Rissanen才分别用定长的寄存器才分别用定长的寄存器实现了有限精度的算术编码。实现了有限精度的算术编码。1987年年Witten等人发表了一个实用的算术编码程序，后用等人发表了一个实用的算术编码程序，后用 于于ITU-T的的H.263视频压缩标准。视频压缩标准。整数算术编码示例示例1：对输入序列：对输入序列”

19、SWISS MISS”进行压缩进行压缩符号下限上限S0.51.0W0.700.75I0.710.72S0.7150.720S0.71750.720空格0.717500.71775M0.7175250.717550I0.7175300.717535S0.71753250.7175350S0.717533750.71753500如何利用有限字长寄存器来实现算术编码？如何利用有限字长寄存器来实现算术编码？整数算术编码示例示例1：对输入序列：对输入序列”SWISS MISS”进行压缩进行压缩符号下限上限S0.51.0W0.700.75I0.710.72S0.7150.720S0.71750.720空格

20、0.717500.71775M0.7175250.717550I0.7175300.717535S0.71753250.7175350S0.717533750.71753500在算术编码中，当前区间的下限在算术编码中，当前区间的下限LOW和上限和上限HIGH左边左边的数字一旦相同，就不会再变化。的数字一旦相同，就不会再变化。整数算术编码示例示例1：对输入序列：对输入序列”SWISS MISS”进行压缩进行压缩相同的数字可以直接输出到压缩码流，这样相同的数字可以直接输出到压缩码流，这样LOW和和HIGH中可以不用再保留它们中可以不用再保留它们 ，将它们从，将它们从LOW和和HIGH中移出去。这个

21、特点使得中移出去。这个特点使得LOW和和HIGH可以使用较短的可以使用较短的长度来表示。长度来表示。符号下限上限S0.51.0W0.700.75I0.710.72S0.7150.720S0.71750.720空格0.717500.71775M0.7175250.717550I0.7175300.717535S0.71753250.7175350S0.717533750.71753500整数算术编码示例示例1：对输入序列：对输入序列”SWISS MISS”进行压缩进行压缩相同的数字可以直接输出到压缩码流，这样相同的数字可以直接输出到压缩码流，这样LOW和和HIGH中可以不用再保留它们中可以不用再

22、保留它们 ，将它们从，将它们从LOW和和HIGH中移出去。这个特点使得中移出去。这个特点使得LOW和和HIGH可以使用较短的可以使用较短的长度来表示。长度来表示。符号下限上限S0.51.0W0.700.75I0.710.72S0.7150.720S0.71750.720空格0.717500.71775M0.7175250.717550I0.7175300.717535S0.71753250.7175350S0.717533750.71753500整数算术编码110/ )() 1(XqHighCumFreOldLowOldHighOldLowNewHigh以以0.0000表示表示0，以，以0.9

23、9999表示表示1。以以4位表示，则初始值位表示，则初始值LOW=0000，HIGH=9999。10/ )() 1(XLowCumFreqOldLowOldHighOldLowNewLow如果最高位数字相等，则移出最高位，然后如果最高位数字相等，则移出最高位，然后LOW的右边补的右边补0，HIGH的右边补的右边补9。符号SWIM空格频率51211概率0.50.10.20.10.1区间0.5,1.0)0.4,0.5)0.2,0.4)0.1,0.2)0,0.1)LowCumFreq54210HighCumFreq105421整数算术编码示例示例3：对输入序列：对输入序列”SWISS MISS”进行

24、压缩，输出为进行压缩，输出为717533750符号下限计算上限计算输出下限上限S0000+10000*5/10=50000000+10000*10/10-1=999950009999W5000+5000*4/10=70005000+5000*6/10-1= 7499700004999I0000+5000*2/10=10000000+5000*4/10-1=1999100009999S0000+10000*5/10=50000000+10000*10/10-1=999950009999S5000+5000*5/10=75005000+5000*10/10-1=999975009999空格7500

25、+2500*0/10=75007500+2500*2/10-1=7749750007499110/ )() 1(XqHighCumFreOldLowOldHighOldLowNewHigh10/ )() 1(XLowCumFreqOldLowOldHighOldLowNewLow整数算术编码示例示例3：对输入序列：对输入序列”SWISS MISS”进行压缩，输出为进行压缩，输出为717533750符号下限计算上限计算输出下限上限空格7500+2500*0/10=75007500+2500*2/10-1=7749750007499M5000+2500*1/10=52505000+2500*2/1

26、0-1=5499525004999I2500+2500*2/10=30002500+2500*4/10-1=3499300004999S0000+5000*5/10=25000000+5000*10/10-1=499925004999S2500+2500*5/10=37502500+2500*10/10-1=4999375037504999110/ )() 1(XqHighCumFreOldLowOldHighOldLowNewHigh10/ )() 1(XLowCumFreqOldLowOldHighOldLowNewLow编码结束时，当前下限应当输出，即输出编码结束时，当前下限应当输出，即

27、输出3750或输出或输出4。整数算术编码示例示例3：对输入序列：对输入序列”SWISS MISS”进行压缩，输出为进行压缩，输出为717533750符号下限计算上限计算输出下限上限S0000+10000*5/10=50000000+10000*10/10-1=999950009999W5000+5000*4/10=70005000+5000*6/10-1= 7499700004999I0000+5000*2/10=10000000+5000*4/10-1=1999100009999S0000+10000*5/10=50000000+10000*10/10-1=999950009999S5000

28、+5000*5/10=75005000+5000*10/10-1=999975009999空格7500+2500*0/10=75007500+2500*2/10-1=7749750007499M5000+2500*1/10=52505000+2500*2/10-1=5499525004999I2500+2500*2/10=30002500+2500*4/10-1=3499300004999S0000+5000*5/10=25000000+5000*10/10-1=499925004999S2500+2500*5/10=37502500+2500*10/10-1=4999375037504999

29、整数算术编码整数算术编码的解码过程如下：整数算术编码的解码过程如下：) 1/() 110*) 1(LowHighLowCodeIndex并截尾到最近的整数并截尾到最近的整数10/ )(*) 1(xLowCumFreqLowHighLowLow110/ )(*) 1(xqHighCumFreLowHighLowHigh如果如果Low和和High最左边的数字相等，就把最左边的数字相等，就把Low和和High和和Code左移一位。左移一位。Low的右边补的右边补0，High的右边补的右边补9，Code的右边补上压缩码流的下一位数字的右边补上压缩码流的下一位数字用用Index和累积频率表相比较，解出下

30、一个符号。和累积频率表相比较，解出下一个符号。重复上述过程直到解码结束。重复上述过程直到解码结束。整数算术编码示例示例3：对压缩码流：对压缩码流717533750进行解码。进行解码。计算输出修正Index=(7175-0+1)*10-1)/(9999-0+1)=7.1759S7175Low=0+(9999-0+1)*5/10=50005000High=0+(9999-0+1)*10/10-1=99999999Index=(7175-5000+1)*10-1)/(9999-5000+1)=4.3518W1753Low=5000+(9999-5000+1)*4/10=70000000High=50

31、00+(9999-5000+1)*5/10-1=74994999) 1/() 110*) 1(LowHighLowCodeIndex10/ )(*) 1(xLowCumFreqLowHighLowLow110/ )(*) 1(xqHighCumFreLowHighLowHigh整数算术编码示例示例3：对压缩码流：对压缩码流717533750进行解码。进行解码。计算输出修正Index=(1753-0000+1)*10-1)/(4999-0000+1)=3.5078I7533Low=0000+(4999-0000+1)*2/10=10000000High=0000+(4999-0000+1)*4/

32、10-1=19999999Index=(7533-0+1)*10-1)/(9999-0+1)=7.5339S7533Low=0+(9999-0+1)*5/10=50005000High=0+(9999-0+1)*10/10-1=99999999) 1/() 110*) 1(LowHighLowCodeIndex10/ )(*) 1(xLowCumFreqLowHighLowLow110/ )(*) 1(xqHighCumFreLowHighLowHigh整数算术编码示例示例3：对压缩码流：对压缩码流717533750进行解码。进行解码。计算输出修正Index=(7533-5000+1)*10-

33、1)/(9999-5000+1)=5.0678S7533Low=5000+(9999-5000+1)*5/10=75000000High=5000+(9999-5000+1)*10/10-1=99994999Index=(7533-7500+1)*10-1)/(9999-7500+1)=0.1356空格5337Low=7500+(9999-7500+1)*0/10=75005000High=7500+(9999-7500+1)*1/10-1=77497499) 1/() 110*) 1(LowHighLowCodeIndex10/ )(*) 1(xLowCumFreqLowHighLowLow

34、110/ )(*) 1(xqHighCumFreLowHighLowHigh整数算术编码示例示例3：对压缩码流：对压缩码流717533750进行解码。进行解码。计算输出修正Index=(5337-5000+1)*10-1)/(9999-5000+1)=1.3516M3375Low=5000+(9999-5000+1)*1/10=52502500High=5000+(9999-0+1)*2/10-1=54994999Index=(3375-2500+1)*10-1)/(4999-2500+1)=3.5063I3750Low=2500+(4999-2500+1)*2/10=30000000High

35、=2500+(4999-2500+1)*4/10-1=34994999) 1/() 110*) 1(LowHighLowCodeIndex10/ )(*) 1(xLowCumFreqLowHighLowLow110/ )(*) 1(xqHighCumFreLowHighLowHigh整数算术编码示例示例3：对压缩码流：对压缩码流717533750进行解码。进行解码。计算输出修正Index=(3750-0000+1)*10-1)/(4999-0000+1)=7.5018S3750Low=0000+(4999-0000+1)*5/10=25002500High=0000+(4999-0000+1)

36、*10/10-1=49994999Index=(3750-2500+1)*10-1)/4999-2500+1)=5.0036S3375Low=2500+(4999-2500+1)*5/10=37502500High=2500+(4999-2500+1)*10/10-1=49994999) 1/() 110*) 1(LowHighLowCodeIndex10/ )(*) 1(xLowCumFreqLowHighLowLow110/ )(*) 1(xqHighCumFreLowHighLowHigh解码结果为解码结果为SWISS MISS整数算术编码问题问题2：当：当LOW和和HIGH计算出现计算

37、出现3999和和4000时，区间长度只时，区间长度只有有1，继续编码，继续编码LOW和和HIGH的值将一直保持的值将一直保持3999和和4000。在这种情况下，直到输入码流结束，编码器都将不会产生在这种情况下，直到输入码流结束，编码器都将不会产生输出。如何避免这种情况？输出。如何避免这种情况？10/ )(*) 1(xLowCumFreqLowHighLowLow110/ )(*) 1(xqHighCumFreLowHighLowHigh解答：解答：在区间变短的时候就要提前进行处理。在区间变短的时候就要提前进行处理。比如在出现比如在出现39xx和和40 xx的时候，就要对区间进行比例放大。的时候

38、，就要对区间进行比例放大。整数算术编码解答：解答：当出现当出现39xx和和40 xx的时候，将次高位的时候，将次高位9和和0移出，移出，LOW和和HIGH变为变为3xx0和和4xx9，使得区间放大。，使得区间放大。这个过程可能重复若干次，直到区间变的足够大。这个过程可能重复若干次，直到区间变的足够大。以以Scale记录移出次高位的次数，每当次高位移出，变量记录移出次高位的次数，每当次高位移出，变量Scale加加1。继续迭代，直到区间变为继续迭代，直到区间变为3xxx,3xxx)或或4xxx,4xxx)。输出最高位。输出最高位。如果最高位为如果最高位为3，则输出，则输出Scale个个9；如果最高

39、位为；如果最高位为4，则输，则输出出Scale个个0。将将Scale清清0。整数算术编码下限下限3999399039003000迭代迭代3xxx上限上限4000400940994999迭代迭代3xxxScale01230输出输出无无无无无无无无无无3999实际上是实际上是3999xxx，因为因为999先被移出去先被移出去了了下限下限3999399039003000迭代迭代4xxx上限上限4000400940994999迭代迭代4xxxScale01230输出输出无无无无无无无无无无4000实际上是实际上是4000 xxx，因为因为000先被移出去先被移出去了了整数算术编码问题问题3：LOW和和

40、HIGH需要使用多少位？用需要使用多少位？用000表示表示0，用，用999表示表示1行不行？行不行？eqTotalCumFrxLowCumFreqLowHighLowLow/)(*)1(1/)(*)1(eqTotalCumFrxqHighCumFreLowHighLowHigh解答：解答：High和和Low都是整数，要保证在每次迭代时每个符号的区都是整数，要保证在每次迭代时每个符号的区间宽度大于间宽度大于0，无法进行表示。，无法进行表示。TotalCumFreq等价于数据长度，数据越长，等价于数据长度，数据越长，LOW和和HIGH需要的位数越多。需要的位数越多。二进制算术编码以以m个个0代表代

41、表0，1个个1和和m-1个个0代表代表0.5，m个个1代表代表1。 times00.00m times100.015 . 0m times11.11m以以in表示符号表示符号i出现的次数，定义出现的次数，定义kiinkCumCount1)(编码下限编码下限l和上限和上限u可以用下式迭代：可以用下式迭代：TotalCountxCumCountlull) 1(*) 1(1)(*) 1(TotalCountxCumCountlulu二进制算术编码如果如果l和和u的最高位都是的最高位都是b，或者，或者Scale条件成立条件成立如果如果l和和u的最高位都是的最高位都是b将将b输出到码流输出到码流将将l左

42、移左移1位，最低位补位，最低位补0将将u左移左移1位，最低位补位，最低位补1如果如果Scale0，输出，输出b的补，的补，scale减减1如果如果Scale条件成立条件成立将将l左移左移1位，最低位补位，最低位补0将将u左移左移1位，最低位补位，最低位补1l 和和u最高位取反，最高位取反，scale加加1LOWHIGH0X0X输出输出01X1X输出输出10010正常区间正常区间0111正常区间正常区间0011正常区间正常区间0110Scale区间区间二进制算术编码假定对序列假定对序列1,3,2,1进行算术编码，其统计参数进行算术编码，其统计参数XCount(X)CumCount(X)00014

43、04021413950选用选用8位二进制数计算，初始值位二进制数计算，初始值Scale=0，Low=0=(00000000)2，High=255=(11111111)2二进制算术编码第一个符号是第一个符号是12)00000000(0500*) 10255(0Low2)11001011(20315040*) 10255(0HighXCount(X)CumCount(X)0001404021413950TotalCountxCumCountlull) 1(*) 1(1)(*) 1(TotalCountxCumCountlulu最高位不相等，无输出最高位不相等，无输出二进制算术编码第二个符号是第二个

44、符号是322)01001110(78)10100111(1675041*) 10203(0Low22)10010111(151)11001011(20315050*) 10203(0HighXCount(X)CumCount(X)0001404021413950TotalCountxCumCountlull) 1(*) 1(1)(*) 1(TotalCountxCumCountlulu最高位相等，输出最高位最高位相等，输出最高位1。low和和High左移左移1位，位，Low最低位补最低位补0，High最低位补最低位补1二进制算术编码22)00011100(28)01001110(78Low22

45、)10101111(175)10010111(151High现在现在Low=01xxxxxx，High=10 xxxxxx，将区间比例，将区间比例放大。放大。Low和和High分别左移分别左移1位，最高位取反，位，最高位取反，右边分别补右边分别补0和和1，标志变量，标志变量Scale加加1。110Scale第二个符号的输出为第二个符号的输出为1二进制算术编码第三个符号是第三个符号是222)00100100(36)10010010(1465040*) 128175(28Low22)00101001(41)10010100(14815041*) 128175(28HighXCount(X)CumC

46、ount(X)0001404021413950TotalCountxCumCountlull) 1(*) 1(1)(*) 1(TotalCountxCumCountlulu最高位相等，输出最高位最高位相等，输出最高位1。 low和和High左移左移1位，位，Low最低位补最低位补0，High最低位补最低位补1。因。因Scale=1，再输，再输出最高位的补码，即出最高位的补码，即1个个0，将，将Scale减减1变为变为0。二进制算术编码最高位仍然相等，输出最高位最高位仍然相等，输出最高位0。low和和High左移左移1位，位，Low最低位补最低位补0，High最低位补最低位补122)010010

47、00(72)00100100(36Low22)01010011(83)00101001(41High最高位仍然相等，输出最高位最高位仍然相等，输出最高位0。low和和High左移左移1位，位，Low最低位补最低位补0，High最低位补最低位补122)10010000(144)01001000(72Low22)10100111(167)01010011(83High二进制算术编码最高位仍然相等，输出最高位最高位仍然相等，输出最高位1。low和和High左移左移1位，位，Low最低位补最低位补0，High最低位补最低位补122)00100000(32)10010000(144Low22)01001

48、111(79)10100111(167High最高位仍然相等，输出最高位最高位仍然相等，输出最高位0。low和和High左移左移1位，位，Low最低位补最低位补0，High最低位补最低位补1。22)01000000(64)00100000(3222)10011111(159)01001111(79二进制算术编码现在现在Low=01xxxxxx，High=10 xxxxxx，将区间比例，将区间比例放大。放大。Low和和High分别左移分别左移1位，最高位取反，位，最高位取反，右边分别补右边分别补0和和1，标志变量，标志变量Scale加加1。110Scale22)00000000(64)01000

49、000(6422)10111111(191)10011111(159第三个符号的输出为第三个符号的输出为100010二进制算术编码第四个符号是第四个符号是12)00000000(0500*) 10191(0Low2)10011000(15215040*) 10191(0High最高位不相等，无输出。最高位不相等，无输出。因码流结束，应输出结束时的因码流结束，应输出结束时的Low，即输出，即输出8个个0。又因又因Scale=1，在输出第，在输出第1个个0之后应插入之后应插入1个个1。因此第四个符号的输出为因此第四个符号的输出为010000000码流码流1,3,2,1的输出为的输出为1100010

50、010000000二进制算术编码解码过程刚好相反解码过程刚好相反以以Index解码符号解码符号xTotalCountxCumCountlull) 1(*) 1(1)(*) 1(TotalCountxCumCountlulu初始化初始化l和和u。从压缩码流读入。从压缩码流读入m个比特作为个比特作为t。) 1(1*) 1(luTotalCountltIndex二进制算术编码如果如果l和和u的最高位都是的最高位都是b，或者，或者Scale条件成立条件成立如果如果l和和u的最高位都是的最高位都是b将将t左移左移1位，最低位从压缩码流补位，最低位从压缩码流补1个比特个比特将将l左移左移1位，最低位补位，

51、最低位补0将将u左移左移1位，最低位补位，最低位补1如果如果Scale条件成立条件成立将将t左移左移1位，最低位从压缩码流补位，最低位从压缩码流补1个比特个比特将将l左移左移1位，最低位补位，最低位补0将将u左移左移1位，最低位补位，最低位补1将将l,u,t最高位取反最高位取反二进制算术编码假定对压缩码流假定对压缩码流1100010010000000进行解码进行解码38) 10255(150*) 10196(Index0)00000000(2Low255)10011000(2High196)11000100(2t显然，该字符为显然，该字符为1。2)00000000(0500*) 10255(0l2)11001011(20315040*) 10255(0uXCount(X)CumCount(X)0001404021413950二进制算术编码假定对压缩码流假定对压缩码流1100010010000000进行解码进行解码48) 10203(150*197IndexXCount(X)CumCount(X