算术编码的基本思想学习教案

1、会计学1算术编码的基本算术编码的基本(jbn)思想思想第一页，共65页。回顾回顾(hug)：扩展的：扩展的Huffman编编码码n基本(jbn)思想：n考虑对两个字母序列而不是单个字母编码l = 1.222/2 = 0.611冗余(rn y) = 0.276 bits/symbol（27%）第2页/共65页第二页，共65页。回顾：扩展回顾：扩展(kuzhn)的的Huffman编码编码n该思想还可以继续扩展n考虑(kol)长度为n的所有可能的mn 序列 (已做了32)n理论上：考虑(kol)更长的序列能提高编码性能n实际上：n字母表的指数增长将使得这不现实n例如：对长度为3的ASCII序列：25

2、63 = 224 = 16Mn需要对长度为n的所有序列产生码本n很多序列的概率可能为0n分布严重不对称是真正的大问题：nA = a, b, c, P(a) = 0.95, P(b) = 0.02, P(c) = 0.03 nH = 0.335 bits/symbolnl1 = 1.05, l2 = 0.611, n当n = 8时编码性能才变得可接受n但此时|alphabet| = 38 = 6561 !第3页/共65页第三页，共65页。算术算术(sunsh)编码（编码（Arithmetic Coding）n算术编码：从另一种角度对很长的信源符号序列进行有效(yuxio)编码n对整个序列信源符号

3、串产生一个唯一的标识（ tag ）n直接对序列进行编码（不是码字的串联）：非分组码n不用对该长度所有可能的序列编码n标识是0,1)之间的一个数（二进制小数，可作为序列的二进制编码）第4页/共65页第四页，共65页。概率概率(gil)复习复习 n随机变量：n将试验的输出映射到实数n用数字代替符号nX(ai) = i, 其中 ai A (A = ai, i = 1.n)n给定信源的概率模型Pn概率密度函数（probability density function, pdf）n累积(lij)密度函数（cumulative density function, cdf） iP XiP a 11iiXik

4、kFiP XkP a第5页/共65页第五页，共65页。产生产生(chnshng)标识标识n定义一一映射：nak FX(k-1), FX(k), k = 1.m, FX(0) = 0nFX(k-1), FX(k)区间内的任何数字表示 akn对2字母序列ak aj编码n对ak ，选择FX(k-1), FX(k)n然后将该区间按比例分割(fng)并选取第j个区间： 00,.1,1XXXFmiiFiF 11,111XXXXXXXXFjFjFkFkFkFkFkFkv将0, 1)分为(fn wi)m个区间：第6页/共65页第六页，共65页。产生产生(chnshng)标识：例标识：例n考虑对a1a2a3编码

5、(bin m)：nA = a1, a2, a3, P = 0.7, 0.1, 0.2)n映射：a1 1, a2 2, a3 3ncdf: FX(1) = 0.7, FX(2) = 0.8, FX(3) = 1.0第7页/共65页第七页，共65页。映射映射(yngsh)成实数成实数nA = a1, a2, , amv对公平(gng png)掷骰子的例子：1, 2, 3, 4, 5, 66.161kforkXP iXPiFiXPkXPaTXikiX2112111 25. 022112XPXPTX 75. 0521541XPkXPTkX第8页/共65页第八页，共65页。词典词典(cdin)顺序顺序（

6、 Lexicographic order ）n字符串的词典顺序：n其中 表示(biosh)“在字母顺序中，y在x的前面”nn 为序列的长度 ( ):12inXiiTPPy y xxyxxy 第9页/共65页第九页，共65页。词典词典(cdin)顺序：例顺序：例n考虑两轮(lin ln)连续的骰子：n输出 = 11, 12, , 16, 21, 22, , 26, , 61, 62, , 66 469. 07251321121113xPxPxPTXv注意：v为了产生13的标识，我们(w men)不必对产生其他标识v但是，为了产生长度为n的字符串的标识，我们(w men)必须知道比其短的字符串的概

