第四章算術(shù)編碼

1、第四章：算術(shù)編碼n算術(shù)編碼：越來越流行（在很多標(biāo)準(zhǔn)中被采用）n適合的場合：n小字母表：如二進(jìn)制信源n概率分布不均衡n建模與編碼分開n內(nèi)容：n算術(shù)編碼的基本思想n一些性質(zhì)n實(shí)現(xiàn)n有限精度：區(qū)間縮放（浮點(diǎn)數(shù)/整數(shù)實(shí)現(xiàn)）n計(jì)算復(fù)雜度：用移位代替乘法二進(jìn)制編碼n自適應(yīng)模型nQM編碼器：自適應(yīng)二進(jìn)制編碼回顧： Huffman編碼n例1：信源的符號數(shù)目很少n :0.10.9XabP X0ab1a=0, b=1回顧：擴(kuò)展的Huffman編碼n例2：信源的符號的概率嚴(yán)重不對稱：nA = a, b, c, P(a) = 0.95, P(b) = 0.02, P(c) = 0.03nH = 0.335 bits/

2、symbolnHuffman編碼：a0b11c10nl = 1.05 bits/symboln冗余（Redundancy） = l - H = 0.715 bits/sym (213%!)n問題：能做得更好嗎？10ab c01回顧：擴(kuò)展的Huffman編碼n基本思想：n考慮對兩個字母序列而不是單個字母編碼l = 1.222/2 = 0.611冗余 = 0.276 bits/symbol（27%）回顧：擴(kuò)展的Huffman編碼n該思想還可以繼續(xù)擴(kuò)展n考慮長度為n的所有可能的mn 序列 (已做了32)n理論上：考慮更長的序列能提高編碼性能n實(shí)際上：n字母表的指數(shù)增長將使得這不現(xiàn)實(shí)n例如：對長度為3

3、的ASCII序列：2563 = 224 = 16Mn需要對長度為n的所有序列產(chǎn)生碼本n很多序列的概率可能為0n分布嚴(yán)重不對稱是真正的大問題：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當(dāng)n = 8時編碼性能才變得可接受n但此時|alphabet| = 38 = 6561 !算術(shù)編碼（Arithmetic Coding）n算術(shù)編碼：從另一種角度對很長的信源符號序列進(jìn)行有效編碼n對整個序列信源符號串產(chǎn)生一個唯一的標(biāo)識（ tag ）n直接對序列進(jìn)行

4、編碼（不是碼字的串聯(lián)）：非分組碼n不用對該長度所有可能的序列編碼n標(biāo)識是0,1)之間的一個數(shù)（二進(jìn)制小數(shù)，可作為序列的二進(jìn)制編碼）概率復(fù)習(xí) n隨機(jī)變量：n將試驗(yàn)的輸出映射到實(shí)數(shù)n用數(shù)字代替符號nX(ai) = i, 其中 ai A (A = ai, i = 1.n)n給定信源的概率模型Pn概率密度函數(shù)（probability density function, pdf）n累積密度函數(shù)（cumulative density function, cdf） iP XiP a 11iiXikkFiP XkP a產(chǎn)生標(biāo)識n定義一一映射：nak FX(k-1), FX(k), k = 1.m, FX(0)

5、 = 0nFX(k-1), FX(k)區(qū)間內(nèi)的任何數(shù)字表示 akn對2字母序列ak aj編碼n對ak ，選擇FX(k-1), FX(k)n然后將該區(qū)間按比例分割并選取第j個區(qū)間： 00,.1,1XXXFmiiFiF 11,111XXXXXXXXFjFjFkFkFkFkFkFkv將0, 1)分為m個區(qū)間：產(chǎn)生標(biāo)識：例n考慮對a1a2a3編碼：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映射成實(shí)數(shù)nA = a1, a2, , amv對公平擲骰子的例

6、子：1, 2, 3, 4, 5, 66.161kforkXP iXPiFiXPkXPaTXikiX2112111 25. 022112XPXPTX 75. 0521541XPkXPTkX詞典順序（ Lexicographic order ）n字符串的詞典順序：n其中 表示“在字母順序中，y在x的前面”nn 為序列的長度 ( ):12inXiiTPPy y xxyxxy 詞典順序：例n考慮兩輪連續(xù)的骰子：n輸出 = 11, 12, , 16, 21, 22, , 26, , 61, 62, , 66 469. 07251321121113xPxPxPTXv注意：為了產(chǎn)生13的標(biāo)識，我們不必對產(chǎn)生

