第7章 限失真信源編碼

信息論與編碼理論

第7章限失真信源編碼為什么允許存在失真連續(xù)信源其上有無(wú)窮多個(gè)點(diǎn)，但是傳輸時(shí)不可能傳輸無(wú)窮多個(gè)點(diǎn)，只能選擇有限個(gè)點(diǎn)傳輸?shù)怯糜邢蘧_表示無(wú)限是不可能的，失真必然存在離散信源信源符號(hào)的個(gè)數(shù)雖然是有限的，但有時(shí)為了提高壓縮效果，需要減少符號(hào)個(gè)數(shù)例如{0.5,1.0,1.5,2.0,2.5,3.0}壓縮為{1,2,3}，這必然引入失真信宿有時(shí)信宿不要求精確恢復(fù)消息，例如人眼、人耳等去掉信宿感覺(jué)不到的數(shù)據(jù)可以提高壓縮比，不過(guò)這樣也就帶來(lái)了失真Lena.bmp118KLena.jpg25K7.1失真的度量

7.1.1失真函數(shù)和失真矩陣由于進(jìn)行失真編碼，因此發(fā)送的數(shù)據(jù)與接收的數(shù)據(jù)之間有差別設(shè)離散無(wú)記憶信源（限失真信源編碼之前的數(shù)據(jù)）為接收端接收到的數(shù)據(jù)（限失真信源編碼之后的數(shù)據(jù)）為因此可以定義失真函數(shù)(或單個(gè)符號(hào)失真度)為：d(ui,vj)≥0,i=1,2,…,n;j=1,2,…,m用來(lái)度量信源發(fā)出符號(hào)為ui，接收符號(hào)為vj時(shí)所引起的誤差或失真失真矩陣信源U有n個(gè)符號(hào)，接收變量V有m個(gè)符號(hào)d(ui,vj)就有n×m個(gè)，可以排成矩陣形式，即：稱(chēng)為失真矩陣，是n×m階矩陣漢明失真如果誤碼失真的常數(shù)值為1，則稱(chēng)為漢明失真失真矩陣舉例【例】二元對(duì)稱(chēng)信源，信源U＝{0,1}，接收變量V＝{0,1}，在漢明失真定義下，失真函數(shù)為：d(0,0)＝d(1,1)＝0,d(0,1)＝d(1,0)＝1則失真矩陣為【例】設(shè)信源U＝{0,1},接收變量V＝{0,1,2}，失真函數(shù)為d(0,0)＝d(1,1)＝0,d(0,1)＝d(1,0)＝1,d(0,2)＝d(1,2)＝0.5則失真矩陣為【例】信源U＝{0,1,2},接收變量V＝{0,1,2},失真函數(shù)為d(ui,vj)＝(ui－vj)2由失真定義得d(0,0)＝d(1,1)＝d(2,2)＝0d(0,1)＝d(1,0)＝d(1,2)＝d(2,1)＝1d(0,2)＝d(2,0)＝4則失真矩陣為7.1.2序列失真

（N次擴(kuò)展信源失真）信源序列失真度（或失真函數(shù)）定義為：S=s1s2…sN——信源的一個(gè)輸出序列Y=y1y2…yN——信宿的一個(gè)接收序列sl——信源輸出序列中的一個(gè)符號(hào)yl——信宿接收序列中的一個(gè)符號(hào)例若信源序列S=01,Y=02則d(S,Y)=(d(0,0)+d(1,2))/2=(0+0.5)/3=0.25又若信源序列S=11,Y=02則d(S,Y)=(d(1,0)+d(1,2))/2=(1+0.5)/2=0.757.1.3平均失真和保真度準(zhǔn)則信源平均失真：ui——信源輸出符號(hào)，i＝1，2，…，np(ui)——信源輸出符號(hào)ui的概率vj——信宿接收符號(hào)，j＝1,2,…，mp(vj|ui)——信道傳遞概率含義：從總體上描述整個(gè)系統(tǒng)失真情況例信源U={0,1}，信宿V={0,1,2}信道失真矩陣則信源平均失真為保真度準(zhǔn)則保真度準(zhǔn)則指平均失真度不大于允許失真D，即：保真度準(zhǔn)則體現(xiàn)了限失真信源編碼中的“限”7.2信息率失真函數(shù)信息傳輸率R：平均每個(gè)碼元攜帶的信息量試驗(yàn)信道BD：將編碼過(guò)程看成一個(gè)信道，而且滿足保真度準(zhǔn)則失真越大編碼后的數(shù)據(jù)能夠提供的關(guān)于編碼前的數(shù)據(jù)的信息量越小需要通過(guò)試驗(yàn)信道傳輸?shù)男畔⒘吭叫⌒畔鬏斅试叫∫虼耍覀冴P(guān)注信息傳輸率的最小值而這個(gè)最小值又與允許的失真有關(guān)將這個(gè)信息傳輸率的最小值記作R(D)，這就是信息率失真函數(shù)即互信息越小關(guān)于率失真函數(shù)的說(shuō)明從所有滿足保真度準(zhǔn)則的試驗(yàn)信道中找到一個(gè)條件概率，使平均互信息最小，其實(shí)質(zhì)是選擇（設(shè)計(jì)）一種編碼方式，在滿足保真度準(zhǔn)則的條件下，使信息傳輸率最小，即保留的信息最少/失真最大，以達(dá)到壓縮比最高當(dāng)給定系統(tǒng)所允許的失真D之后，R(D)已經(jīng)是信息傳輸率的最小值，不能再小了。如果再小，系統(tǒng)將不滿足保真度準(zhǔn)則的要求。7.2.2信息率失真函數(shù)