7、率v这与产生所有的码字一样繁重！v应该想办法来避免此事第10页/共65页第十页，共65页。区间区间(q jin)构造构造n观察n包含某个标识的区间与所有其他标识的区间不相交n基本(jbn)思想n递归：将序列的下/上界视为更短序列的界的函数n上述骰子的例子：n考虑序列：3 2 2 n令u(n), l(n) 为长度为n序列的上界和下界，则nu(1) = FX(3), l(1) = FX(2)nu(2) = FX(2)(32), l(2) = FX(2)(31) (2)32(11).(16)(21).(26)(31)(32)XFPPPPPPxxxxxx第11页/共65页第十一页，共65页。区间区间(

8、q jin)构造构造 (2)32(11).(16)(21).(26)(31)(32)XFPPPPPPxxxxxx6661212112111,iiiPkiP xk xiP xkP xiP xkwherex xxx(2)1132(1)(2)(31)(32)(2)(31)(32)XXFP xP xPPFPPxxxx1221(31)(32)(3)(1)(2)(3)(2)XPPP xP xP xP xFxx)2()3()3(1XXFFxP)2()2()3()2(32)2(XXXXXFFFFF)2()1()1()1()2(XFlulu第12页/共65页第十二页，共65页。区间区间(q jin)构造构造 )

9、 1 ()2()3()2(31)2(XXXXXFFFFF) 1 ()1()1()1()2(XFlull()()(3)( )(3)( )322 ,32133XXuFlF=()()(3)(2)(2)(2)322(31)(32)(31)(2)XXXXXFFFFF=+-()()(3)(2)(2)(2)321(31)(32)(31)(1)XXXXXFFFFF=+-)2()2()2()2()3(XFlulu) 1 ()2()2()2()3(XFlull)2()2()3()2(32)2(XXXXXFFFFF)2()1()1()1()2(XFlulu第13页/共65页第十三页，共65页。产生产生(chnshn

10、g)标识标识n通常(tngchng)，对任意序列x = x1x2xn ( )( )2nnXulTx( )(1)(1)(1)( )(1)(1)(1)()(1)kkkkkkXkXkkkulullluFxFxl只需知道(zh do)信源的cdf，即信源的概率模型算术编码：编码和解码过程都只涉及算术运算（加、减、乘、除）第14页/共65页第十四页，共65页。产生产生(chnshng)标识：例标识：例n考虑随机变量(su j bin lin)X(ai) = i n对序列1 3 2 1编码：3, 1)(, 1)3(,82. 0)2(, 8 . 0) 1 (, 0, 0)(kkFFFFkkFXXXXX1,

11、0)0()0(ul8 . 0) 1 (0)0()0()0()0()1()0()0()0()1(XXFluluFlull18 . 0) 3(656. 0)2()1()1()1()2()1()1()1()2(XXFluluFlull1377408. 0)2(7712. 0) 1 ()2()2()2()3()2()2()2()3(XXFluluFlull132()()(4)(1)(3)(3)(4)(3)(3)(3)( )0.7712(1)0.7735040XXllulFululF=+-=+-=1321(4)(4)13210.7723522XulT( )(1)(1)(1)( )(1)(1)(1)()(

12、1)kkkkkkXkXkkkulullluFxFxl第15页/共65页第十五页，共65页。解码解码(jim)标识标识nAlgorithmnInitialize l(0) = 0, u(0) = 1.1.For each i, i = 1.nCompute t*=(tag-l(k-1)/(u(k-1)-l(k-1).2.Find the xk: FX(xk-1) t* FX(xk).3.Update u(n), l(n)4.If done-exit, otherwise goto 1.第16页/共65页第十六页，共65页。解码解码(jim)：例：例3, 1)(, 1)3(,82. 0)2(, 8

13、 . 0) 1 (, 0, 0)(kkFFFFkkFXXXXXvAlgorithmInitialize l(0) = 0, u(0) = 1.1.Compute t*=(tag-l(k-1)/(u(k-1)-l(k-1).2.Find the xk: FX(xk-1) t* FX(xk).3.Update u(k), l(k)4.If done-exit, otherwise goto 1. 8 . 0) 1 (0)0() 1 (8 . 00)0(772352. 0010772352. 0)0()0()0()1()0()0()0()1(*XXXXFluluFlullFtFt 8 . 0)3(6

14、56. 0)2()3(182. 0)2(96544. 008 . 00772352. 0)1()1()1()2()1()1()1()2(*XXXXFluluFlullFtFt77408. 0)2(7712. 0)1 ()2(82. 08 . 0)1 (808. 0656. 08 . 0656. 0772352. 0)2()2()2()3()2()2()2()3(*XXXXFluluFlullFtFt) 1 (8 . 00)0(4 . 07712. 077408. 07712. 0772352. 0*XXFtFt1131321321第17页/共65页第十七页，共65页。算术算术(sunsh)编码

15、的唯一性和效编码的唯一性和效率率n上述产生的标识可以唯一表示一个序列，这意味着该标识的二进制表示为序列的唯一二进制编码n但二进制表示的精度可以是无限长：保证唯一性但不够有效n为了保证有效性，可以截断二进制表示，但如何保证唯一性？n答案：为了保证唯一性和有效性，需取小数点后l位数字作为信源序列的码字，其中n注意(zh y)：P(x)为最后区间的宽度，也是该符号串的概率n符合概率匹配原则：出现概率较大的符号取较短的码字，而对出现概率较小的符号取较长的码字 1log1( )lPxx第18页/共65页第十八页，共65页。算术算术(sunsh)编码的唯一性和效编码的唯一性和效率率n长度为n的序列的算术编

16、码(bin m)的平均码长为： ( )1 ( )log1( )1 ( ) log1 1( ) ( )log( )2( ) 22AnlPlPPPPPPPH XnH X xxxxxxxxx 2 2 nAAHnH XlnH XXlH Xn算术编码的效率高：当信源符号序列很长，平均(pngjn)码长接近信源的熵第19页/共65页第十九页，共65页。实现实现(shxin)n迄今为止n已有能工作的编码/解码算法n假设实数（无限精度）n最终l(n) 和u(n) 将集中到一起n我们需要对字符串增量(zn lin)式编码n观测：当区间变窄时nl(n), u(n) 0, 0.5), 或nl(n), u(n) 0.

17、5, 1), 或nl(n) 0, 0.5), u(n) 0.5, 1).n先集中处理1. & 2，稍后再讨论3第20页/共65页第二十页，共65页。实现实现(shxin)n编码器：n一旦我们到达1. 或2.，就可以忽略0,1)的另一半n还需要告知解码器标识所在的半区间：n发送0/1 比特用来指示下上界所在区间n将标识区间缩放到0, 1):nE1: 0, 0.5) = 0, 1);E1(x) = 2xnE2: 0. 5,1) = 0, 1);E2(x) = 2(x-0.5)n注意：在缩放过程中我们丢失(dis)了最高位n但这不成问题我们已经发送出去了n解码器n根据0/1比特并相应缩放n与