7、其他標(biāo)識=但是，為了產(chǎn)生長度為n的字符串的標(biāo)識，我們必須知道比其短的字符串的概率 這與產(chǎn)生所有的碼字一樣繁重！應(yīng)該想辦法來避免此事區(qū)間構(gòu)造n觀察n包含某個標(biāo)識的區(qū)間與所有其他標(biāo)識的區(qū)間不相交n基本思想n遞歸：將序列的下/上界視為更短序列的界的函數(shù)n上述骰子的例子：n考慮序列：3 2 2 n令u(n), l(n) 為長度為n序列的上界和下界，則u(1) = FX(3), l(1) = FX(2)u(2) = FX(2)(32), l(2) = FX(2)(31) (2)32(11).(16)(21).(26)(31)(32)XFPPPPPPxxxxxx區(qū)間構(gòu)造 (2)32(11).(16)(21

8、).(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區(qū)間構(gòu)造 ) 1 ()2()3()2(31)2(XXXXXFFFFF) 1 ()1()1()1()2(XFlull()()(3)

9、( )(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產(chǎn)生標(biāo)識n通常，對任意序列x = x1x2xn ( )( )2nnXulTx( )(1)(1)(1)( )(1)(1)(1)()(1)kkkkkkXkXkkkulullluFx

10、Fxl只需知道信源的cdf，即信源的概率模型算術(shù)編碼：編碼和解碼過程都只涉及算術(shù)運(yùn)算（加、減、乘、除）產(chǎn)生標(biāo)識：例n考慮隨機(jī)變量X(ai) = i n對序列1 3 2 1編碼：3, 1)(, 1)3(,82. 0)2(, 8 . 0) 1 (, 0, 0)(kkFFFFkkFXXXXX1, 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()

11、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)kkkkkkXkXkkkulullluFxFxl解碼標(biāo)識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)

12、 t* FX(xk).3. Update u(n), l(n)4. If done-exit, otherwise goto 1.解碼：例3, 1)(, 1)3(,82. 0)2(, 8 . 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

13、)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.077408

