第9講——算術(shù)編碼與LZ編碼2014

1、算術(shù)編碼算術(shù)編碼前面所討論的無失真編碼，都是建立在信源符號與碼字一前面所討論的無失真編碼，都是建立在信源符號與碼字一一對應(yīng)的基礎(chǔ)上，這種編碼方法通常稱為一對應(yīng)的基礎(chǔ)上，這種編碼方法通常稱為塊碼或分組碼塊碼或分組碼，此時(shí)信源符號一般是此時(shí)信源符號一般是多元多元的。的。如果要對二元序列進(jìn)行編碼，則需采用合并信源符號方法，如果要對二元序列進(jìn)行編碼，則需采用合并信源符號方法，把二元序列轉(zhuǎn)換成多值符號，轉(zhuǎn)換時(shí)二元符號之間的相關(guān)把二元序列轉(zhuǎn)換成多值符號，轉(zhuǎn)換時(shí)二元符號之間的相關(guān)性不予考慮，轉(zhuǎn)換后這些多值符號之間的相關(guān)性也不予考性不予考慮，轉(zhuǎn)換后這些多值符號之間的相關(guān)性也不予考慮。這就使信源編碼的匹配原則不

2、能充分滿足，編碼效率慮。這就使信源編碼的匹配原則不能充分滿足，編碼效率一般不高。一般不高。為了克服這種局限性，需要跳出分組碼范疇，為了克服這種局限性，需要跳出分組碼范疇，從整個(gè)符號從整個(gè)符號序列出發(fā)，采用遞推形式進(jìn)行編碼序列出發(fā)，采用遞推形式進(jìn)行編碼。 從整個(gè)符號序列出發(fā)，根據(jù)各信源序列的概率將信源從整個(gè)符號序列出發(fā)，根據(jù)各信源序列的概率將信源序列映射到序列映射到0,1) 區(qū)間上，然后選取區(qū)間內(nèi)的一點(diǎn)（也區(qū)間上，然后選取區(qū)間內(nèi)的一點(diǎn)（也就是一個(gè)二進(jìn)制的小數(shù)）來表示信源序列。就是一個(gè)二進(jìn)制的小數(shù)）來表示信源序列。算術(shù)編碼基本思想算術(shù)編碼基本思想 設(shè)信源字母表為設(shè)信源字母表為a1, a2,概率概率

3、p(a1)=0.6, p(a2)=0.4，將將0,1按概率比例分為區(qū)間按概率比例分為區(qū)間0,0.6,0.6,l。p(a1)p(a2)0 0.6 10 0.36 0.6 0.84 1p(a1a1)p(a1a2)p(a2a1) p(a2a2)隨著序列的長度不斷增隨著序列的長度不斷增加加,C所在區(qū)間的長度就所在區(qū)間的長度就越短越短,精確地確定精確地確定C的位的位置需要碼長也不斷增加置需要碼長也不斷增加 設(shè)信源符號集設(shè)信源符號集A=a1,a2,an, 其相應(yīng)概率分布為其相應(yīng)概率分布為pi, pi 0 (i=1,2, ,n), 定義信源符號的定義信源符號的為為 P1= 0; P2= p1 ; P3= p

4、1+p2 ; 11riirpP累積概率累積概率r=1,2, ,npr = Pr+1 - Pr) 1 , 0rPP1p1P2P3P41p2p30 當(dāng)當(dāng)A=0,1二元信源時(shí)，二元信源時(shí)，P1=P(0)= 0 ; P2 = P(1)= p0P(0)P(1)01p0p1二元序列的累積概率二元序列的累積概率引例引例 設(shè)有二元序列設(shè)有二元序列S=011，求，求S的累積概率的累積概率P(S)=p(000)+ p(001)+ p(010)若若S后面接后面接0P(S0)=p(0000)+ p(0001)+ p(0010)+p(0011)+ p(0100)+ p(0101) =p(000)+ p(001)+ p(

5、010) =P(S)若若S后面接后面接1P(S1)=p(0000)+ p(0001)+ p(0010)+p(0011)+ p(0100)+ p(0101)+ p(0110) =P(S)+ p(0110) =P(S)+p(S) p0二元序列的累積概率二元序列的累積概率P(0)=0,P(1)=p0 P(Sar)=P(S) + p(S) PrS0=0110S1=0111 p(Sar)=p(S) p(ar) p(Sar)=p(S) p(ar /S) P(Sar)=P(S) + p(S) Pr/SP(0)0P(1)1p0設(shè)符號序列設(shè)符號序列S = 011p1P(0)P(1)p(00)=p(0)P(1)P

