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

信息論第講算術(shù)編碼與編碼第一頁，共二十八頁，2022年，8月28日算術(shù)編碼前面所討論的無失真編碼，都是建立在信源符號(hào)與碼字一一對(duì)應(yīng)的基礎(chǔ)上，這種編碼方法通常稱為塊碼或分組碼，此時(shí)信源符號(hào)一般是多元的。如果要對(duì)二元序列進(jìn)行編碼，則需采用合并信源符號(hào)方法，把二元序列轉(zhuǎn)換成多值符號(hào)，轉(zhuǎn)換時(shí)二元符號(hào)之間的相關(guān)性不予考慮，轉(zhuǎn)換后這些多值符號(hào)之間的相關(guān)性也不予考慮。這就使信源編碼的匹配原則不能充分滿足，編碼效率一般不高。為了克服這種局限性，需要跳出分組碼范疇，從整個(gè)符號(hào)序列出發(fā)，采用遞推形式進(jìn)行編碼。第二頁，共二十八頁，2022年，8月28日從整個(gè)符號(hào)序列出發(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)隨著序列的長(zhǎng)度不斷增加,C所在區(qū)間的長(zhǎng)度就越短,精確地確定C的位置需要碼長(zhǎng)也不斷增加第三頁，共二十八頁，2022年，8月28日

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

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

累積概率r=1,2,…,npr=Pr+1-PrP1p1P2P3P41p2p3……0第四頁，共二十八頁，2022年，8月28日當(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)第五頁，共二十八頁，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設(shè)符號(hào)序列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日累積概率遞推公式一般多元信源序列的累積概率遞推公式序列的概率(所對(duì)應(yīng)區(qū)間的寬度)遞推公式第八頁，共二十八頁，2022年，8月28日實(shí)際中,求序列累積概率只需兩個(gè)存儲(chǔ)器,起始時(shí)可令:A(Φ)=1,P(Φ)=0

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

a1,a2,

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