信息論與編碼-第五章(續(xù)2)

信息論與編碼-第五章(續(xù)2)第一頁，共44頁。信息論與編碼-限失真信源編碼

定理說明，在允許失真為D的條件下，信源最小可達(dá)的信息傳輸率是信源的R(D)。保真度準(zhǔn)則下的信源編碼定理（限失真信源編碼定理）是有失真信源壓縮的理論基礎(chǔ)。定理說明了在允許失真D確定后，總存在一種編碼方法，使編碼的信息傳輸率大于R(D)且可以任意接近R(D)，而平均失真度小于允許失真D。而當(dāng)信息傳輸率小于R(D)時(shí)，編碼的平均失真將大于D。可見，R(D)是允許失真度為D的情況下信源信息壓縮的下限值。第二頁，共44頁。信息論與編碼-限失真信源編碼比較香農(nóng)第一定理和香農(nóng)第三定理可知，當(dāng)信源給定后，無失真信源壓縮的極限值是信源熵H(X)，而有失真信源壓縮的極限值是信息率失真函數(shù)R(D)。在給定D后，一般R(D)<H(X)。R(D)可以作為衡量各種壓縮編碼方法性能優(yōu)劣的一種尺度。但香農(nóng)第三定理同樣是一個(gè)指出存在性的定理，至于如何尋找這種最佳壓縮編碼方法，定理中沒有給出。在實(shí)際應(yīng)用中，該理論主要存在以下兩類問題：第三頁，共44頁。信息論與編碼-限失真信源編碼（1）符合實(shí)際信源的R(D)函數(shù)的計(jì)算相當(dāng)困難。首先，需要對(duì)實(shí)際信源的統(tǒng)計(jì)特性有確切的數(shù)學(xué)描述，其次，需要符合主客觀實(shí)際的失真度量。這些都不是很容易的事情。即使有了這些，率失真函數(shù)的計(jì)算也是相當(dāng)困難的。（2）即使求得了符合實(shí)際的信息率失真函數(shù)，還需要研究采用何種編碼方法，才能達(dá)到或接近極限值R(D)。第四頁，共44頁。信息論與編碼-限失真信源編碼

常用信源編碼方法簡(jiǎn)介

1.游程編碼在二元序列中，只有“0”和“1”兩個(gè)碼元，我們把連續(xù)出現(xiàn)的“0”叫做“0”游程，連續(xù)出現(xiàn)的“1”叫做“1”游程。連續(xù)出現(xiàn)“0”或者“1”碼元的個(gè)數(shù)叫做游程長(zhǎng)度。這樣，一個(gè)二元序列可以轉(zhuǎn)換成游程序列，例如：二元序列00010可以變換成，若規(guī)定游程必須從“0”游程開始，則上述變換是可逆的。如果連“0”或連“1”非常多，則可以達(dá)到信源壓縮的目的。游程編碼是無失真信源編碼。第五頁，共44頁。信息論與編碼-限失真信源編碼2.矢量量化連續(xù)信源進(jìn)行編碼的主要方法是量化，即將連續(xù)的樣值離散化成為。n是量化級(jí)數(shù)，這樣就把連續(xù)值轉(zhuǎn)化為n個(gè)實(shí)數(shù)中的一個(gè)，可以用0，1，2，…，n等n個(gè)數(shù)字來表示。由于是一個(gè)標(biāo)量，因此稱為標(biāo)量量化。在量化的過程中，將會(huì)引入失真，量化時(shí)必須使這些失真最小。第六頁，共44頁。信息論與編碼-限失真信源編碼要想得到更好的性能，僅采用標(biāo)量量化是不可能的。從前面的討論我們已經(jīng)知道，把多個(gè)信源符號(hào)組成一個(gè)符號(hào)序列進(jìn)行聯(lián)合編碼可以提高編碼效率。連續(xù)信源也是如此，當(dāng)把多個(gè)信源符號(hào)聯(lián)合起來形成多維矢量，然后進(jìn)行量化，可以進(jìn)一步壓縮碼率，這種量化方法叫做矢量量化。第七頁，共44頁。信息論與編碼-限失真信源編碼實(shí)驗(yàn)證明，即使各信源符號(hào)相互獨(dú)立，矢量量化也可以壓縮信息率，因此，人們對(duì)矢量量化非常感興趣，是當(dāng)前信源編碼的一個(gè)熱點(diǎn)，而且不僅限于連續(xù)信源，對(duì)離散信源也可以如此。如圖像編碼時(shí)采用矢量量化，但由于聯(lián)合概率密度不易測(cè)定，目前常用的是訓(xùn)練序列的方法，如圖像編碼時(shí)就要采用訓(xùn)練序列的方法，進(jìn)行量化。還可以與神經(jīng)網(wǎng)絡(luò)方法結(jié)合，利用神經(jīng)網(wǎng)絡(luò)的自組織來得到訓(xùn)練集。