6、(01)p(01)P(01)P(1)P(011)p(010)=p(01)P(1)p(011)二元序列的累積概率二元序列的累積概率 P(Sar)=P(S)+p(S)Pr累積概率遞推公式累積概率遞推公式一般多元信源序列的累積概率遞推公式一般多元信源序列的累積概率遞推公式rrPSpSPaSPP)()(),(0)()()(),(),(1)(rrrapSpaSpaSAp序列的概率序列的概率(所對應(yīng)區(qū)間的寬度所對應(yīng)區(qū)間的寬度)遞推公式遞推公式SrrPSpSPaSPP/)()(),(0)()/()(),(),(1)(SapSpaSpaSAprrr 實(shí)際中實(shí)際中,求序列累積概率只需兩個(gè)存儲(chǔ)器求序列累積概率只需

7、兩個(gè)存儲(chǔ)器,起始時(shí)可令起始時(shí)可令: A() =1, P() = 0 每輸入一個(gè)符號每輸入一個(gè)符號,存儲(chǔ)器存儲(chǔ)器P和和A 就按照上式更新一次就按照上式更新一次,直至符直至符號輸入完畢號輸入完畢,這時(shí)存儲(chǔ)器這時(shí)存儲(chǔ)器P的內(nèi)容即為該序列的累積概率。的內(nèi)容即為該序列的累積概率。 0)()()(),(PPSpSPaSPrr，1)()()(),(),(papSpaSpaSArrr，累積概率遞推公式累積概率遞推公式累積概率遞推計(jì)算累積概率遞推計(jì)算注意：計(jì)算過程中注意：計(jì)算過程中,每輸入一個(gè)符號只要進(jìn)行乘每輸入一個(gè)符號只要進(jìn)行乘法和加法運(yùn)算。法和加法運(yùn)算。 通過信源符號序列累積概率計(jì)算通過信源符號序列累積概率

8、計(jì)算,把區(qū)間分割成許把區(qū)間分割成許多小區(qū)間多小區(qū)間,不同的信源符號序列對應(yīng)不同的區(qū)間為不同的信源符號序列對應(yīng)不同的區(qū)間為P(S), P(S) + p(S) ，可取小區(qū)間內(nèi)的一點(diǎn)來代表這，可取小區(qū)間內(nèi)的一點(diǎn)來代表這序列。序列。 將符號序列的將符號序列的寫成二進(jìn)位小數(shù)，取小數(shù)點(diǎn)寫成二進(jìn)位小數(shù)，取小數(shù)點(diǎn)后后L位位,若后面有尾數(shù)若后面有尾數(shù),就進(jìn)位到第就進(jìn)位到第L位，即位，即)(1logSpL算術(shù)編碼算術(shù)編碼若若P(S) = 0.10110001，L=3 則則C = 0.110LLSP.0)(算術(shù)編碼的唯一可譯性算術(shù)編碼的唯一可譯性由碼由碼C的形成方法，的形成方法，)(SPC )(1logSpL又又可

9、知可知可知可知LSp 2)()()(SpSPLSP2)(C由此可見由此可見C必在必在)()(),(SpSPSP)()(),(SpSPSPCLSPC2)(,因而唯一可譯。因而唯一可譯。)(1logSpL對于長序列，對于長序列，p(S)必然很小，必然很小，L與概率倒數(shù)對數(shù)幾乎相與概率倒數(shù)對數(shù)幾乎相等，也就是說取整造成的差別很小，因而平均碼長將等，也就是說取整造成的差別很小，因而平均碼長將接近于信源熵接近于信源熵H(S)7)(1logSpL設(shè)二元無記憶信源設(shè)二元無記憶信源S=0,1,p(0)=1/4,p(1)=3/4。S=11111100，對其做算術(shù)編碼。，對其做算術(shù)編碼。P(S) = p(0000

10、0000) + p(00000001) + p(00000010) + + p(11111011) = 1- p(11111111)- p(11111110)- p(11111101) - p(11111100) = 1- p(111111) = 1-(3/4)6= 0.110100100111從而得從而得C = 0.1101010，S的碼字為的碼字為1101010解：解：p(S) = p2(0)p6(1) = (1/4)2 (3/4)6例例 題題1101001%7 .928/7811. 0+=p(1)=3/4=(0.11)2p(11)=(3/4)2=(0.1001)2+=p(0)=(1/4)

11、=2-2p(S)p(0)p(S)右移2位1log14( )npu設(shè)無記憶信源設(shè)無記憶信源U=a1,a2,a3,a4，其概率分布依次為，其概率分布依次為 0.5,0.25,0.125,0.125，對信源序列，對信源序列做算術(shù)編碼。做算術(shù)編碼。解：解：例例 題題21 134121a a a a a a a au42214( )(0.5) (0.25) (0.125)2Pu序號序號uip(ui)P(ui)l(ui)C0空空1001a21/41/220.102a11/81/230.1003a11/161/240.10004a31/12835/6470.10001105a41/1024567/10241

12、00.10001101116a11/2048567/1024110.100011011107a21/81922269/4096130.10001101110108a11/163842269/4096140.10001101110100算術(shù)編碼遞推過程算術(shù)編碼遞推過程 a1, a2, a3 , a40.5,0.25,0.125,0.12521 134121a a a a a a a aurrPSpSPaSP)()(),(1( )0P a 2( ) 1/2P a3( )3/4P a 4( )7/8P a由算術(shù)編碼遞推表得由算術(shù)編碼遞推表得C = 0. 1000110111010000 ，從而從而U

13、的碼字為的碼字為10001101110100 RUH)(1.75100%14/8()0.5log0.50.25log0.2520.125log0.1251.75H U ( )logH UnDP(0)0P(1)1p(0)譯碼輸出序列譯碼輸出序列 011p(1)P(0)P(1)p(00)P(01)p(01)P(01)P(1)P(011)p(010)p(011)算術(shù)譯碼算術(shù)譯碼CCC( )CP ( ) (0)Ap對二元算術(shù)碼而言，其譯碼過程是一系列比較過程：對二元算術(shù)碼而言，其譯碼過程是一系列比較過程：每一步比較每一步比較 與與 ，這里，這里 為前面已譯出的為前面已譯出的序列串，序列串， 是序列串是

14、序列串 對應(yīng)的寬度，對應(yīng)的寬度， 是序列是序列 的累的累積概率值，即為積概率值，即為 對應(yīng)區(qū)間的下界限，對應(yīng)區(qū)間的下界限， 是此區(qū)間是此區(qū)間內(nèi)下一個(gè)輸入為符號內(nèi)下一個(gè)輸入為符號“0”所占的子區(qū)間寬度。所占的子區(qū)間寬度。譯碼規(guī)則為：譯碼規(guī)則為： 若若 ，則譯輸出符號為，則譯輸出符號為“0”； 若若 ，則譯輸出符號為，則譯輸出符號為“1”。( )CP ( ) (0)Ap( )A ( )P ( ) (0)Ap( )CP ( ) (0)Ap( )CP ( ) (0)Ap算術(shù)編碼的譯碼算術(shù)編碼的譯碼 算術(shù)編碼的編碼效率很高，當(dāng)信源符號序列很長時(shí)，算術(shù)編碼的編碼效率很高，當(dāng)信源符號序列很長時(shí)，L很大時(shí)，平

15、均碼長接近信源熵。很大時(shí)，平均碼長接近信源熵。 從性能上來看，算術(shù)編碼具有許多優(yōu)點(diǎn)，它所需的從性能上來看，算術(shù)編碼具有許多優(yōu)點(diǎn)，它所需的參數(shù)較少、編碼效率高、編譯碼簡單，不象哈夫曼參數(shù)較少、編碼效率高、編譯碼簡單，不象哈夫曼碼那樣需要一個(gè)很大的碼表。碼那樣需要一個(gè)很大的碼表。 算術(shù)編碼在圖像數(shù)據(jù)壓縮標(biāo)準(zhǔn)（如算術(shù)編碼在圖像數(shù)據(jù)壓縮標(biāo)準(zhǔn)（如JPEG）中得到）中得到廣泛的應(yīng)用。廣泛的應(yīng)用。算術(shù)編碼的優(yōu)點(diǎn)算術(shù)編碼的優(yōu)點(diǎn)算術(shù)編碼要注意的一些問題算術(shù)編碼要注意的一些問題計(jì)算精度計(jì)算精度 隨著遞推過程的延續(xù)，P(u)和F(u)的小數(shù)位數(shù)也將逐步增加，若不能隨時(shí)輸出和加以截?cái)?，運(yùn)算器將難以容納。但有所截?cái)啾厝?/p>

