信息論算術(shù)編碼與LZ編碼講義

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

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

3、來(lái)表示信源序列。 設(shè)信源字母表為設(shè)信源字母表為a1, a2,概率概率p(a1)=0.6, p(a2)=0.4， 將將0,1按概率比例分為區(qū)間按概率比例分為區(qū)間0,0.6,0.6,l。 0 0.6 1 p(a1) p(a2) 0 0.36 0.6 0.84 1 p(a1a1) p(a1a2) p(a2a1) p(a2a2) 隨著序列的長(zhǎng)度不斷增隨著序列的長(zhǎng)度不斷增加加,C所在區(qū)間的長(zhǎng)度就所在區(qū)間的長(zhǎng)度就越短越短,精確地確定精確地確定C的位的位置需要碼長(zhǎng)也不斷增加置需要碼長(zhǎng)也不斷增加 累積概率累積概率 設(shè)信源符號(hào)集設(shè)信源符號(hào)集A=a1,a2,an, 其相應(yīng)概率分布為其相應(yīng)概率分布為pi, pi 0

4、 (i=1,2, ,n), 定義信源符號(hào)的定義信源符號(hào)的累積概率（分布函數(shù)）累積概率（分布函數(shù)）為為 r?1i?1Pr?pir=1,2, , n P1= 0; P2= p1 ; P3= p1+p2 ; P ?0 ,1 )r pr = Pr+1 - Pr 0 P1 p1 P2 p2 P3 P4 p3 1 二元序列的累積概率二元序列的累積概率 當(dāng)當(dāng)A=0,1二元信源時(shí)，二元信源時(shí)，P1=P(0)= 0 ; P2 = P(1)= p0 0 P(0) p0 P(1) p1 1 引例引例 設(shè)有二元序列設(shè)有二元序列S=011，求，求S的累積概率的累積概率 P(S)= p(000)+ p(001)+ p(0

5、10) 二元序列的累積概率二元序列的累積概率 若若S后面接后面接0 S0=0110 P(S0)= p(0000)+ p(0001)+ p(0010)+p(0011)+ p(0100)+ p(0101) =p(000)+ p(001)+ p(010) =P(S) 若若S后面接后面接1 S1=0111 P(S1)= p(0000)+ p(0001)+ p(0010)+p(0011)+ p(0100)+ p(0101)+ p(0110) =P(S)+ p(0110) P(0) =0 ,P(1) =p p(Sa p(Sa)=p )=p(S) (S) p(ap(a) r) 0rrr =P(S)+p(S)

6、 p0 P(Sa =P(S) + p(S) P P(Sa)=P(S) + p(S) Pr)r rr 二元序列的累積概率二元序列的累積概率 設(shè)符號(hào)序列設(shè)符號(hào)序列S = 011 P(Sar)=P(S)+p(S)Pr 1 p1 p(01) P(011) p(011) P(1) P(1) 0 P(0) P(0) p0 P(1) P(01) p(00)= p(0) P(1) P(01) p(010)=p(01) P(1) 累積概率遞推公式累積概率遞推公式 一般多元信源序列的累積概率遞推公式一般多元信源序列的累積概率遞推公式 P( P? ?()?)0?0P( P S ( ,S a,ra )r?S ( )S

7、?p(p S ( )S P)P?( P )?)r/PS r序列的概率序列的概率(所對(duì)應(yīng)區(qū)間的寬度所對(duì)應(yīng)區(qū)間的寬度)遞推公式遞推公式 p? ?11p(?)?AS,aa )?p(S,a )?p(S)p(a )A (S)?p(S,a )?p(S)p(a /rrrrrrS)累積概率遞推計(jì)算累積概率遞推計(jì)算 累積概率遞推公式累積概率遞推公式 P(S,ar)?P(S)?p(S)Pr，P(?)?0A (S,ar)?p(S,ar)?p(S)p(ar) ，p(?)?1? 實(shí)際中實(shí)際中,求序列累積概率只需兩個(gè)存儲(chǔ)器求序列累積概率只需兩個(gè)存儲(chǔ)器,起始時(shí)可令起始時(shí)可令: A() =1, P() = 0 每輸入一個(gè)符號(hào)

