四章算术编码ppt课件

1、:0.10.9XabP X0ab1a=0, b=110ab c01l = 1.222/2 = 0.611冗余 = 0.276 bits/symbol27%n但此时|alphabet| = 38 = 6561 ! iP XiP a 11iiXikkFiP XkP a 00,.1,1XXXFmiiFiF 11,111XXXXXXXXFjFjFkFkFkFkFkFkv将0, 1)分为m个区间：v对公平掷骰子的例子：1, 2, 3, 4, 5, 66.161kforkXP iXPiFiXPkXPaTXikiX2112111 25. 022112XPXPTX 75. 0521541XPkXPTkX (

2、):12inXiiTPPy y xxyxxy 469. 07251321121113xPxPxPTXv留意：v为了产生13的标识，我们不用对产生其他标识v但是，为了产生长度为n的字符串的标识，我们必需知道比其短的字符串的概率v这与产生一切的码字一样繁重！v应该想方法来防止此事(2)32(11).(16)(21).(26)(31)(32)XFPPPPPPxxxxxx (2)32(11).(16)(21).(26)(31)(32)XFPPPPPPxxxxxx6661212112111,iiiPkiP xk xiP xkP xiP xkwherex xxx(2)1132(1)(2)(31)(32)(

3、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) 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)

4、(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 ( )( )2nnXulTx( )(1)(1)(1)( )(1)(1)(1)()(1)kkkkkkXkXkkkulullluFxFxl只需知道信源的cdf，即信源的概率模型算术编码：编码和解码过程都只涉及算术运算加、减、乘、除3, 1)(, 1)3(,82. 0)2(, 8 . 0) 1 (, 0, 0)(kkFFFFkkFXXXXX1, 0)0()0(ul8 . 0) 1 (0

5、)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)()(1)kkkkkkXkXkkkululllu

6、FxFxl3, 1)(, 1)3(,82. 0)2(, 8 . 0) 1 (, 0, 0)(kkFFFFkkFXXXXX772352. 01321 XTvAlgorithmvInitialize l(0) = 0, u(0) = 1.vCompute t*=(tag-l(k-1)/(u(k-1)-l(k-1).vFind the xk: FX(xk-1) t* FX(xk).vUpdate u(k), l(k)vIf done-exit, otherwise goto 1.) 1()()1()1()1()()1()1()1()(kXkkkkkXkkkkxFlullxFlulu 8 .0)1 (

7、0)0()1 (8 .00)0(772352.0010772352.0)0()0()0()1()0()0()0()1(*XXXXFluluFlullFtFt 8 .0)3(656.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.07740

8、8.07712.0772352.0*XXFtFt1131321321 1log1( )lPxx ( )1 ( )log1( )1 ( ) log1 1( ) ( )log( )2( ) 22AnlPlPPPPPPPH XnH X xxxxxxxxx 2 2 nAAHnH XlnH XXlH Xn算术编码的效率高：当信源符号序列很长，平均码长接近信源的熵nn与编码器坚持同步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

9、,)0,0.5),)0.5,1)XXllulFululFluluget next symbolInput: 1321Output: 6 . 0)5 . 08 . 0(2312. 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: 1Input: -21Output: 1154816. 0)2(5424. 0) 1 ()2()2()2()3()2()2()2()3(XXFluluFlull6 . 0,312. 0)

10、2()2(ul09632. 05 . 054816. 020848. 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: 1100077056. 038528. 026784. 03392. 02)3()3(ulInput: -1Output: 11000154112. 0)5 . 077056. 0(23568. 0)5 . 0

11、6784. 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留意：0.1100011 = 2-1+2-2+2-6+2-7= 0.7734375 0.7712,0.77408n如何终了？ )3(182.0)2(9570.008 .00765625.0*XXFtFt8 .0)3(656.0)2()1()1()1()2()1()1()1

12、()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(XXFluluFlull09632. 05 . 054816. 020848. 05 . 05424. 02)3