18、编码器保持同步第21页/共65页第二十一页，共65页。标识产生标识产生(chnshng)：带缩放的：带缩放的例子例子n考虑随机变量(su j bin lin)X(ai) = i n对序列1 3 2 1编码：3, 1)(, 1)3(,82. 0)2(, 8 . 0) 1 (, 0, 0)(kkFFFFkkFXXXXX1, 0)0()0(ul(1)(0)(0)(0)(1)(0)(0)(0)(1)(1)(1)(1)(0)0(1)0.8,)0,0.5),)0.5,1)XXllulFululFluluget next symbolInput: 1321Output: 6 . 0)5 . 08 . 0(2

19、312. 0)5 . 0656. 0(2) 1 , 5 . 08 . 0,656. 08 . 0) 3(656. 0)2()2()2()1()1()1()2()1()1()1()2(ulFluluFlullXXInput: -321Output: 1第22页/共65页第二十二页，共65页。标识标识(biozh)产生：带缩放的例子产生：带缩放的例子Input: -21Output: 1154816. 0)2(5424. 0) 1 ()2()2()2()3()2()2()2()3(XXFluluFlull6 . 0,312. 0)2()2(ul09632. 05 . 054816. 020848.

20、 05 . 05424. 02)3()3(ulInput: -1Output: 11019264. 009632. 021696. 00848. 02)3()3(ulInput: -1Output: 110038528. 019264. 023392. 01696. 02)3()3(ulInput: -1Output: 11000第23页/共65页第二十三页，共65页。标识产生标识产生(chnshng)：带缩放的例子：带缩放的例子nEOT:nl(n),u(n)区间内的任何一个(y )数字n在此选 0.510 = 0.1277056. 038528. 026784. 03392. 02)3()3