定義域及性質(zhì)R(D)的定義域?yàn)?≤Dmin≤D≤DmaxDmin是允許的平均失真的最小值由于而其中的p(u)和d(u,v)是已知條件，因此所以對(duì)任意的ui，只要能夠找到一個(gè)vj，使得取最小值，則此時(shí)的平均失真就是Dmin假設(shè)d(ui,v*)是d(ui,v1),…,d(ui,vm)中最小的那一個(gè)，則的最小值就是d(ui,v*)此時(shí)在p(ui,v1),…,p(ui,vm)中，只有p(ui,v*)=1，其他的均為0這就意味著使得平均失真取Dmin的信道（編碼方法）也就確定了此時(shí)只要失真矩陣中每行有一個(gè)0，則Dmin=0。在實(shí)際應(yīng)用中，一般Dmin=0。例則使允許失真達(dá)到Dmin的信道為例則使允許失真達(dá)到Dmin的信道為DmaxR(D)是關(guān)于D的下凸函數(shù)，并嚴(yán)格遞減為什么求最小值？從圖中可以看出，當(dāng)D>Dmax時(shí)，R(D)也不再減小，仍然為0由于I(U,V)=0，因此此時(shí)的試驗(yàn)信道須滿足：使得U和V無(wú)關(guān)，即p(v|u)=p(v)，一般取例則使允許失真達(dá)到Dmax的信道為R(D)函數(shù)的性質(zhì)R(Dmin)≤H(U),R(Dmax)=0下凸連續(xù)單調(diào)遞減7.2.3信息率失真函數(shù)和信道容量的關(guān)系只有當(dāng)R(D)<C時(shí)，才能找到至少一個(gè)試驗(yàn)信道（即一種限失真信源編碼方法）滿足保真度準(zhǔn)則的要求。7.2.4保真度準(zhǔn)則下的信源編碼定理定理7-1（限失真信源編碼定理，香農(nóng)第三定理）設(shè)R(D)為離散無(wú)記憶信源U的信息率失真函數(shù)，R為信息傳輸率，D為允許失真，則當(dāng)信息率R>R(D)，只要信源序列長(zhǎng)度L足夠長(zhǎng)，一定存在一種編碼方法，其譯碼失真小于或等于D＋ε，ε為任意小的正數(shù)；反之，若R<R(D)，則無(wú)論采用什么樣的編碼方法，其譯碼失真必大于D。如果是二元信源，對(duì)于任意小的ε>0，每一個(gè)信源符號(hào)的平均碼長(zhǎng)滿足如下公式：限失真信源編碼定理的說(shuō)明該定理說(shuō)明在一定條件下滿足保真度準(zhǔn)則的編碼方法是存在的，但并未給出編碼步驟在給定允許失真D的情況下，所需信息率R的下限值，或信源信息壓縮的下限值，就是R(D)7.3量化編碼