14、.07712.0772352.0*XXFtFt1131321321算術(shù)編碼的唯一性和效率n上述產(chǎn)生的標(biāo)識可以唯一表示一個序列，這意味著該標(biāo)識的二進(jìn)制表示為序列的唯一二進(jìn)制編碼n但二進(jìn)制表示的精度可以是無限長：保證唯一性但不夠有效n為了保證有效性，可以截斷二進(jìn)制表示，但如何保證唯一性？n答案：為了保證唯一性和有效性，需取小數(shù)點(diǎn)后l位數(shù)字作為信源序列的碼字，其中n注意：P(x)為最后區(qū)間的寬度，也是該符號串的概率n符合概率匹配原則：出現(xiàn)概率較大的符號取較短的碼字，而對出現(xiàn)概率較小的符號取較長的碼字 1log1( )lPxx算術(shù)編碼的唯一性和效率n長度為n的序列的算術(shù)編碼的平均碼長為： ( )1 (

15、 )log1( )1 ( ) log1 1( ) ( )log( )2( ) 22AnlPlPPPPPPPH XnH X xxxxxxxxx 2 2 nAAHnH XlnH XXlH Xn算術(shù)編碼的效率高：當(dāng)信源符號序列很長，平均碼長接近信源的熵實(shí)現(xiàn)n迄今為止 0, 1);E1(x) = 2xnE2: 0. 5,1) = 0, 1);E2(x) = 2(x-0.5)n注意：在縮放過程中我們丟失了最高位n但這不成問題我們已經(jīng)發(fā)送出去了n解碼器n根據(jù)0/1比特并相應(yīng)縮放n與編碼器保持同步標(biāo)識產(chǎn)生：帶縮放的例子n考慮隨機(jī)變量X(ai) = i n對序列1 3 2 1編碼：3, 1)(, 1)3(,8

16、2. 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(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: -321Ou

17、tput: 1標(biāo)識產(chǎn)生：帶縮放的例子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. 05 . 05424. 02)3()3(ulInput: -1Output: 11019264. 009632. 021696. 00848. 02)3()3(ulInput: -1Output: 110038528. 019264. 023392. 01696. 02)3()3(ulInput: -1Out

18、put: 11000標(biāo)識產(chǎn)生：帶縮放的例子nEOT:nl(n),u(n)區(qū)間內(nèi)的任何一個數(shù)字n在此選 0.510 = 0.1277056. 038528. 026784. 03392. 02)3()3(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: -1Outp

19、ut: 110001Output: 11000110v注意：0.1100011 = 2-1+2-2+2-6+2-7= 0.7734375 0.7712,0.77408增量式標(biāo)識解碼n我們需要增量式解碼n如：網(wǎng)絡(luò)傳輸n問題n如何開始？n必須有足夠的信息，可以對第一個字符無歧義解碼 接收到的比特數(shù)應(yīng)比最小標(biāo)識對應(yīng)的區(qū)間更小n怎樣繼續(xù)？n一旦有一個非歧義的開始，只要模擬編碼器即可n如何結(jié)束？標(biāo)識解碼：例n假設(shè)碼字長為6n輸入：110001100000n0.1100012 = 0.76562510n第1位：1Output: 1 )3(182.0)2(9570.008 .00765625.0*XXFtF

20、t8 .0)3(656.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(XXFluluFlull09632. 0

21、5 . 054816. 020848. 05 . 05424. 02)3()3(ulInput: -001100000 (左移)Input: -0001100000 (左移)(1)(1)0(10)000(10)0.80.8lu此時解碼最后一個符號標(biāo)識解碼：例19264. 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: -10

22、0000 (左移)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第三種情況：E3n回憶三種情況1.l(n), u(n) 0, 0.5): E1: 0, 0.5) = 0, 1); E1(x) = 2x2.l(n), u(n) 0.5, 1): E2: 0. 5, 1) = 0, 1); E2(x) = 2(x-0.5)3.l(n) 0, 0.5), u(n) 0.5

23、, 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規(guī)則：記錄E3 連續(xù)的次數(shù)，并在輸出下一個E2/E1 之后發(fā)送該次數(shù)證明請見文獻(xiàn)： Witten, Radford, Neal, Cleary, “Arithmetic Coding for Data Compression” Communications of the ACM, vol. 30, no. 6, pp. 5

24、20-540, June 1987. 第三種情況：E3整數(shù)實(shí)現(xiàn)n假設(shè)碼字長度為n，則nni = 長度為TotalCount（TC） 的序列中字符i出現(xiàn)的次數(shù)n累積計(jì)數(shù)：CC timestimes0,1000111nn 1times0.5100nTCkCCkFnkCCXkii)()()(1( )(1)(1)(1)( )(1)(1)(1)()(1)kkkkkkXkXkkkulullluFxFxl整數(shù)實(shí)現(xiàn)nMSB(x) = Most Significant Bit of xnLSB(x) = Least Significant Bit of xnSB(x, i) = ith Significant

25、Bit of xnMSB(x) = SB(x, 1); LSB(x) = SB(x, m)nE3(l, u) = (SB(l, 2) = 1 & SB(u, 2) = 0)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) /

26、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 = (u 28 x 50/1= 最小 n = 8 (28 = 256)l=000, u=111, e3_count=0repeat x=get_symbol l=

27、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+ endif endwhileuntil done整數(shù)編碼器：例l=000, u=111, e3_count=0repeat x=g

28、et_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+ endif endwhileuntil done2)0(2)0()11111111(255)0000000

29、0(0ulfalse32)1(2)1(),()()11001011(203150402560)00000000(05002560EuMSBlMSBulInput: 1321Output: Input: -321Output: 1 1)()()11001011(203150502040)10100111(167504120402)2(2)2(uMSBlMSBul整數(shù)編碼器：例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) O

30、R 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)10010010(1465040148282)3(2)3(e3_countuMSBlMSBul175)10