21、(ulInput: -1Output: 11000154112. 0)5 . 077056. 0(23568. 0)5 . 06784. 0(2)3()3(ulInput: -1Output: 110001504256. 0) 1 ()3568. 054112. 0(3568. 03568. 0)0()3568. 054112. 0(3568. 0)4()4(XXFuFlInput: -1Output: 110001Output: 11000110v注意(zh y)：0.1100011 = 2-1+2-2+2-6+2-7= 0.7734375 0.7712,0.77408第24页/共65页第二

22、十四页，共65页。增量式标识增量式标识(biozh)解码解码n我们需要(xyo)增量式解码n如：网络传输n问题n如何开始？n必须有足够的信息，可以对第一个字符无歧义解码n 接收到的比特数应比最小标识对应的区间更小n怎样继续？n一旦有一个非歧义的开始，只要模拟编码器即可n如何结束？第25页/共65页第二十五页，共65页。标识标识(biozh)解码：例解码：例n假设(jish)码字长为6n输入：110001100000n0.1100012 = 0.76562510n第1位：1nOutput: 1 )3(182. 0)2(9570. 008 . 00765625. 0*XXFtFt8 . 0)3(6

23、56. 0)2()1()1()1()2()1()1()1()2(XXFluluFlullInput: 110001100000Output: 13Input:-10001100000 (左移)6 . 0)5 . 08 . 0(2312. 0)5 . 0656. 0(2)2()2(ul )2(82. 08 . 0) 1 (8155. 0312. 06 . 0312. 0546875. 0*XXFtFtInput: -10001100000 (0.546875)Output: 13254816. 0)2(5424. 0) 1 ()2()2()2()3()2()2()2()3(XXFluluFlul

24、l09632. 05 . 054816. 020848. 05 . 05424. 02)3()3(ulInput: -001100000 (左移)Input: -0001100000 (左移)(1)(1)0(10)000(10)0.80.8lu第26页/共65页第二十六页，共65页。此时解码(jim)最后一个符号标识标识(biozh)解码：例解码：例19264. 009632. 021696. 00848. 02)3()3(ulInput: -01100000 (左移)38528. 019264. 023392. 01696. 02)3()3(ulInput: -1100000 (左移)770

25、56. 038528. 026784. 03392. 02)3()3(ulInput: -100000 (左移)504256. 0) 1 ()3568. 054112. 0(3568. 03568. 0)0()3568. 054112. 0(3568. 0)4()4(XXFuFlInput: -100000*2*1000000.5,(0)00.8(1)XXtFtFOutput: 1321第27页/共65页第二十七页，共65页。第三种情况第三种情况(qngkung)：E3n回忆三种情况nl(n), u(n) 0, 0.5): E1: 0, 0.5) = 0, 1); E1(x) = 2xnl(n

26、), u(n) 0.5, 1): E2: 0. 5, 1) = 0, 1); E2(x) = 2(x-0.5)nl(n) 0, 0.5), u(n) 0.5, 1): E3(x) = ?nE3 缩放nE3: 0.25, 0.75) = 0, 1); E3(x) = 2(x-0.25)n编码nE1 = 0, E2 = 1, E3 = ?n注意： nE3 E3 E1 = E1 E2 E2 nE3 E3 E2 = E2 E1 E1 n规则(guz)：记录E3 连续的次数，并在输出下一个E2/E1 之后发送该次数证明(zhngmng)请见文献： Witten, Radford, Neal, Clear

27、y, “Arithmetic Coding for Data Compression” Communications of the ACM, vol. 30, no. 6, pp. 520-540, June 1987. 第28页/共65页第二十八页，共65页。第三种情况第三种情况(qngkung)：E3第29页/共65页第二十九页，共65页。整数整数(zhngsh)实现实现n假设码字长度为n，则nni = 长度为TotalCount（TC） 的序列中字符i出现的次数n累积(lij)计数：CC timestimes0,1000111nn 1times0.5100nTCkCCkFnkCCXkii