7.3.1量化編碼的主要作用連續(xù)信號(hào)離散信號(hào)的轉(zhuǎn)換過(guò)程（A/D）：量化量化也是連續(xù)信源限失真編碼的主要方法常用量化方法標(biāo)量量化：各個(gè)樣本值分別量化（零記憶量化）矢量量化量化關(guān)心的主要問(wèn)題量化失真越小越好7.3.2均勻量化（線性量化）連續(xù)信源的取值范圍為[a0,an]，將[a0,an]均分為n個(gè)子區(qū)間，取每個(gè)小區(qū)間的中點(diǎn)值作為量化值yi=(ai+1+ai)/2量化失真（量化誤差）量化誤差：e=x-yi均方誤差：信噪比SNR（SignalNoiseRate）：7.3.3最優(yōu)量化最優(yōu)量化：使均方誤差最小或者信噪比最大的量化如何得到最值？一階導(dǎo)數(shù)為07.3.4矢量量化思想回想第二章講到的算術(shù)編碼和LZW編碼，對(duì)信源序列進(jìn)行編碼，目的是提高編碼效率受到這種思想的啟發(fā)，矢量量化編碼是對(duì)多個(gè)信源符號(hào)組成的矢量進(jìn)行量化編碼優(yōu)點(diǎn)自由度更大碼率可進(jìn)一步壓縮7.4預(yù)測(cè)編碼

7.4.1基本原理有記憶信源：信源先后發(fā)出的消息符號(hào)之間彼此依存（信源相關(guān)性）例1：自然語(yǔ)言例2：數(shù)字圖像我們、要、的、把、看、…碗、機(jī)、水、書(shū)、框、…基本原理預(yù)測(cè)編碼的基本原理：根據(jù)已經(jīng)得到的數(shù)據(jù)預(yù)測(cè)當(dāng)前數(shù)據(jù)的值?i（預(yù)測(cè)值），編碼僅對(duì)預(yù)測(cè)值?i和實(shí)際值ui之間的差（預(yù)測(cè)誤差）ei=ui-?i進(jìn)行編碼。為什么可以根據(jù)已經(jīng)得到的數(shù)據(jù)預(yù)測(cè)當(dāng)前數(shù)據(jù)的值？信源具有相關(guān)性因此預(yù)測(cè)編碼只適合于有記憶信源，對(duì)無(wú)記憶信源來(lái)講，預(yù)測(cè)編碼起不到壓縮的作用7.4.3DPCM編譯碼原理DPCM：差分脈沖編碼調(diào)制（DifferentialPulse-CodeModulation）預(yù)測(cè)值：?i=aui-1，其中a=1，a叫做預(yù)測(cè)系數(shù)編碼：如果ei>0，則編碼為1如果ei<0，則編碼為0譯碼：如果碼字為1，則增加一個(gè)固定的幅度Δ如果碼字為0，則減少一個(gè)固定的幅度Δ如何提高DPCM的精度提高采樣頻率，同時(shí)減小Δ采樣頻率越高，相鄰兩個(gè)采樣點(diǎn)之間的差別越?。ㄏ嚓P(guān)性越強(qiáng)）7.5變換編碼

7.5.1變換編碼基本原理時(shí)域（空域）頻域(1,2)空域數(shù)據(jù)頻域數(shù)據(jù)基基時(shí)域頻域變換時(shí)域頻域變換例2Matlab源代碼x=0:0.01:(4*pi);y0=5;y1=4*sin(x);y4=0.25*sin(8*x);ysum=y0+y1+y4;subplot(4,1,1);plot(x,y0);subplot(4,1,2);plot(x,y1);subplot(4,1,3);plot(x,y4);subplot(4,1,4);plot(x,ysum);4sin(x)0.25sin(8x)5+4sin(x)+0.25sin(8x)5空域數(shù)據(jù)sin(x)、sin(8x)：基540.25頻域數(shù)據(jù)直流系數(shù)（分量）低頻交流系數(shù)時(shí)域頻域變換高頻交流系數(shù)交流系數(shù)的值代表相應(yīng)頻率的能量，信號(hào)的能量主要集中在低頻。（信號(hào)的能量為信號(hào)幅度的和，即積分值）低頻表示信號(hào)的大體的趨勢(shì)，高頻表示信號(hào)的細(xì)節(jié)。7.5.2變換編碼能夠壓縮信源的原因解除信號(hào)相關(guān)性，提高壓縮效率傳輸時(shí)，只傳輸前面一部分低頻系數(shù)，而舍棄后面的高頻系數(shù)。540.25變換54壓縮反變換編碼譯碼9.5.3離散余弦（DCT）變換-3.0959-8.0022-1.86857.56435.43045.9623-4.9717-1.8566-0.148222.4009-4.58556.1522-1.2966-1.33085.9227-4.3259低頻高頻0.0166670.0066967-0.0043756-0.0262510.0014272-0.0048-0.00045128-0.017946-0.019903-0.00556390.00363880.031094-0.0067224-0.0139010.0045089-0.024418左上角數(shù)據(jù)