第八頁，共44頁。信息論與編碼-限失真信源編碼3.預(yù)測(cè)編碼預(yù)測(cè)就是從已收到的符號(hào)來提取關(guān)于未收到的符號(hào)的信息，從而預(yù)測(cè)其最可能的值作為預(yù)測(cè)值。并把它與實(shí)際值之差進(jìn)行編碼，由于這個(gè)差值一般都比較小，所以在編碼時(shí)會(huì)出現(xiàn)很多連“0”值，再采用游程編碼，就可以大大地壓縮碼率。由此可見，預(yù)測(cè)編碼是利用信源符號(hào)之間的相關(guān)性來壓縮碼率的，對(duì)于獨(dú)立信源，預(yù)測(cè)就沒有可能。第九頁，共44頁。信息論與編碼-限失真信源編碼4.變換編碼變換是一個(gè)廣泛的概念。變換編碼就是經(jīng)變換后的信號(hào)能更有效地編碼，也就是通過變換來解除或減弱信源符號(hào)間的相關(guān)性，以達(dá)到壓縮碼率的效果（如單頻率正弦波信號(hào)，變換到頻域）。一般地，對(duì)一個(gè)函數(shù)，變換式為：第十頁，共44頁。信息論與編碼-限失真信源編碼而反變換為：要使上式成立，要求必須是正交完備的（相當(dāng)于歐氏空間的坐標(biāo)投影），求的公式，實(shí)際上就是內(nèi)積運(yùn)算，把函數(shù)投影到上去。第十一頁，共44頁。信息論與編碼-限失真信源編碼信源編碼常用的變換有：DCT（discreteCosineTransform）變換：如JPEG、MPEG等圖像壓縮標(biāo)準(zhǔn)中，就是主要采用的這種變換壓縮方法。K-L變換：K-L變換是均方誤差準(zhǔn)則下的最佳變換。它是一種正交變換，變換后的隨機(jī)變量之間互不相關(guān)，一般認(rèn)為，K-L變換是最佳變換，其最大缺點(diǎn)是計(jì)算復(fù)雜，除了需要測(cè)定相關(guān)函數(shù)和解積分方程外，變換時(shí)的運(yùn)算也十分復(fù)雜，也沒有快速算法，因此，K-L變換不是一種實(shí)用的變換編碼方法，但經(jīng)常用來作為標(biāo)準(zhǔn)，評(píng)估其他方法的優(yōu)劣。第十二頁，共44頁。信息論與編碼-限失真信源編碼小波（WaveletTransform）變換：小波變換是當(dāng)前信號(hào)處理以及多種應(yīng)用科學(xué)中廣泛用到的一種相當(dāng)有效的數(shù)學(xué)工具。小波變換的概念首先是由法國的石油地質(zhì)工程師J.Morlet于1980年提出的，1990年Mallat等人一起建立了多分辯分析的概念。與經(jīng)典的Fourier分析相比較，小波的最大優(yōu)勢(shì)是變換本身具有時(shí)間與頻率的雙重局部性質(zhì)，解決了Fourier分析不能處理的許多實(shí)際問題，因而小波變換被人們稱之為“數(shù)學(xué)顯微鏡”。第十三頁，共44頁。信息論與編碼-限失真信源編碼20世紀(jì)90年代中期以前，圖像壓縮主要采用離散余弦變換(DCT)技術(shù)，著名的JPEG、H.263等圖像壓縮國際標(biāo)準(zhǔn)均采用DCT方法實(shí)現(xiàn)圖像壓縮。而DCT最大的缺陷是當(dāng)壓縮比較大時(shí)，會(huì)出現(xiàn)馬賽克效應(yīng)，因而影響圖像壓縮質(zhì)量。最近幾年來，由于小波變換具有DCT無可比擬的良好壓縮性質(zhì)，在最新推出的靜態(tài)圖像壓縮國際標(biāo)準(zhǔn)JPEG2000中，9/7雙正交小波變換已經(jīng)正式取代DCT而作為新的標(biāo)準(zhǔn)變換方法。第十四頁，共44頁。信息論與編碼-限失真信源編碼分形（FractalTransform）變換：基于塊的分形編碼是一種利用圖像的自相似性來減少圖象冗余度的新型編碼技術(shù)，它具有以下特點(diǎn)：(1)較高的壓縮比。(2)解碼圖象的分辨率無關(guān)性。可按任意高于或低于原編碼圖象的分辨率來進(jìn)行解碼。當(dāng)要解碼成較高分辨率圖象時(shí)，引入的細(xì)節(jié)會(huì)與整個(gè)圖象大致和諧一致，從而比象素復(fù)制或插值方法得到的圖象看起來更自然。這種縮放能力也可以用作圖象增強(qiáng)工具。第十五頁，共44頁。信息論與編碼-限失真信源編碼（3）解碼速度快。分形壓縮是一非對(duì)稱過程，雖然編碼很耗時(shí)，但解碼速度快，因此較適用于一次編碼多次解碼的應(yīng)用中。（4）編碼時(shí)間過長(zhǎng)，實(shí)時(shí)性差，從而阻礙了該方法在實(shí)際中的廣泛應(yīng)用。還有很多其他的編碼方法，這里就不再一一介紹了。第十六頁，共44頁。信息論與編碼-限失真信源編碼5.算術(shù)編碼算術(shù)編碼也是一種無失真信源編碼方法。前面討論的無失真信源編碼方法，都是針對(duì)單個(gè)信源符號(hào)的編碼，當(dāng)信源符號(hào)之間有相關(guān)性時(shí)，這些編碼方法由于沒有考慮到符號(hào)之間的相關(guān)性，因此編碼效率就不可能很高。解決的辦法是對(duì)較長(zhǎng)的信源序列進(jìn)行編碼，但會(huì)遇到與定長(zhǎng)編碼時(shí)同樣的問題。而且，采用前面的序列編碼需要完全知道聯(lián)合概率和條件概率，這在場(chǎng)合下也是比較困難的。第十七頁，共44頁。信息論與編碼-限失真信源編碼為了解決這個(gè)問題，需要跳出分組碼的局限，研究非分組碼。算術(shù)編碼就是一種非分組編碼方法。其基本思路是：從全序列出發(fā)，將不同的信源序列的累計(jì)概率映射到[0，1]區(qū)間上，使每個(gè)序列對(duì)應(yīng)區(qū)間上的一點(diǎn)，也就是說，把區(qū)間[0，1]分成許多互不重疊的小區(qū)間，不同的信源序列對(duì)應(yīng)不同的小區(qū)間可以證明，只要這些小區(qū)間互不重疊，就可以編得即時(shí)碼。第十八頁，共44頁。信息論與編碼-限失真信源編碼這種編碼方法無需計(jì)算出所有信源序列的概率分布及編出碼表，可以直接對(duì)輸入的信源符號(hào)序列進(jìn)行編碼輸出。算術(shù)編碼的主要編碼方法就是計(jì)算信源符號(hào)序列所對(duì)應(yīng)的小區(qū)間。下面我們討論如何找出信源符號(hào)序列所對(duì)應(yīng)的區(qū)間。設(shè)信源符號(hào)集，其相應(yīng)的概率分布為。第十九頁，共44頁。信息論與編碼-限失真信源編碼定義信源符號(hào)的累積分布函數(shù)為則對(duì)二元序列有：現(xiàn)在，來計(jì)算信源序列的累積分布函數(shù)。只討論二元無記憶信源，結(jié)果可推廣到一般情況。第二十頁，共44頁。信息論與編碼-限失真信源編碼初始時(shí)，在[0，1）區(qū)間內(nèi)由F(1)劃分成二個(gè)子區(qū)間[0，F(xiàn)(1)）和[F(1)，1），F(xiàn)(1)=p(0)。子區(qū)間[0，F(xiàn)(1)]的寬度為A(0)=p(0)，子區(qū)間[F(1)，1）的寬度為A(1)=p(1)。子區(qū)間[0，F(xiàn)(1)]對(duì)應(yīng)于信源符號(hào)“0”，子區(qū)間[F(1)，1）對(duì)應(yīng)于信源符號(hào)“1”。若輸入符號(hào)序列的第一個(gè)符號(hào)為s=“0”，即落入相應(yīng)的區(qū)間為[0，F(xiàn)(1)),得F(s=“0”)=F(0)=0。即某序列累積概率分布函數(shù)為該序列所對(duì)應(yīng)區(qū)間的下界值。第二十一頁，共44頁。信息論與編碼-限失真信源編碼當(dāng)輸入的第二個(gè)符號(hào)為“1”時(shí)，s=“01”，s=“01”所對(duì)應(yīng)的區(qū)間是在[0，F(xiàn)(1)）中進(jìn)行分割。符號(hào)序列“00”對(duì)應(yīng)的區(qū)間寬度為A(00)=A(0)p(0)=p(0)p(0)；符號(hào)序列“01”對(duì)應(yīng)的區(qū)間寬度為A(01)=A(0)p(1)=p(0)p(1)=p(01)，也等于A(01)=A(0)-A(00)。”00”對(duì)應(yīng)的區(qū)間為[0，F(xiàn)(s=“01”))；”01”對(duì)應(yīng)的區(qū)間為[F(s=“01”)，F(xiàn)(1))。其中F(s=“01”)是符號(hào)序列“01”區(qū)間的下界值，可見，F(xiàn)(s=“01”)=p(0)p(0)正是符號(hào)序列s=“01”的累計(jì)分布函數(shù)。第二十二頁，共44頁。信息論與編碼-限失真信源編碼當(dāng)輸入符號(hào)序列中第三個(gè)符號(hào)為“1”時(shí)，因前面已輸入序列為s=“01”，所以可記做輸入序列為s1=“011”（若第三個(gè)符號(hào)輸入為“0”，可記做s0=“010”）。現(xiàn)在，輸入序列s1=“011”所對(duì)應(yīng)的區(qū)間是對(duì)區(qū)間[F(s)，F(xiàn)(1)）進(jìn)行分割。序列s0=“010”對(duì)應(yīng)的區(qū)間寬度為A(s0=“010”)=A(s=“01”)p(0)=A(s)p(0)，其對(duì)應(yīng)的區(qū)間為[F(s)，F(xiàn)(s)+A(s)p(0))。而序列s1=“011”對(duì)應(yīng)的區(qū)間寬度為A(s1=“011”)=A(s)p(1)=A(s=“01”)-A(s0=“010)，第二十三頁，共44頁。信息論與編碼-限失真信源編碼即A(s1=“011”)=A(s)-A(s0)，其對(duì)應(yīng)的區(qū)間為[F(s)+A(s)p(0),F(1))?？梢姡?hào)序列s1=“011”的累計(jì)概率分布函數(shù)為F(s1)=F(s)+A(s)p(0)。若第三個(gè)符號(hào)輸入為“0”，由上述分析可得，符號(hào)序列s0=“010”的區(qū)間下界值仍為F(s)，所以符號(hào)s0=“010”的累計(jì)分布函數(shù)為F(s0)=F(s)。現(xiàn)已輸入三個(gè)符號(hào)串，將這符號(hào)序列標(biāo)為s，接著輸入第四個(gè)符號(hào)為“0”或“1”，又可計(jì)算出s0=“0110”或s1=“0111”對(duì)應(yīng)的子區(qū)間及其累積分布函數(shù)。第二十四頁，共44頁。信息論與編碼-限失真信源編碼根據(jù)前面的分析，可歸納出：當(dāng)已知前面輸入符號(hào)序列s，若接著輸入一個(gè)符號(hào)“0”，序列s0的累計(jì)分布函數(shù)為

F(s0)=F(s)對(duì)應(yīng)區(qū)間寬度為A(s0)=A(s)p(0)若接著輸入的一個(gè)符號(hào)是“1”，序列s1的累計(jì)分布函數(shù)為

F(s1)=F(s)+A(s)p(0)對(duì)應(yīng)的區(qū)間寬度為A(s1)=A(s)p(1)=A(s)-A(s0)第二十五頁，共44頁。信息論與編碼-限失真信源編碼由前面的分析又知，符號(hào)序列對(duì)應(yīng)的區(qū)間寬度為

A(s=“0”)=p(0);A(s=“1”)=1-A(s=“0”)=p(1);A(s=“00”)=A(0)p(0)=p(0)p(0)=p(00);

A(s=“01”)=A(s=“0”)-A(s=“00”)=A(0)p(1)=p(0)p(1)=p(01);第二十六頁，共44頁。信息論與編碼-限失真信源編碼

A(s=“10”)=A(1)p(0)=p(1)p(0)=p(10);A(s=“11”)=A(s=“1”)-A(s=“10”)=A(1)p(1)=p(1)p(1)=p(11);

A(s=“010”)=A(s=“01”)p(0)=p(01)p(0)=p(010);A(“011”)=A(s=“01”)-A(s=“010”)=A(s=“01”)p(1)=p(01)p(1)=p(011);…由此可得，信源符號(hào)序列s對(duì)應(yīng)的區(qū)間寬度等于符號(hào)序列s的概率p(s)。第二十七頁，共44頁。信息論與編碼-限失真信源編碼綜合上述幾個(gè)式子，可得二元信源符號(hào)序列的累計(jì)分布函數(shù)的遞推公式為

F(sr)=F(s)+p(s)F(r)(r=0,1)其中sr表示已知前面信源符號(hào)序列為s，接著再輸入符號(hào)為r。同樣，可得信源符號(hào)序列所對(duì)應(yīng)區(qū)間寬度的遞推公式為

A(sr)=p(sr)=p(s)p(r)因此，當(dāng)已輸入的二元信源符號(hào)序列為s=“011”，若接著輸入符號(hào)為“1”，得累積分布函數(shù)為第二十八頁，共44頁。信息論與編碼-限失真信源編碼F(s1)=F(0111)=F(s=“011”)+p(011)p(0)=F(s=“01”)+p(01)p(0)+p(011)p(0)=F(s=“0”)+p(0)p(0)+p(01)p(0)+p(011)p(0)=0+p(00)+p(010)+p(0110)其對(duì)應(yīng)的區(qū)間寬度為A(s1)=A(s=“011”)p(1)=p(011)p(1)=p(0111)第二十九頁，共44頁。信息論與編碼-限失真信源編碼由于累積分布函數(shù)和子區(qū)間寬度都是遞推公式，因此在實(shí)際應(yīng)用中，只需要兩個(gè)存儲(chǔ)器，把p(s)和F(s)存下來，然后隨著符號(hào)的輸入，不斷地更新兩個(gè)存儲(chǔ)器中的數(shù)值。因?yàn)樵诰幋a過程中，沒輸入一個(gè)符號(hào)要進(jìn)行乘法和加法運(yùn)算，所以稱這種編碼方法為算術(shù)編碼。很容易將其推廣到多元信源序列?？梢缘玫揭话阈旁蛄械睦塾?jì)分布函數(shù)和區(qū)間寬度的遞推公式為

第三十頁，共44頁。信息論與編碼-限失真信源編碼通過關(guān)于信元符號(hào)序列的累計(jì)分布函數(shù)計(jì)算，F(xiàn)(s)可以把區(qū)間[0，1）分割成許多小區(qū)間，不同的信元符號(hào)序列對(duì)應(yīng)于不同的區(qū)間為[F(s),F(s)+p(s)）。可取小區(qū)間內(nèi)的一點(diǎn)來代表這序列。如何選擇這個(gè)點(diǎn)？將符號(hào)序列的累計(jì)分布函數(shù)寫成二進(jìn)制小數(shù)，取小數(shù)點(diǎn)后l位，若后面有尾數(shù)，則進(jìn)位到第l位，這樣得到的一個(gè)數(shù)C，并使l滿足：第三十一頁，共44頁。信息論與編碼-限失真信源編碼設(shè)，取0或者1，得符號(hào)s的碼字為。這樣選取的數(shù)值C，根據(jù)二進(jìn)制小數(shù)截去位數(shù)的影響，得當(dāng)F(s)在l位以后沒有尾數(shù)時(shí)，C=F(s)。另外，由可知，，則信源符號(hào)序列第三十二頁，共44頁。信息論與編碼-限失真信源編碼S對(duì)應(yīng)區(qū)間的上界可見，數(shù)值C在區(qū)間[F(s)，F(xiàn)(s)+p(s)）內(nèi)。不同的信源序列對(duì)應(yīng)的不同區(qū)間（左封右開的區(qū)間）式不重疊的，所以編得的碼是即時(shí)碼。符號(hào)序列s的平均碼長(zhǎng)滿足：第三十三頁，共44頁。信息論與編碼-限失真信源編碼平均每個(gè)信源符號(hào)的碼長(zhǎng)為對(duì)無記憶信源，有因此有第三十四頁，共44頁。信息論與編碼-限失真信源編碼可以看出，算術(shù)編碼的編碼效率是比較高的。當(dāng)信源符號(hào)序列很長(zhǎng)時(shí)，n很大，平均碼長(zhǎng)接近于信源的符號(hào)熵。例題：設(shè)二元無記憶信源s={0,1}，其p(0)=1/4，p(1)=3/4。對(duì)二元序列s=11111100做算術(shù)編碼。解：第三十五頁，共44頁。信息論與編碼-限失真信源編碼于是過程是這樣的：先來一個(gè)1，F(xiàn)(s)=p(0)，又來一個(gè)1，F(xiàn)(s1)=F(s)+p(s)F(1)=p(0)+p(1)p(0)=p(0)+p(10)，…轉(zhuǎn)換成二進(jìn)制小數(shù)為：F(s)=0.110100100111第三十六頁，共44頁。信息論與編碼-限失真信源編碼得C=0.1101010，s的碼字為。編碼效率為譯碼就是一系列的比較過程。每一步比較C-F(s)與p(s)p(0)。s為前面已譯出的序列串，得p(s)為序列串s對(duì)應(yīng)的寬度，F(xiàn)(s)是序列串s的累計(jì)分布函數(shù)，即為s對(duì)應(yīng)區(qū)間的下界。p(s)p(0)是此區(qū)間內(nèi)下一個(gè)輸入為符號(hào)“0”所占的字區(qū)間寬度。所第三十七頁，共44頁。信息論與編碼-限失真信源編碼以，得以上一個(gè)例題為例，C=0.1101010，p(0)=0.01，起始時(shí)，F(xiàn)(s)=0,p(s)=1。第一步：C-F(s)>p(s)p(0)，譯出一個(gè)“1”；第二步：此時(shí)，F(xiàn)(s)=p(0)=0.01，p(s)=p(1)=0.11，

C-F(s)=0.1001010，p(s)p(0)=0.0011，又譯出一個(gè)“1”；第三十八頁，共44頁。信息論與編碼-限失真信源編碼第三步：此時(shí)，F(xiàn)(s)=p(0)+p(10)=0.01+0.0011=0.0111，p(s)=0.1001，p(s)p(0)=0.001001，C-F(s)=0.011001，又譯出一個(gè)“1”；第四步：此時(shí)，F(xiàn)(s)=0.0111+p(110)=0.10011，p(s)=0.011011，p(s)p(0)=0.00011011，

C-F(s)=0.001111，又譯出一個(gè)“1”；第五步：此時(shí)，F(xiàn)(s)=0.10011+p(1110)=0.10110011，p(s)=0.010100