16、降低精度，而精度不夠會(huì)影響譯碼的正確性。存儲(chǔ)器容量存儲(chǔ)器容量 編成的碼字S的長度也是隨序列u的長度增加而不斷增長。若不及時(shí)輸出，存儲(chǔ)量將非常大。但若輸出過早，運(yùn)算過程中可能還需調(diào)整已經(jīng)輸出的部分，那就來不及了。計(jì)算復(fù)雜性計(jì)算復(fù)雜性 每次遞歸運(yùn)算都有乘法， P(ak)小數(shù)位數(shù)影響計(jì)算復(fù)雜度。在算術(shù)編碼中使用的概率P(ak)不一定完全等于真實(shí)的概率分布，只要設(shè)定的分布近似于真實(shí)分布就很有效。自適應(yīng)算術(shù)編碼自適應(yīng)算術(shù)編碼 在實(shí)際應(yīng)用中，可以在編碼過程中根據(jù)輸入的信源序列自適應(yīng)估計(jì)信源的分布，因此可以對任意概率分布的信源（包含有記憶）進(jìn)行編碼。 上述問題現(xiàn)已解決，算術(shù)編碼已進(jìn)入實(shí)用。上述問題現(xiàn)已解決，

17、算術(shù)編碼已進(jìn)入實(shí)用。兩位以色列研究者兩位以色列研究者J. Ziv和和A. Lempel獨(dú)辟蹊徑，完全脫獨(dú)辟蹊徑，完全脫離離Huffman及算術(shù)編碼的設(shè)計(jì)思路，創(chuàng)造出了一系列比及算術(shù)編碼的設(shè)計(jì)思路，創(chuàng)造出了一系列比Huffman編碼更有效，比算術(shù)編碼更快捷的通用壓縮算編碼更有效，比算術(shù)編碼更快捷的通用壓縮算法法LZ算法。算法。LZ編碼編碼對于統(tǒng)計(jì)特性確知的平穩(wěn)信源，已有對于統(tǒng)計(jì)特性確知的平穩(wěn)信源，已有Huffman編碼和算編碼和算術(shù)編碼高效編碼方法，其平均碼長可逼近信源的平均符術(shù)編碼高效編碼方法，其平均碼長可逼近信源的平均符號熵，而且實(shí)現(xiàn)困難不算太大，所以已進(jìn)入實(shí)用。號熵，而且實(shí)現(xiàn)困難不算太大，