28、)()()(1( )(1)(1)(1)( )(1)(1)(1)()(1)kkkkkkXkXkkkulullluFxFxl第30页/共65页第三十页，共65页。整数整数(zhngsh)实现实现nMSB(x) = Most Significant Bit of xnLSB(x) = Least Significant Bit of xnSB(x, i) = ith Significant Bit of xnMSB(x) = SB(x, 1); LSB(x) = SB(x, m)nE3(l, u) = (SB(l, 2) = 1 & SB(u, 2) = 0)第31页/共65页第三十一页，共

29、65页。l=000, u=111, e3_count=0repeat x=get_symbol l=l+ (u-l+1)CC(x-1)/TC / lower bound update u=l+ (u-l+1)CC(x)/TC -1 / upper bound update while(MSB(u)=MSB(l) OR E3(u,l) / MSB(u)=MSB(l)=0 E1 rescaling if(MSB(u)=MSB(l) / MSB(u)=MSB(l)=1 E2 rescaling send(MSB(u) l = (l1)+0 / shift left, set LSB to 0 u =

30、 (u0) send(!MSB(u) / encode accumulated E3 rescalings e3_count- endwhile endif if(E3(u,l) / perform E3 rescaling & remember l = (l1)+0 u = (u 28 x 50/1n= 最小 n = 8 (28 = 256)l=000, u=111, e3_count=0repeat x=get_symbol l=l+ (u-l+1)CC(x-1)/TC u=l+ (u-l+1)CC(x)/TC -1 while(MSB(u)=MSB(l) OR E3(u,l) i

31、f(MSB(u)=MSB(l) send(MSB(u) l = (l1)+0 u = (u0) send(!MSB(u) e3_count- endwhile endif if(E3(u,l) l = (l1)+0 u = (u1)+1 complement MSB(u) and MSB(l) e3_count+ endif endwhileuntil done第33页/共65页第三十三页，共65页。整数整数(zhngsh)编码器：例编码器：例l=000, u=111, e3_count=0repeat x=get_symbol l=l+ (u-l+1)CC(x-1)/TC u=l+ (u-l

32、+1)CC(x)/TC -1 while(MSB(u)=MSB(l) OR E3(u,l) if(MSB(u)=MSB(l) send(MSB(u) l = (l1)+0 u = (u0) send(!MSB(u) e3_count- endwhile endif if(E3(u,l) l = (l1)+0 u = (u1)+1 complement MSB(u) and MSB(l) e3_count+ endif endwhileuntil done2)0(2)0()11111111(255)00000000(0ulfalse32)1 (2)1 (),()()11001011(203150

33、402560)00000000(05002560EuMSBlMSBulInput: 1321Output: Input: -321Output: 1 1)()()11001011(203150502040)10100111(167504120402)2(2)2(uMSBlMSBul第34页/共65页第三十四页，共65页。整数整数(zhngsh)编码器：例编码器：例l=000, u=111, e3_count=0repeat x=get_symbol l=l+ (u-l+1)CC(x-1)/TC u=l+ (u-l+1)CC(x)/TC -1 while(MSB(u)=MSB(l) OR E3(

34、u,l) if(MSB(u)=MSB(l) send(MSB(u) l = (l1)+0 u = (u0) send(!MSB(u) e3_count- endwhile endif if(E3(u,l) l = (l1)+0 u = (u1)+1 complement MSB(u) and MSB(l) e3_count+ endif endwhileuntil doneInput: -21Output: 110 1, 1)()()10010100(1481504114828)10010010(1465040148282)3(2)3(e3_countuMSBlMSBul175)1000000

35、0(11)10010111(281000000001)01001110(151)10010111(11)11001011(78)01001110(01)10101011(22)2(2)2(322)2(22)2(xorxortrueulEule3_count = 1第35页/共65页第三十五页，共65页。整数整数(zhngsh)编码器：例编码器：例l=000, u=111, e3_count=0repeat x=get_symbol l=l+ (u-l+1)CC(x-1)/TC u=l+ (u-l+1)CC(x)/TC -1 while(MSB(u)=MSB(l) OR E3(u,l) if(M

36、SB(u)=MSB(l) send(MSB(u) l = (l1)+0 u = (u0) send(!MSB(u) e3_count- endwhile endif if(E3(u,l) l = (l1)+0 u = (u1)+1 complement MSB(u) and MSB(l) e3_count+ endif endwhileuntil doneInput: -1Output: 1100 0)()(41)00101001(11)10010100(36)00100100(1)10010010(22)3(22)3(uMSBlMSBulInput: -1Output: 11000 0)()

37、(83)01010011(11)00101001(72)01001000(1)00100100(22)3(22)3(uMSBlMSBulInput: -1Output: 110001 1)()(167)10100111(11)01010011(144)10010000(1)01001000(22)3(22)3(uMSBlMSBul第36页/共65页第三十六页，共65页。整数整数(zhngsh)编码器：例编码器：例l=000, u=111, e3_count=0repeat x=get_symbol l=l+ (u-l+1)CC(x-1)/TC u=l+ (u-l+1)CC(x)/TC -1 w

38、hile(MSB(u)=MSB(l) OR E3(u,l) if(MSB(u)=MSB(l) send(MSB(u) l = (l1)+0 u = (u0) send(!MSB(u) e3_count- endwhile endif if(E3(u,l) l = (l1)+0 u = (u1)+1 complement MSB(u) and MSB(l) e3_count+ endif endwhileuntil doneInput: -1Output: 1100010 0)()(79)01001111(11)10100111(32)00100000(1)10010000(22)3(22)3(

39、uMSBlMSBulInput: -1191)10000000(11)10011111(01000000001)01000000(),()(159)10011111(11)01001111(64)01000000(1)00100000(22)3(2)3(322)3(22)3(xorxortrueulEuMSBlMSBule3_count = 1第37页/共65页第三十七页，共65页。整数整数(zhngsh)编码器：例编码器：例l=000, u=111, e3_count=0repeat x=get_symbol l=l+ (u-l+1)CC(x-1)/TC u=l+ (u-l+1)CC(x)/

40、TC -1 while(MSB(u)=MSB(l) OR E3(u,l) if(MSB(u)=MSB(l) send(MSB(u) l = (l1)+0 u = (u0) send(!MSB(u) e3_count- endwhile endif if(E3(u,l) l = (l1)+0 u = (u1)+1 complement MSB(u) and MSB(l) e3_count+ endif endwhileuntil doneInput: -1Output: 1100010 false32)4(2)4(),()()10011000(152150401920)00000000(0500

41、1920EuMSBlMSBulv结束v通常(tngchng)，发送l(4): (00000000)2v但是 e3_count = 1，因此v在发送l(4)的第一个0后发送1最后(zuhu) output: 1100010010000000 第38页/共65页第三十八页，共65页。Initialize l, u, t / t = first n bitsrepeat k=0 while( (t-l+1)TC-1)/(u-l+1) CC(k) k+ x = decode_symbol(k) l=l+ (u-l+1)CC(x-1)/TC u=l+ (u-l+1)CC(x)/TC -1 while(M

42、SB(u)=MSB(l) OR E3(u,l) if(MSB(u)=MSB(l) / Perform E1/E2 rescaling of l,u,t l = (l1)+0 / add 0 to the right of l u = (u1)+1 / add 1 to the right of u t = (t1)+next_bit endif if(E3(u,l) / Perform E3 rescaling of l,u,t l = (l1)+0 u = (u1)+1 t = (t1)+next_bit complement MSB(u), MSB(l), MSB(t) endif end

43、whileuntil done整数整数(zhngsh)解码器解码器第39页/共65页第三十九页，共65页。整数整数(zhngsh)解码器：例解码器：例Initialize l, u, t repeat k=0 while( (t-l+1)CC(x-1)/TC CC(k) k+ x = decode_symbol(k) l=l+ (u-l+1)CC(x-1)/TC u=l+ (u-l+1)CC(x)/TC -1 while(MSB(u)=MSB(l) OR E3(u,l) if(MSB(u)=MSB(l) l = (l1)+0 u = (u1)+1 t = (t1)+next_bit endif

44、 if(E3(u,l) l = (l1)+0 u = (u1)+1 t = (t1)+next_bit complement MSB(u), MSB(l), MSB(t) endif endwhileuntil doneInput: 1100010010000000 222)11000100(196)11111111(255)00000000(0tul11382561501970*xktOutput: 1false322),()()11001011(20350402560)00000000(05002560EuMSBlMSBul33482031501970*xktOutput: 13第40页/

45、共65页第四十页，共65页。整数整数(zhngsh)解码器：例解码器：例Input: 1100010010000000 )()()11001011(203150502040)10100111(16750412040)10001001(222uMSBlMSBultInput: 1100010010000000 true322222),()()10010111(11)11001011()01001110(1)10100111()00010010(EuMSBlMSBultInput: 1100010010000000 falsexorxorxor3222222),()(175)10111001(10

46、00000011)10010111(28)00011100(100000001)01001110(146)10010010(10000000)00010010(EuMSBlMSBultInitialize l, u, t repeat k=0 while( (t-l+1)CC(x-1)/TC CC(k) k+ x = decode_symbol(k) l=l+ (u-l+1)CC(x-1)/TC u=l+ (u-l+1)CC(x)/TC -1 while(MSB(u)=MSB(l) OR E3(u,l) if(MSB(u)=MSB(l) l = (l1)+0 u = (u1)+1 t = (t

47、1)+next_bit endif if(E3(u,l) l = (l1)+0 u = (u1)+1 t = (t1)+next_bit complement MSB(u), MSB(l), MSB(t) endif endwhileuntil done第41页/共65页第四十一页，共65页。整数整数(zhngsh)解码器：例解码器：例2240) 128175(150) 128146*xktOutput: 1322228148 40 50146(10010010)28148 41 501148(10010100)( )( )5luMSB lMSB u ，共 次v结束v已解码接收(jishu)到

48、了预定数目的字符，或v接收(jishu)到EOTInitialize l, u, t repeat k=0 while( (t-l+1)CC(x-1)/TC CC(k) k+ x = decode_symbol(k) l=l+ (u-l+1)CC(x-1)/TC u=l+ (u-l+1)CC(x)/TC -1 while(MSB(u)=MSB(l) OR E3(u,l) if(MSB(u)=MSB(l) l = (l1)+0 u = (u1)+1 t = (t1)+next_bit endif if(E3(u,l) l = (l1)+0 u = (u1)+1 t = (t1)+next_bit

49、 complement MSB(u), MSB(l), MSB(t) endif endwhileuntil done22*(01000000)(10011111)0 1tlutx 最后，Output: 1321第42页/共65页第四十二页，共65页。算术算术(sunsh)编码编码 vs. Huffman编码编码nn = 序列长度n平均码长：n算术：n扩展(kuzhn)Huffman：n观察n二者的积渐近性质相同nHuffman有一个微小的边际n扩展(kuzhn)的Huffman要求巨大数量的存储和编码mnn而算术编码不用n 实际应用中可以对算术编码假设较大的长度n 但 Huffman不可n

50、我们期望算术编码表现更好（除了当概率为2的整数次幂的情况）()( )2AH XlH xn()( ) 1HH XlH xn第43页/共65页第四十三页，共65页。算术算术(sunsh)编码编码 vs. Huffman编码编码n增益为字母表大小和分布的函数n较大的字母表（通常）较适合 Huffmann不均衡的分布更适合算术编码n很容易(rngy)将算术编码扩展到多个编码器nQM编码器n很容易(rngy)将算术编码适应到统计变化模型（自适应模型、上下文模型）n不必对树重新排序n可以将建模与编码分开第44页/共65页第四十四页，共65页。应用应用(yngyng)：图像压缩：图像压缩自适应(shyng)

51、算术编码：对像素值自适应算术编码(bin m)：对像素差分第45页/共65页第四十五页，共65页。自适应自适应(shyng)算术编码算术编码n统计编码技术需要(xyo)利用信源符号的概率，获得这个概率的过程称为建模。不同准确度（通常也是不同复杂度）的模型会影响算术编码的效率。n建模的方式：n静态建模：在编码过程中信源符号的概率不变。但一般来说事先知道精确的信源概率是很难的，而且是不切实际的。n自适应动态建模：信源符号的概率根据编码时符号出现的频繁程度动态地进行修改。当压缩消息时，我们不能期待一个算术编码器获得最大的效率，所能做的最有效的方法是在编码过程中估算概率。n算术编码很容易与自适应建模相

52、结合。第46页/共65页第四十六页，共65页。自适应自适应(shyng)算术编码算术编码n自适应算术编码：n在编码之前，假设每个信源符号的频率相等（如都等于1），并计算累积频率n从输入流中读入一个字符，并对该符号进行算术编码n更新该符号的频率，并更新累积频率n由于在解码之前，解码器不知道(zh do)是哪个信源符号，所以概率更新应该在解码之后进行n对应的，编码器也应在编码后进行概率更新第47页/共65页第四十七页，共65页。自适应自适应(shyng)算术编码算术编码n为了(wi le)提高解码器的搜索效率，信源符号的频率、累积频率表按符号出现频率降序排列n在自适应算术编码中，可以用平衡二叉树来

53、快速实现对频率和累积频率的更新n平衡二叉树可用数组实现（类似Huffman编码中的堆）n最可能出现的符号安排在根附近，从而平均搜索的次数最小n详见数据压缩原理与应用第2.15节第48页/共65页第四十八页，共65页。自适应自适应(shyng)算术编码算术编码n例：信源符号及其出现(chxin)频率为：数组下标：1 2 3 4 5 6 7 8 9 10 信源符号：频率：辅助变量：辅助变量为该节点(ji din)左子树的总计数，用于计算累积频率例：计算a6 的累积频率得到从节点(ji din)10（a6）到根节点(ji din)的路径： 10 5 2 1 a6 a1 a2a8 2. 令 af=0,

54、 沿树枝从根节点(ji din)向节点(ji din)10（a6） 1) 取根节点(ji din)的左分支到子节点(ji din)a2，af不变 2) 取节点(ji din)a2的右分支到到节点(ji din)a1 ， 将该节点(ji din)的两个数值加到af af = af + 12 + 16 = 28 2)取节点(ji din)a1的左分支到到节点(ji din)a6后 ，将其左子树计数0加至af，最后af=28为累积频率区间的起点第49页/共65页第四十九页，共65页。自适应算术自适应算术(sunsh)编码编码n 数组下标：1 2 3 4 5 6 7 8 9 10 信源符号：频率：辅助

55、变量：频率(pnl)、累积频率(pnl)表：第50页/共65页第五十页，共65页。自适应算术自适应算术(sunsh)编码编码n在平衡二叉树上更新(gngxn)频率：n例：读进符号a9，将其频率计数从12变为13n在数组中寻找符号a9的左边、离a9最远的、频率小于a9的元素，同时更新(gngxn)左子树计数值第51页/共65页第五十一页，共65页。总结总结(zngji)n直接对序列(xli)进行编码（不是码字的串联）：非分组码n可证明是唯一可译码n渐近接近熵界n对不均衡的分布，比Huffman更有效n只产生必要的码字n但是实现更复杂n允许将建模和编码分开，容易与自适应模型和上下文模型结合n对错误

56、很敏感，如果有一位发生错误就会导致整个消息译码错误第52页/共65页第五十二页，共65页。下节课内容下节课内容(nirng)n作业(zuy)：nSayood 3rd, pp.114-115n必做：5, 6, 7, 8n下节课内容：nJPEG、JPEG2000和JBIG中的算术编码： QM编码器第53页/共65页第五十三页，共65页。HistorynThe idea of encoding by using cumulative probability in some ordering, and decoding by comparison of magnitude of binary frac

57、tion was introduced in Shannons celebrated paper 1948. nThe recursive implementation of arithmetic coding was devised by Elias (another member in Fanos first information theory class at MIT). This unpublished result was first introduced by Abramson as a note in his book on information theory and cod

58、ing 1963. nThe result was further developed by Jelinek in his book on information theory 1968. nThe growing precision problem prevented arithmetic coding from practical usage, however. The proposal of using finite precision arithmetic was made independently by Pasco 1976 and Rissanen 1976.第54页/共65页第

59、五十四页，共65页。HistorynPractical arithmetic coding was developed by several independent groups Rissanen 1979, Rubin 1979, Guazzo 1980. nA well-known tutorial paper on arithmetic coding appeared in Langdon 1984. nThe tremendous efforts made in IBM lead to a new form of adaptive binary arithmetic coding known as the Q-coder Pennebaker 1988. nBased on the Q-coder, the activities of JPEG and JBIG combined the best features of the various existing arithmetic coders and developed the binary arithmetic coding procedure known as