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

第9講——算術(shù)編碼與LZ編碼2014第一頁，共32頁。算術(shù)編碼前面所討論的無失真編碼，都是建立在信源符號與碼字一一對應(yīng)的基礎(chǔ)上，這種編碼方法通常稱為塊碼或分組碼，此時(shí)信源符號一般是多元的。如果要對二元序列進(jìn)行編碼，則需采用合并信源符號方法，把二元序列轉(zhuǎn)換成多值符號，轉(zhuǎn)換時(shí)二元符號之間的相關(guān)性不予考慮，轉(zhuǎn)換后這些多值符號之間的相關(guān)性也不予考慮。這就使信源編碼的匹配原則不能充分滿足，編碼效率一般不高。為了克服這種局限性，需要跳出分組碼范疇，從整個(gè)符號序列出發(fā)，采用遞推形式進(jìn)行編碼。第二頁，共32頁。從整個(gè)符號序列出發(fā)，根據(jù)各信源序列的概率將信源序列映射到[0,1)區(qū)間上，然后選取區(qū)間內(nèi)的一點(diǎn)（也就是一個(gè)二進(jìn)制的小數(shù)）來表示信源序列。算術(shù)編碼基本思想設(shè)信源字母表為{a1,a2},概率p(a1)=0.6,p(a2)=0.4，將[0,1]按概率比例分為區(qū)間[0,0.6],[0.6,l]。p(a1)p(a2)00.6100.360.60.841p(a1a1)p(a1a2)p(a2a1)p(a2a2)隨著序列的長度不斷增加,C所在區(qū)間的長度就越短,精確地確定C的位置需要碼長也不斷增加第三頁，共32頁。

設(shè)信源符號集A={a1,a2,…,an},其相應(yīng)概率分布為pi,pi>0(i=1,2,…,n),定義信源符號的累積概率（分布函數(shù)）為P1=0;P2=p1;P3=p1+p2;…

累積概率r=1,2,…,npr=Pr+1-PrP1p1P2P3P41p2p3……0第四頁，共32頁。當(dāng)A={0,1}二元信源時(shí)，P1=P(0)=0

;P2

=P(1)=

p0P(0)P(1)01p0p1二元序列的累積概率引例設(shè)有二元序列S=011，求S的累積概率P(S)=p(000)+p(001)+p(010)第五頁，共32頁。若S后面接0P(S0)=p(0000)+p(0001)+p(0010)+p(0011)+

p(0100)+p(0101)