8、每輸入一個(gè)符號(hào),存儲(chǔ)器存儲(chǔ)器P和和A 就按照上式更新一次就按照上式更新一次,直至符直至符號(hào)輸入完畢號(hào)輸入完畢,這時(shí)存儲(chǔ)器這時(shí)存儲(chǔ)器P的內(nèi)容即為該序列的累積概率。的內(nèi)容即為該序列的累積概率。 注意：計(jì)算過(guò)程中注意：計(jì)算過(guò)程中,每輸入一個(gè)符號(hào)只要進(jìn)行乘每輸入一個(gè)符號(hào)只要進(jìn)行乘法和加法運(yùn)算。法和加法運(yùn)算。 算術(shù)編碼算術(shù)編碼 通過(guò)信源符號(hào)序列累積概率計(jì)算通過(guò)信源符號(hào)序列累積概率計(jì)算,把區(qū)間分割成許把區(qū)間分割成許多小區(qū)間多小區(qū)間,不同的信源符號(hào)序列對(duì)應(yīng)不同的區(qū)間為不同的信源符號(hào)序列對(duì)應(yīng)不同的區(qū)間為P(S), P(S) + p(S) ，可取小區(qū)間內(nèi)的一點(diǎn)來(lái)代表這，可取小區(qū)間內(nèi)的一點(diǎn)來(lái)代表這序列。序列。 將

9、符號(hào)序列的累積概率寫(xiě)成二進(jìn)位小數(shù)，取小數(shù)點(diǎn)將符號(hào)序列的累積概率寫(xiě)成二進(jìn)位小數(shù)，取小數(shù)點(diǎn)后后L位位,若后面有尾數(shù)若后面有尾數(shù),就進(jìn)位到第就進(jìn)位到第L位，即位，即 ?1?L?log?p(S)?P(S)?L?0.?L 若若P(S) = 0.10110001，L=3 則則C = 0.110 C?P(S),P(S)?p(S)?算術(shù)編碼的唯一可譯性算術(shù)編碼的唯一可譯性 可知可知由碼由碼C的形成方法，的形成方法， C?P(S)?1?L又又 L?log可知可知 p(S)?2?p(S)?LP(S)?p(S)?P(S)?2? CC?P(S)?2?L由此可見(jiàn)由此可見(jiàn)C必在必在 P(S),P(S)?p(S),因而唯一

10、可譯。因而唯一可譯。 對(duì)于長(zhǎng)序列，對(duì)于長(zhǎng)序列，p(S)必然很小，必然很小，L與概率倒數(shù)對(duì)數(shù)幾乎相與概率倒數(shù)對(duì)數(shù)幾乎相等，也就是說(shuō)取整造成的差別很小，因而平均碼長(zhǎng)將等，也就是說(shuō)取整造成的差別很小，因而平均碼長(zhǎng)將接近于信源熵接近于信源熵H(S) 例例 題題 設(shè)二元無(wú)記憶信源設(shè)二元無(wú)記憶信源S=0,1, p(0)=1/4,p(1)=3/4。 S=11111100，對(duì)其做算術(shù)編碼。，對(duì)其做算術(shù)編碼。 解：解：p(S) = p2(0) p6(1) = (1/4)2 (3/4)6 P(S) = p(00000000) + p (00000001) + p (00000010) + + p (1111101

11、1) = 1- p(11111111)- p(11111110)- p(11111101) - p(11111100) = 1- p(111111) = 1-(3/4)6= 0.110100100111 1101001 ?1?L?log?7?p(S)?從而得從而得C = 0.1101010，S的碼字為的碼字為1101010 0.811?92 .7 %7/8p(1)=3/4=(0.11)2 p(0)=(1/4)=2-2 p(S)p(0)p(S)右移2 位 p(11)=(3/4)2=(0.1001)2 輸入符號(hào)輸入符號(hào) p(S) 空空 1 1 1 1 1 1 1 0 0 序列序列11111100的

12、編碼過(guò)程的編碼過(guò)程 p(S)p(0) P(S) 0 + 0.01 0.0011 0.11 0.1001 0.011011 0.01010001 0.0011110011 0.001011011001 0.00001011011001 + = = L C 0 1 0.1 1 0.1 2 0.11 2 0.11 3 0.111 0.01 0.0111 0.100101 0.10101111 0.1100001101 0.001001 0.00011011 0.0001010001 0.000011110011 0.00001011011001 0.0000001011011001 0.000000

13、1011011001 0.110100100111 7 0.1101010 0.110100100111 3 0.111 0.110100100111 5 0.11011 例例 題題 設(shè)無(wú)記憶信源設(shè)無(wú)記憶信源U=a1,a2,a3,a4，其概率分布依次為，其概率分布依次為 0.5,0.25,0.125,0.125，對(duì)信源序列，對(duì)信源序列 u ?a2a1a1a3a4a1a2a1做算術(shù)編碼。做算術(shù)編碼。 解：解： P(u)?(0.5)(0.25) (0.125)?2422?14?1?n?log?14?p(u)?u?a2a1a1a3a4a1a2a1 a1, a2, a3 , a4 序號(hào)序號(hào) 0 ui

