信息論第講算術編碼與編碼

信息論第講算術編碼與編碼第一頁，共二十八頁，2022年，8月28日算術編碼前面所討論的無失真編碼，都是建立在信源符號與碼字一一對應的基礎上，這種編碼方法通常稱為塊碼或分組碼，此時信源符號一般是多元的。如果要對二元序列進行編碼，則需采用合并信源符號方法，把二元序列轉換成多值符號，轉換時二元符號之間的相關性不予考慮，轉換后這些多值符號之間的相關性也不予考慮。這就使信源編碼的匹配原則不能充分滿足，編碼效率一般不高。為了克服這種局限性，需要跳出分組碼范疇，從整個符號序列出發(fā)，采用遞推形式進行編碼。第二頁，共二十八頁，2022年，8月28日從整個符號序列出發(fā)，根據(jù)各信源序列的概率將信源序列映射到[0,1)區(qū)間上，然后選取區(qū)間內(nèi)的一點（也就是一個二進制的小數(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的位置需要碼長也不斷增加第三頁，共二十八頁，2022年，8月28日

設信源符號集A={a1,a2,…,an},其相應概率分布為pi,pi>0(i=1,2,…,n),定義信源符號的累積概率（分布函數(shù)）為

P1=0;P2=p1;P3=p1+p2;…

累積概率r=1,2,…,npr=Pr+1-PrP1p1P2P3P41p2p3……0第四頁，共二十八頁，2022年，8月28日當A={0,1}二元信源時，P1=P(0)=0

;P2

=P(1)=

p0P(0)P(1)01p0p1二元序列的累積概率引例設有二元序列S=011，求S的累積概率P(S)=p(000)+p(001)+p(010)第五頁，共二十八頁，2022年，8月28日若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)

P(Sar)=P(S)+p(S)Pr第六頁，共二十八頁，2022年，8月28日P(0)0P(1)1p0設符號序列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第七頁，共二十八頁，2022年，8月28日累積概率遞推公式一般多元信源序列的累積概率遞推公式序列的概率(所對應區(qū)間的寬度)遞推公式第八頁，共二十八頁，2022年，8月28日實際中,求序列累積概率只需兩個存儲器,起始時可令:A(Φ)=1,P(Φ)=0

每輸入一個符號,存儲器P和A就按照上式更新一次,直至符號輸入完畢,這時存儲器P的內(nèi)容即為該序列的累積概率。累積概率遞推公式累積概率遞推計算注意：計算過程中,每輸入一個符號只要進行乘法和加法運算。第九頁，共二十八頁，2022年，8月28日通過信源符號序列累積概率計算,把區(qū)間分割成許多小區(qū)間,不同的信源符號序列對應不同的區(qū)間為[P(S),P(S)+p(S))，可取小區(qū)間內(nèi)的一點來代表這序列。將符號序列的累積概率寫成二進位小數(shù)，取小數(shù)點后L位,若后面有尾數(shù),就進位到第L位，即算術編碼若P(S)=0.10110001，L=3則C=0.110第十頁，共二十八頁，2022年，8月28日算術編碼的唯一可譯性由碼C的形成方法，又可知可知由此可見C必在,因而唯一可譯。對于長序列，p(S)必然很小，L與概率倒數(shù)對數(shù)幾乎相等，也就是說取整造成的差別很小，因而平均碼長將接近于信源熵H(S)第十一頁，共二十八頁，2022年，8月28日設二元無記憶信源S={0,1},p(0)=1/4,p(1)=3/4。S=11111100，對其做算術編碼。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從而得C=0.1101010，S的碼字為1101010解：p(S)=p2(0)p6(1)=(1/4)2(3/4)6例題1101001第十二頁，共二十八頁，2022年，8月28日+=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位第十三頁，共二十八頁，2022年，8月28日設無記憶信源U={a1,a2,a3,a4}，其概率分布依次為0.5,0.25,0.125,0.125，對信源序列做算術編碼。解：例題第十四頁，共二十八頁，2022年，8月28日序號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.10001101110108a11/163842269/4096140.10001101110100算術編碼遞推過程

a1,a2,

a3,a40.5,0.25,0.125,0.125第十五頁，共二十八頁，2022年，8月28日由算術編碼遞推表得C=0.

，從而U的碼字為

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