13、()3(ulInput: -001100000 (左移)Input: -0001100000 (左移)(1)(1)0(10)000(10)0.80.8lu19264. 009632. 021696. 00848. 02)3()3(ulInput: -01100000 (左移)38528. 019264. 023392. 01696. 02)3()3(ulInput: -1100000 (左移)77056. 038528. 026784. 03392. 02)3()3(ulInput: -100000 (左移)504256. 0) 1 ()3568. 054112. 0(3568. 03568.

14、 0)0()3568. 054112. 0(3568. 0)4()4(XXFuFlInput: -100000*2*1000000.5,(0)00.8(1)XXtFtFOutput: 1321证明请见文献： Witten, Radford, Neal, Cleary, “Arithmetic Coding for Data Compression Communications of the ACM, vol. 30, no. 6, pp. 520-540, June 1987. timestimes0,1000111nn 1times0.5100nTCkCCkFnkCCXkii)()()(1(

15、 )(1)(1)(1)( )(1)(1)(1)1(1)1()1nnnnnnnnnnllulCC xTCululCC xTC( )(1)(1)(1)( )(1)(1)(1)()(1)kkkkkkXkXkkkulullluFxFxll=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 re

16、scaling 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 = (u0) send(!MSB(u) / encode accumulated E3 rescalings e3_count- endwhile endif if(E3(u,l) / perform E3 rescaling & remember l = (l1)+0 u = (u1)+1 complement MSB(u) and MSB(l) e3_count+ en

17、dif endwhileuntil donel=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(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

18、+ endif endwhileuntil donel=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(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_c

19、ount+ endif endwhileuntil done2)0(2)0()11111111(255)00000000(0ulfalse32)1(2)1(),()()11001011(203150402560)00000000(05002560EuMSBlMSBulInput: 1321Output: Input: -321Output: 1 1)()()11001011(203150502040)10100111(167504120402)2(2)2(uMSBlMSBull=000, u=111, e3_count=0repeat x=get_symbol l=l+ (u-l+1)CC(x

20、-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) 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)10

21、010010(1465040148282)3(2)3(e3_countuMSBlMSBul175)10000000(11)10010111(281000000001)01001110(151)10010111(11)11001011(78)01001110(01)10101011(22)2(2)2(322)2(22)2(xorxortrueulEule3_count = 1l=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

22、 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: 1100 0)()(41)00101001(11)10010100(36)00100100(1)10010010(22)3(22)3(uMSBlMSBulInput: -1Outpu

23、t: 11000 0)()(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(uMSBlMSBull=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)

24、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(uMSBlMSBulInput: -1191)1000000

25、0(11)10011111(01000000001)01000000(),()(159)10011111(11)01001111(64)01000000(1)00100000(22)3(2)3(322)3(22)3(xorxortrueulEuMSBlMSBule3_count = 1l=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(MSB(u)=MSB(l) send(MSB(u) l = (l1

26、)+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(05001920EuMSBlMSBulv终了v通常，发送l(4): (00000000)2v但是 e3_count = 1，因此v在发送l(4)的第一个0

27、后发送1最后 output: 1100010010000000 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(MSB(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 o

28、f 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 endwhileuntil doneInitialize 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

29、+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 complement MSB(u), MSB(l), MSB(t) endif endwhileuntil doneInput: 1100010010000000 222)11000100(196)11111111(255)000000

30、00(0tul11382561501970*xktOutput: 1false322),()()11001011(20350402560)00000000(05002560EuMSBlMSBul33482031501970*xktOutput: 13Input: 1100010010000000 )()()11001011(203150502040)10100111(16750412040)10001001(222uMSBlMSBultInput: 1100010010000000 true322222),()()10010111(11)11001011()01001110(1)1010011

31、1()00010010(EuMSBlMSBultInput: 1100010010000000 falsexorxorxor3222222),()(175)10111001(1000000011)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

32、)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 complement MSB(u), MSB(l), MSB(t) endif endwhileuntil done2240) 128175(150) 128146*xktOutput: 1322228148 40 50146(10010010)28148 41 501148(10010100)( )( )5luMSB lMSB u ，共 次v终了v已解码接纳到了预定数目的字符，或v接纳到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)/