14、空空 0.5,0.25,0.125,0.125 P(S,ar)?P(S)?p(S)Pr算術(shù)編碼遞推過(guò)程算術(shù)編碼遞推過(guò)程 P(a1)?0 P(a2)?1/ 2P(a3)?3/ 4P(a4)?7/8P(ui) 0 l(ui) 0 C p(ui) 1 1 2 3 4 5 6 7 8 a2 a1 a1 a3 a4 a1 a2 a1 1/4 1/8 1/16 1/128 1/1024 1/2048 1/8192 1/16384 1/2 1/2 1/2 35/64 567/1024 567/1024 2269/4096 2269/4096 2 3 4 7 10 11 13 14 0.10 0.100 0.

15、1000 0.1000110 0.1000110111 0.10001101110 0.1000110111010 0.10001101110100 由算術(shù)編碼遞推表得由算術(shù)編碼遞推表得C = 0. 1000110111010000 ， 從而從而U的碼字為的碼字為10001101110100 H(U)? ?0.5log0.5?0.25log0.25?2?0.125log0.125?1.75H(U)1.75H(U)?100%?RnlogD14 /8算術(shù)譯碼算術(shù)譯碼 C? ?P(?)A(?)p(0)0 P(0) P(0) p(0) p(00) P(1) C P(01) p(01) P(011) p

16、(1) C P(1) P(1) 1 P(01) C p(011) p(010) 譯碼輸出序列譯碼輸出序列 011 算術(shù)編碼的譯碼算術(shù)編碼的譯碼 對(duì)二元算術(shù)碼而言，其譯碼過(guò)程是一系列比較過(guò)程：對(duì)二元算術(shù)碼而言，其譯碼過(guò)程是一系列比較過(guò)程： ?為前面已譯出的為前面已譯出的 C? ?P(?)與與 每一步比較每一步比較 ，這里，這里 A(?)p(0)A(?)是序列串是序列串 ?對(duì)應(yīng)的寬度，對(duì)應(yīng)的寬度，?的累的累 序列串，序列串， P (?)是序列是序列 A(?)p(0)是此區(qū)間是此區(qū)間 積概率值，即為積概率值，即為 ?對(duì)應(yīng)區(qū)間的下界限，對(duì)應(yīng)區(qū)間的下界限，內(nèi)下一個(gè)輸入為符號(hào)內(nèi)下一個(gè)輸入為符號(hào)“0”所占的

17、子區(qū)間寬度。所占的子區(qū)間寬度。 譯碼規(guī)則為：譯碼規(guī)則為： C? ?P(?) A(?)p(0)，則譯輸出符號(hào)為，則譯輸出符號(hào)為“0”； 若若 C? ?P(?) A(?)p(0)，則譯輸出符號(hào)為，則譯輸出符號(hào)為“1”。 若若 算術(shù)編碼的優(yōu)點(diǎn)算術(shù)編碼的優(yōu)點(diǎn) ?算術(shù)編碼的編碼效率很高，當(dāng)信源符號(hào)序列很長(zhǎng)算術(shù)編碼的編碼效率很高，當(dāng)信源符號(hào)序列很長(zhǎng)時(shí)，時(shí)，L很大時(shí)，平均碼長(zhǎng)接近信源熵。很大時(shí)，平均碼長(zhǎng)接近信源熵。 ?從性能上來(lái)看，算術(shù)編碼具有許多優(yōu)點(diǎn)，它所需從性能上來(lái)看，算術(shù)編碼具有許多優(yōu)點(diǎn)，它所需的參數(shù)較少、編碼效率高、編譯碼簡(jiǎn)單，不象哈的參數(shù)較少、編碼效率高、編譯碼簡(jiǎn)單，不象哈夫曼碼那樣需要一個(gè)很大的