18、所以已進(jìn)入實(shí)用。要確知信源的統(tǒng)計(jì)特性相當(dāng)困難。通用編碼指在信源統(tǒng)要確知信源的統(tǒng)計(jì)特性相當(dāng)困難。通用編碼指在信源統(tǒng)計(jì)特性不知時(shí)，對信源進(jìn)行編碼，而且編碼效率很高。計(jì)特性不知時(shí)，對信源進(jìn)行編碼，而且編碼效率很高。 Ziv和Lempel于1977年提出了LZ77算法。1978年，二人又提出了改進(jìn)算法，后被命名為LZ78。1984年，T. A. Welch提出了LZ78算法的一個(gè)變種，即LZW算法。1990年后，T. C. Bell等人又陸續(xù)提出了許多LZ系列算法的變體或改進(jìn)版本。 LZ系列算法用一種巧妙的方式將字典技術(shù)應(yīng)用于通用數(shù)據(jù)壓縮領(lǐng)域，而且，可以從理論上證明LZ 系列算法同樣可以逼近信息熵的極

19、限. 下面我們主要介紹LZ78算法。12 ,KAa aa設(shè)輸入信源符號序列為設(shè)輸入信源符號序列為盡可能取最少個(gè)相連的信源符號，并保證各段都不相同。盡可能取最少個(gè)相連的信源符號，并保證各段都不相同。Luuuu,21iu，其中，其中編碼時(shí)將此序列分成不同的段。編碼時(shí)將此序列分成不同的段。分段規(guī)則：分段規(guī)則：設(shè)序列分段結(jié)果為設(shè)序列分段結(jié)果為.,321cyyyy若若ij ，則必有，則必有rijayy LZ78碼碼LZ78編碼算法是一種分段編碼。編碼算法是一種分段編碼。由分段規(guī)則可見，字典中每一段都是前面某一段由分段規(guī)則可見，字典中每一段都是前面某一段后加一個(gè)符號。后加一個(gè)符號。 開始時(shí)，先取一個(gè)符號作

20、為第一段，然后再繼續(xù)分段。若出現(xiàn)有與前面相同符號時(shí)，就再取緊跟后面的一個(gè)符號一起組成一個(gè)段，以使與前面的段不同。 這些分段構(gòu)成字典。 當(dāng)字典達(dá)到一定大小后，再分段時(shí)就應(yīng)查看有否與字典中的短語相同，若有重復(fù)就添加符號后再查看，直至與字典中短語不同為止。 由分段規(guī)則可見，字典中每一段都是前面某一段后加一個(gè)符號。則編碼的碼字由段號加后面一個(gè)符號組成。則編碼的碼字由段號加后面一個(gè)符號組成。 或者說編碼碼字可用兩個(gè)數(shù)段號或者說編碼碼字可用兩個(gè)數(shù)段號i 和符號序號和符號序號r 組成。組成。 段號段號i i 和符號序號和符號序號r r 的表示的表示 由于ri，則 所以，對Nj編碼所需的比特?cái)?shù)為 由上式可見，各段所需的比特?cái)?shù)是不同的，是隨j的增加而增多。1,jijrK NKirKjlog(1)logjjlNKj 設(shè)設(shè)U=a1, a2, a3, a4，信源序列為，信源序列為121324243 1 14a a a a a a a a a a a