31、000000(11)10010111(281000000001)01001110(151)10010111(11)11001011(78)01001110(01)10101011(22)2(2)2(322)2(22)2(xorxortrueulEule3_count = 1整數(shù)編碼器：例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(MSB(u)=MSB(l) send(MSB(u) l = (

32、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)()(83)01010011(11)00101001(72)01

33、001000(1)00100100(22)3(22)3(uMSBlMSBulInput: -1Output: 110001 1)()(167)10100111(11)01010011(144)10010000(1)01001000(22)3(22)3(uMSBlMSBul整數(shù)編碼器：例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(MSB(u)=MSB(l) send(MSB(u) l = (l

34、1)+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)10000000(11)10011111(01000000001)01000000(

35、),()(159)10011111(11)01001111(64)01000000(1)00100000(22)3(2)3(322)3(22)3(xorxortrueulEuMSBlMSBule3_count = 1整數(shù)編碼器：例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(MSB(u)=MSB(l) send(MSB(u) l = (l1)+0 u = (u0) send(!MSB(u) e

36、3_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結(jié)束通常，發(fā)送l(4): (00000000)2但是 e3_count = 1，因此在發(fā)送l(4)的第一個0后發(fā)送1最后 output: 110001001000000

37、0 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 of l u = (u1)+1 / add 1 to the

38、 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 done整數(shù)解碼器整數(shù)解碼器：例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

39、+ (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)00000000(0tul113825615

40、01970*xktOutput: 1false322),()()11001011(20350402560)00000000(05002560EuMSBlMSBul33482031501970*xktOutput: 13整數(shù)解碼器：例Input: 1100010010000000 )()()11001011(203150502040)10100111(16750412040)10001001(222uMSBlMSBultInput: 1100010010000000 true322222),()()10010111(11)11001011()01001110(1)10100111()000100

41、10(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)CC(x)/TC

42、 -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 done整數(shù)解碼器：例2240) 128175(150) 128146*xktOutput: 1322228148 40 50146(10010010)28148 41 501148(10010

43、100)( )( )5luMSB lMSB u ，共 次v結(jié)束已解碼接收到了預(yù)定數(shù)目的字符，或接收到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

44、 u = (u1)+1 t = (t1)+next_bit complement MSB(u), MSB(l), MSB(t) endif endwhileuntil done22*(01000000)(10011111)0 1tlutx 最后，Output: 1321算術(shù)編碼 vs. Huffman編碼nn = 序列長度n平均碼長：n算術(shù)：n擴(kuò)展Huffman：n觀察n二者的積漸近性質(zhì)相同nHuffman有一個微小的邊際n擴(kuò)展的Huffman要求巨大數(shù)量的存儲和編碼mnn而算術(shù)編碼不用 實(shí)際應(yīng)用中可以對算術(shù)編碼假設(shè)較大的長度n 但 Huffman不可 我們期望算術(shù)編碼表現(xiàn)更好（除了當(dāng)概率為2

45、的整數(shù)次冪的情況）()( )2AH XlH xn()( ) 1HH XlH xn算術(shù)編碼 vs. Huffman編碼n增益為字母表大小和分布的函數(shù)n較大的字母表（通常）較適合 Huffmann不均衡的分布更適合算術(shù)編碼n很容易將算術(shù)編碼擴(kuò)展到多個編碼器nQM編碼器n很容易將算術(shù)編碼適應(yīng)到統(tǒng)計(jì)變化模型（自適應(yīng)模型、上下文模型）n不必對樹重新排序n可以將建模與編碼分開應(yīng)用：圖像壓縮自適應(yīng)算術(shù)編碼：對像素值自適應(yīng)算術(shù)編碼：對像素差分自適應(yīng)算術(shù)編碼n統(tǒng)計(jì)編碼技術(shù)需要利用信源符號的概率，獲得這個概率的過程稱為建模。不同準(zhǔn)確度（通常也是不同復(fù)雜度）的模型會影響算術(shù)編碼的效率。n建模的方式：n靜態(tài)建模：在編

46、碼過程中信源符號的概率不變。但一般來說事先知道精確的信源概率是很難的，而且是不切實(shí)際的。n自適應(yīng)動態(tài)建模：信源符號的概率根據(jù)編碼時符號出現(xiàn)的頻繁程度動態(tài)地進(jìn)行修改。當(dāng)壓縮消息時，我們不能期待一個算術(shù)編碼器獲得最大的效率，所能做的最有效的方法是在編碼過程中估算概率。n算術(shù)編碼很容易與自適應(yīng)建模相結(jié)合。自適應(yīng)算術(shù)編碼n自適應(yīng)算術(shù)編碼：n在編碼之前，假設(shè)每個信源符號的頻率相等（如都等于1），并計(jì)算累積頻率n從輸入流中讀入一個字符，并對該符號進(jìn)行算術(shù)編碼n更新該符號的頻率，并更新累積頻率n由于在解碼之前，解碼器不知道是哪個信源符號，所以概率更新應(yīng)該在解碼之后進(jìn)行n對應(yīng)的，編碼器也應(yīng)在編碼后進(jìn)行概率更新

47、自適應(yīng)算術(shù)編碼n為了提高解碼器的搜索效率，信源符號的頻率、累積頻率表按符號出現(xiàn)頻率降序排列n在自適應(yīng)算術(shù)編碼中，可以用平衡二叉樹來快速實(shí)現(xiàn)對頻率和累積頻率的更新n平衡二叉樹可用數(shù)組實(shí)現(xiàn)（類似Huffman編碼中的堆）n最可能出現(xiàn)的符號安排在根附近，從而平均搜索的次數(shù)最小n詳見數(shù)據(jù)壓縮原理與應(yīng)用第2.15節(jié)自適應(yīng)算術(shù)編碼n例：信源符號及其出現(xiàn)頻率為：數(shù)組下標(biāo)：1 2 3 4 5 6 7 8 9 10 信源符號：頻率：輔助變量：輔助變量為該節(jié)點(diǎn)左子樹的總計(jì)數(shù)，用于計(jì)算累積頻率例：計(jì)算a6 的累積頻率1.得到從節(jié)點(diǎn)10（a6）到根節(jié)點(diǎn)的路徑： 10 5 2 1 a6 a1 a2a8 2. 令 af=

48、0, 沿樹枝從根節(jié)點(diǎn)向節(jié)點(diǎn)10（a6） 1) 取根節(jié)點(diǎn)的左分支到子節(jié)點(diǎn)a2，af不變 2) 取節(jié)點(diǎn)a2的右分支到到節(jié)點(diǎn)a1 ， 將該節(jié)點(diǎn)的兩個數(shù)值加到af af = af + 12 + 16 = 28 2)取節(jié)點(diǎn)a1的左分支到到節(jié)點(diǎn)a6后 ，將其左子樹計(jì)數(shù)0加至af，最后af=28為累積頻率區(qū)間的起點(diǎn)自適應(yīng)算術(shù)編碼n 數(shù)組下標(biāo)：1 2 3 4 5 6 7 8 9 10 信源符號：頻率：輔助變量：頻率、累積頻率表：自適應(yīng)算術(shù)編碼n在平衡二叉樹上更新頻率：n例：讀進(jìn)符號a9，將其頻率計(jì)數(shù)從12變?yōu)?3n在數(shù)組中尋找符號a9的左邊、離a9最遠(yuǎn)的、頻率小于a9的元素，同時更新左子樹計(jì)數(shù)值總結(jié)n直接對序

49、列進(jìn)行編碼（不是碼字的串聯(lián)）：非分組碼n可證明是唯一可譯碼n漸近接近熵界n對不均衡的分布，比Huffman更有效n只產(chǎn)生必要的碼字n但是實(shí)現(xiàn)更復(fù)雜n允許將建模和編碼分開，容易與自適應(yīng)模型和上下文模型結(jié)合n對錯誤很敏感，如果有一位發(fā)生錯誤就會導(dǎo)致整個消息譯碼錯誤下節(jié)課內(nèi)容n作業(yè)：nSayood 3rd, pp.114-115n必做：5, 6, 7, 8n下節(jié)課內(nèi)容：HistorynThe idea of encoding by using cumulative probability in some ordering, and decoding by comparison of magnitud

50、e of binary fraction 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 informatio

51、n theory and coding 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.HistorynPractical arithmetic coding was developed by several independent groups Rissanen 1979, Rubin 1979, Guazzo 1980. nA well-known tutorial paper on ar