18、碼表。夫曼碼那樣需要一個(gè)很大的碼表。 ?算術(shù)編碼在圖像數(shù)據(jù)壓縮標(biāo)準(zhǔn)（如算術(shù)編碼在圖像數(shù)據(jù)壓縮標(biāo)準(zhǔn)（如JPEG）中得到）中得到廣泛的應(yīng)用。廣泛的應(yīng)用。 算術(shù)編碼要注意的一些問(wèn)題算術(shù)編碼要注意的一些問(wèn)題 ?計(jì)算精度計(jì)算精度 隨著遞推過(guò)程的延續(xù)，隨著遞推過(guò)程的延續(xù)，P(u)和和F(u)的小數(shù)位數(shù)的小數(shù)位數(shù)也將逐步增加，若不能隨時(shí)輸出和加以截?cái)?，也將逐步增加，若不能隨時(shí)輸出和加以截?cái)啵\(yùn)算器將難以容納。但有所截?cái)啾厝唤档途?，運(yùn)算器將難以容納。但有所截?cái)啾厝唤档途?，而精度不夠?huì)影響譯碼的正確性。而精度不夠會(huì)影響譯碼的正確性。 ?存儲(chǔ)器容量存儲(chǔ)器容量 編成的碼字編成的碼字S的長(zhǎng)度也是隨序列的長(zhǎng)度也是隨

19、序列u的長(zhǎng)度增加而的長(zhǎng)度增加而不斷增長(zhǎng)。若不及時(shí)輸出，存儲(chǔ)量將非常大。不斷增長(zhǎng)。若不及時(shí)輸出，存儲(chǔ)量將非常大。但若輸出過(guò)早，運(yùn)算過(guò)程中可能還需調(diào)整已經(jīng)但若輸出過(guò)早，運(yùn)算過(guò)程中可能還需調(diào)整已經(jīng)輸出的部分，那就來(lái)不及了。輸出的部分，那就來(lái)不及了。 ?計(jì)算復(fù)雜性計(jì)算復(fù)雜性 每次遞歸運(yùn)算都有乘法，每次遞歸運(yùn)算都有乘法， P(ak)小數(shù)位數(shù)影響小數(shù)位數(shù)影響計(jì)算復(fù)雜度。在算術(shù)編碼中使用的概率計(jì)算復(fù)雜度。在算術(shù)編碼中使用的概率P(ak)不一定完全等于真實(shí)的概率分布，只要設(shè)定的不一定完全等于真實(shí)的概率分布，只要設(shè)定的分布近似于真實(shí)分布就很有效。分布近似于真實(shí)分布就很有效。 ?自適應(yīng)算術(shù)編碼自適應(yīng)算術(shù)編碼 在實(shí)

20、際應(yīng)用中，可以在編碼過(guò)程中根據(jù)輸入的在實(shí)際應(yīng)用中，可以在編碼過(guò)程中根據(jù)輸入的信源序列自適應(yīng)估計(jì)信源的分布，因此可以對(duì)信源序列自適應(yīng)估計(jì)信源的分布，因此可以對(duì)任意概率分布的信源（包含有記憶）進(jìn)行編碼。任意概率分布的信源（包含有記憶）進(jìn)行編碼。 上述問(wèn)題現(xiàn)已解決，算術(shù)編碼已進(jìn)入實(shí)用。上述問(wèn)題現(xiàn)已解決，算術(shù)編碼已進(jìn)入實(shí)用。 LZ編碼編碼 對(duì)于統(tǒng)計(jì)特性確知的平穩(wěn)信源，已有對(duì)于統(tǒng)計(jì)特性確知的平穩(wěn)信源，已有Huffman編碼和算編碼和算術(shù)編碼高效編碼方法，其平均碼長(zhǎng)可逼近信源的平均符術(shù)編碼高效編碼方法，其平均碼長(zhǎng)可逼近信源的平均符號(hào)熵，而且實(shí)現(xiàn)困難不算太大，所以已進(jìn)入實(shí)用。號(hào)熵，而且實(shí)現(xiàn)困難不算太大，所以

21、已進(jìn)入實(shí)用。 要確知信源的統(tǒng)計(jì)特性相當(dāng)困難。通用編碼指在信源統(tǒng)要確知信源的統(tǒng)計(jì)特性相當(dāng)困難。通用編碼指在信源統(tǒng)計(jì)特性不知時(shí)，對(duì)信源進(jìn)行編碼，而且編碼效率很高。計(jì)特性不知時(shí)，對(duì)信源進(jìn)行編碼，而且編碼效率很高。 兩位以色列研究者兩位以色列研究者J. Ziv和和A. Lempel獨(dú)辟蹊徑，完全脫獨(dú)辟蹊徑，完全脫離離Huffman及算術(shù)編碼的設(shè)計(jì)思路，創(chuàng)造出了一系列比及算術(shù)編碼的設(shè)計(jì)思路，創(chuàng)造出了一系列比Huffman編碼更有效，比算術(shù)編碼更快捷的通用壓縮算編碼更有效，比算術(shù)編碼更快捷的通用壓縮算法法LZ算法。算法。 ? Ziv和和Lempel于于1977年提出了年提出了LZ77算法。算法。1978年