=p(000)+p(001)+p(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/S第六頁，共32頁。P(0)0P(1)1p0設(shè)符號序列S=011p1P(0)P(1)p(00)=p(0)P(1)P(01)p(01)P(01)P(1)P(011)p(010)=p(01)P(1)p(011)二元序列的累積概率

P(Sar)=P(S)+p(S)Pr第七頁，共32頁。累積概率遞推公式一般多元信源序列的累積概率遞推公式序列的概率(所對應(yīng)區(qū)間的寬度)遞推公式第八頁，共32頁。實(shí)際中,求序列累積概率只需兩個(gè)存儲器,起始時(shí)可令:A(Φ)=1,P(Φ)=0每輸入一個(gè)符號,存儲器P和A就按照上式更新一次,直至符號輸入完畢,這時(shí)存儲器P的內(nèi)容即為該序列的累積概率。累積概率遞推公式累積概率遞推計(jì)算注意：計(jì)算過程中,每輸入一個(gè)符號只要進(jìn)行乘法和加法運(yùn)算。第九頁，共32頁。通過信源符號序列累積概率計(jì)算,把區(qū)間分割成許多小區(qū)間,不同的信源符號序列對應(yīng)不同的區(qū)間為[P(S),P(S)+p(S))，可取小區(qū)間內(nèi)的一點(diǎn)來代表這序列。將符號序列的累積概率寫成二進(jìn)位小數(shù)，取小數(shù)點(diǎn)后L位,若后面有尾數(shù),就進(jìn)位到第L位，即算術(shù)編碼若P(S)=0.10110001，L=3則C=0.110第十頁，共32頁。算術(shù)編碼的唯一可譯性由碼C的形成方法，又可知可知由此可見C必在,因而唯一可譯。對于長序列，p(S)必然很小，L與概率倒數(shù)對數(shù)幾乎相等，也就是說取整造成的差別很小，因而平均碼長將接近于信源熵H(S)第十一頁，共32頁。設(shè)二元無記憶信源S={0,1},p(0)=1/4,p(1)=3/4。S=11111100，對其做算術(shù)編碼。P(S)=p(00000000)+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例題第十二頁，共32頁。+=p(1)=3/4=(0.11)2p(11)=(3/4)2=(0.1001)2+=…p(0)=(1/4)=2-2p(S)p(0)→p(S)右移2位第十三頁，共32頁。設(shè)無記憶信源U={a1,a2,a3,a4}，其概率分布依次為0.5,0.25,0.125,0.125，對信源序列做算術(shù)編碼。解：例題第十四頁，共32頁。序號uip(ui)P(ui)l(ui)C0空1001a21/41/220.102a11/81/230.1003a11/161/240.10004a31/12835/6470.10001105a41/1024567/1024100.10001101116a11/2048567/1024110.100011011107a21/81922269/4096130.108a11/163842269/4096140.100算術(shù)編碼遞推過程

a1,a2,

a3,a40.5,0.25,0.125,0.125第十五頁，共32頁。由算術(shù)編碼遞推表得C=0.10000，從而U的碼字為100

第十六頁，共32頁。P(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ù)譯碼CCC第十七頁，共32頁。對二元算術(shù)碼而言，其譯碼過程是一系列比較過程：每一步比較與，這里為前面已譯出的序列串，是序列串對應(yīng)的寬度，是序列的累積概率值，即為對應(yīng)區(qū)間的下界限，是此區(qū)間內(nèi)下一個(gè)輸入為符號“0”所占的子區(qū)間寬度。譯碼規(guī)則為：若＜，則譯輸出符號為“0”；若＞，則譯輸出符號為“1”。算術(shù)編碼的譯碼第十八頁，共32頁。算術(shù)編碼的編碼效率很高，當(dāng)信源符號序列很長時(shí)，L很大時(shí)，平均碼長接近信源熵。從性能上來看，算術(shù)編碼具有許多優(yōu)點(diǎn)，它所需的參數(shù)較少、編碼效率高、編譯碼簡單，不象哈夫曼碼那樣需要一個(gè)很大的碼表。算術(shù)編碼在圖像數(shù)據(jù)壓縮標(biāo)準(zhǔn)（如JPEG）中得到廣泛的應(yīng)用。算術(shù)編碼的優(yōu)點(diǎn)第十九頁，共32頁。算術(shù)編碼要注意的一些問題計(jì)算精度隨著遞推過程的延續(xù)，P(u)和F(u)的小數(shù)位數(shù)也將逐步增加，若不能隨時(shí)輸出和加以截?cái)啵\(yùn)算器將難以容納。但有所截?cái)啾厝唤档途?，而精度不夠會影響譯碼的正確性。存儲器容量編成的碼字S的長度也是隨序列u的長度增加而不斷增長。若不及時(shí)輸出，存儲量將非常大。但若輸出過早，運(yùn)算過程中可能還需調(diào)整已經(jīng)輸出的部分，那就來不及了。第二十頁，共32頁。計(jì)算復(fù)雜性每次遞歸運(yùn)算都有乘法，P(ak)小數(shù)位數(shù)影響計(jì)算復(fù)雜度。在算術(shù)編碼中使用的概率P(ak)不一定完全等于真實(shí)的概率分布，只要設(shè)定的分布近似于真實(shí)分布就很有效。自適應(yīng)算術(shù)編碼在實(shí)際應(yīng)用中，可以在編碼過程中根據(jù)輸入的信源序列自適應(yīng)估計(jì)信源的分布，因此可以對任意概率分布的信源（包含有記憶）進(jìn)行編碼。上述問題現(xiàn)已解決，算術(shù)編碼已進(jìn)入實(shí)用。第二十一頁，共32頁。兩位以色列研究者J.Ziv和A.Lempel獨(dú)辟蹊徑，完全脫離Huffman及算術(shù)編碼的設(shè)計(jì)思路，創(chuàng)造出了一系列比Huffman編碼更有效，比算術(shù)編碼更快捷的通用壓縮算法——LZ算法。LZ編碼對于統(tǒng)計(jì)特性確知的平穩(wěn)信源，已有Huffman編碼和算術(shù)編碼高效編碼方法，其平均碼長可逼近信源的平均符號熵，而且實(shí)現(xiàn)困難不算太大，所以已進(jìn)入實(shí)用。要確知信源的統(tǒng)計(jì)特性相當(dāng)困難。通用編碼指在信源統(tǒng)計(jì)特性不知時(shí)，對信源進(jìn)行編碼，而且編碼效率很高。第二十二頁，共32頁。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系列算法同樣可以逼近信息熵的極限.下面我們主要介紹LZ78算法。第二十三頁，共32頁。設(shè)輸入信源符號序列為盡可能取最少個(gè)相連的信源符號，并保證各段都不相同。，其中編碼時(shí)將此序列分成不同的段。分段規(guī)則：設(shè)序列分段結(jié)果為若，則必有LZ78碼LZ78編碼算法是一種分段編碼。由分段規(guī)則可見，字典中每一段都是前面某一段后加一個(gè)符號。第二十四頁，共32頁。開始時(shí)，先取一個(gè)符號作為第一段，然后再繼續(xù)分段。若出現(xiàn)有與前面相同符號時(shí)，就再取緊跟后面的一個(gè)符號一起組成一個(gè)段，以使與前面的段不同。這些分段構(gòu)成字典。當(dāng)字典達(dá)到一定大小后，再分段時(shí)就應(yīng)查看有否與字典中的短語相同，若有重復(fù)就添加符號后再查看，直至與字典中短語不同為止。由分段規(guī)則可見，字典中每一段都是前面某一段后加一個(gè)符號。則編碼的碼字由段號加后面一個(gè)符號組成。或者說編碼碼字可用兩個(gè)數(shù)段號i和符號序號r組成。第二十五頁，共32頁。段號i和符號序號r的表示由于r<K，這兩個(gè)數(shù)也可以用一個(gè)數(shù)Nj來表示，即Nj=iK+r.從Nj很容易恢復(fù)i和r，即用K除Nj，所得余數(shù)就是r，商為i。把Nj表示成二進(jìn)制數(shù)，即得二進(jìn)碼。單符號的碼字段號為0。第二十六頁，共32頁。

計(jì)算對Nj編碼時(shí)所需的比特?cái)?shù)注意到K,i,j,r等都是整數(shù)，并設(shè)j>i，則

所以，對Nj編碼所需的比特?cái)?shù)為由上式可見，各段所需的比特?cái)?shù)是不同的，是隨j的增加而增多。第二十七頁，共32頁。設(shè)U={a1,a2,a3,a4}，信