22、，二年，二人又提出了改進(jìn)算法，后被命名為人又提出了改進(jìn)算法，后被命名為L(zhǎng)Z78。1984年，年，T. A. Welch提出了提出了LZ78算法的一個(gè)變種，即算法的一個(gè)變種，即LZW算法。算法。1990年后，年后，T. C. Bell等人又陸續(xù)提出了許多等人又陸續(xù)提出了許多LZ系列算系列算法的變體或改進(jìn)版本。法的變體或改進(jìn)版本。 ? LZ系列算法用一種巧妙的方式將字典技術(shù)應(yīng)用于通用系列算法用一種巧妙的方式將字典技術(shù)應(yīng)用于通用數(shù)據(jù)壓縮領(lǐng)域，而且，可以從理論上證明數(shù)據(jù)壓縮領(lǐng)域，而且，可以從理論上證明LZ 系列算系列算法同樣可以逼近信息熵的極限法同樣可以逼近信息熵的極限. ?下面我們主要介紹下面我們主

23、要介紹LZ78算法。算法。 LZ78碼碼 LZ78編碼算法是一種分段編碼。編碼算法是一種分段編碼。 設(shè)輸入信源符號(hào)序列為設(shè)輸入信源符號(hào)序列為 u?u1,u2,? ,uL?，其中，其中 ui?A?a1,a2,aK編碼時(shí)將此序列分成不同的段。編碼時(shí)將此序列分成不同的段。 分段規(guī)則：分段規(guī)則： 盡可能取最少個(gè)相連的信源符號(hào)，并保證各段都不相同。盡可能取最少個(gè)相連的信源符號(hào)，并保證各段都不相同。 設(shè)序列分段結(jié)果為設(shè)序列分段結(jié)果為 y1,y2,y3,? ,yc.若若 j?i，則必有，則必有 yj?yiar由分段規(guī)則可見(jiàn)，字典中每一段都是前面某一段由分段規(guī)則可見(jiàn)，字典中每一段都是前面某一段后加一個(gè)符號(hào)。后

24、加一個(gè)符號(hào)。 ?開(kāi)始時(shí)，先取一個(gè)符號(hào)作為第一段，然后再繼續(xù)分段。若開(kāi)始時(shí)，先取一個(gè)符號(hào)作為第一段，然后再繼續(xù)分段。若出現(xiàn)有與前面相同符號(hào)時(shí)，就再取緊跟后面的一個(gè)符號(hào)一出現(xiàn)有與前面相同符號(hào)時(shí)，就再取緊跟后面的一個(gè)符號(hào)一起組成一個(gè)段，以使與前面的段不同。起組成一個(gè)段，以使與前面的段不同。 ?這些分段構(gòu)成字典。這些分段構(gòu)成字典。 ?當(dāng)字典達(dá)到一定大小后，再分段時(shí)就應(yīng)查看有否與字典中當(dāng)字典達(dá)到一定大小后，再分段時(shí)就應(yīng)查看有否與字典中的短語(yǔ)相同，若有重復(fù)就添加符號(hào)后再查看，直至與字典的短語(yǔ)相同，若有重復(fù)就添加符號(hào)后再查看，直至與字典中短語(yǔ)不同為止。中短語(yǔ)不同為止。 ? 由分段規(guī)則可見(jiàn)，字典中每一段都是前面某一段后加一個(gè)由分段規(guī)則可見(jiàn)，字典中每一段都是前面某一段后加一個(gè)符號(hào)。符號(hào)。 則編碼的碼字由段號(hào)加后面一個(gè)符號(hào)組成。則編碼的碼字由段號(hào)加后面一個(gè)符號(hào)組成。 或者說(shuō)編碼碼字可用兩個(gè)數(shù)段號(hào)或者說(shuō)編碼碼字可用兩個(gè)數(shù)段號(hào)i 和符號(hào)序號(hào)和符號(hào)序號(hào)r 組成。組成。 段號(hào)段號(hào)i 和符號(hào)序號(hào)和符號(hào)序號(hào)r 的表示的表示 ?由于由于ri，則，則 i?j?1,r?K,Nj?Ki?r?Kj 所以，對(duì)所以，對(duì)Nj編碼所需的比特?cái)?shù)為編碼所需的比特?cái)?shù)為 lj? ?log(Nj?1)? ? ?logKj? 由上式可見(jiàn)，各段所需的比特?cái)?shù)是不同的，是由上式可見(jiàn)，各段所需的比特?cái)?shù)是不同