第四章有限失真信源編碼

第四章限失真信源編碼簡(jiǎn)介：和無(wú)失真編碼比較，（失真和熵率值比較）熵壓縮編碼在的允許失真條件下，編碼后的熵率壓縮到最小（無(wú)譯碼器）（解釋兩種編碼的必要性）信息速率失真函數(shù)R(D):是熵壓縮編碼的基礎(chǔ)，把信息和失真兩個(gè)度量可聯(lián)系在一起，為信號(hào)處理中同時(shí)考慮兩個(gè)因素提供可解。引入限失真的必要性1）

失真在傳輸中是不可避免的;2）

接收者（信宿）無(wú)論是人還是機(jī)器設(shè)備，都有一定的分辨能力與靈敏度，超過(guò)分辨能力與靈敏度的信息傳送過(guò)程是毫無(wú)意義的;3）

即使信宿能分辨、能判別，但對(duì)通信質(zhì)量的影響不大，也可以稱(chēng)它為允許范圍內(nèi)的失真；4）

我們的目的就是研究不同的類(lèi)型的客觀信源與信宿，在給定的Qos要求下的最大允許（容忍）失真D，及其相應(yīng)的信源最小信息率R(D).5）

對(duì)限失真信源，應(yīng)該傳送的最小信息率是R(D)，而不是無(wú)失真情況下的信源熵H(U).顯然

H(U)≥R(D).當(dāng)且僅當(dāng)D=0時(shí)，等號(hào)成立；6）

為了定量度量D，必須建立信源的客觀失真度量，并與D建立定量關(guān)系；7）

R(D)函數(shù)是限失真信源信息處理的理論基礎(chǔ)；本章節(jié)達(dá)到的目的理解限失真信源編碼在通信系統(tǒng)中的意義了解失真測(cè)度的含義和基本方法理解R(D)函數(shù)的概念、物理意義、性質(zhì)了解特殊情況下R(D)函數(shù)的計(jì)算方法了解R(D)函數(shù)在信道編碼定理中的作用理解香農(nóng)第三定理的物理意義及其實(shí)用意義了解香農(nóng)三大定理的相互關(guān)系與比較情況本章研究?jī)?nèi)容概述失真的度量信息率失真函數(shù)限失真信源編碼定理香農(nóng)三大定理的關(guān)系和比較§4.1:概述－1問(wèn)題引出無(wú)噪信道編碼定理回顧有噪信道編碼定理回顧存在的問(wèn)題：實(shí)際需求特點(diǎn)引出的研究?jī)?nèi)容本章節(jié)研究方法與順序§4.1:概述－2無(wú)噪信道編碼定理回顧：總可以找到一種輸入分布（信源編碼方法），使在無(wú)噪無(wú)損信道上，能夠以信道容量C無(wú)誤地傳輸信息。信源編碼無(wú)噪無(wú)損信道R=C;PE=0,最佳分布消息壓縮冗余度最好地利用C§4.1:概述－3有噪信道編碼定理回顧：只要R<C，總可以找到一種信道編碼方法，使在信道上能夠以盡可能小的PE傳輸信息。信源編碼信道R<C;PE=ε,消息信道編碼增加冗余度，最好地匹配信道特性§4.1:概述－4存在問(wèn)題對(duì)于連續(xù)和模擬信源H(S)=∞信道傳輸率R=H(S)/n（比特/碼符號(hào)）R=

∞平均碼長(zhǎng)l=Hr(S)=H(S)/logr,l=∞,實(shí)際上，因?yàn)锽有限，C一定有限，R<C,及l(fā)=∞均不可能§4.1:概述－5實(shí)際需求特點(diǎn)：信宿對(duì)真實(shí)度的要求：實(shí)際語(yǔ)音信號(hào)：20Hz~8KHz人耳能夠分辨：300Hz~3400Hz圖象色差：可達(dá)足夠多視覺(jué)分辨：256級(jí)（黑白）已足夠可以允許一定的失真度完全保真沒(méi)必要§4.1:概述－6引出的研究?jī)?nèi)容限失真的信源編碼問(wèn)題允許一定的失真度下，能將信源信息壓縮到什么程度？（最少需要多少比特才能在收端描述信源？）一定的信息傳輸率R下，允許的最大失真是多少？相關(guān)問(wèn)題失真如何度量？率失真函數(shù)如何計(jì)算？§4.1:概述－7研究方法：抽象信道虛擬試驗(yàn)信道§4.1:概述－8方法：抽象：將與討論重點(diǎn)關(guān)系小的部分抽象因?yàn)樯婕靶旁淳幋a，對(duì)信道進(jìn)行抽象信道編碼→信道→信道譯碼信道*信道*可以略去根據(jù)信道編碼定理信道*是一個(gè)沒(méi)有干擾的廣義信道，信宿收到信息的失真只來(lái)自于信源編碼§4.1:概述－9方法：虛擬：將討論重點(diǎn)虛擬細(xì)化將限失真信源的編譯碼過(guò)程虛擬信源編碼→信道*→信源譯碼試驗(yàn)信道可以用信道傳遞概率來(lái)描述限失真信源編譯碼前后的關(guān)系信源編碼信道編碼信道信道譯碼信源譯碼信源信宿信源編碼信道*信源譯碼信源信宿信源信宿試驗(yàn)信道UVP(V|U)§4.1:概述－10本章節(jié)討論順序從最簡(jiǎn)單的離散無(wú)記憶信源入手討論失真的度量討論率失真函數(shù)的定義和性質(zhì)討論在最簡(jiǎn)單的二進(jìn)制對(duì)稱(chēng)離散信源和高斯連續(xù)信源條件下率失真函數(shù)R(D)的計(jì)算方法討論限失真信源編碼定理信息率失真理論的探討及應(yīng)用舉例香農(nóng)三大定理的關(guān)系和比較§4.2:失真的度量－1失真度定義平均失真度保真度準(zhǔn)則試驗(yàn)信道§4.2:失真的度量－2失真度定義在U,V聯(lián)合空間上定義：d（ui，vj），ui∈U，vj∈V

為U,V的失真測(cè)度。d（ui，vj）有距離的概念性質(zhì)1：ui=vj時(shí)，d=0性質(zhì)2：mind=0性質(zhì)3：0<d<∞§4.2:失真的度量－3失真度定義0,ui=vj

離散信源：用失真矩陣描述。dij=>0,ui≠

vj

0,ui=vj

漢明距離度量時(shí)：dij=1,ui≠

vj連續(xù)信源：用失真函數(shù)描述。d(u,v)=(u-v)2=|u-v|

§4.2:失真的度量－4平均失真度單符號(hào)失真度：d（ui，vj）≥0，（i=1~r，j=1~s）信源的失真矩陣可表示為：共r×s個(gè)元素§4.2:失真的度量－5平均失真度平均失真度：∵U，V是隨機(jī)變量；∴d（ui，vj）也是隨機(jī)變量平均失真度：

§4.2:失真的度量－6平均失真度c.f:d&d：描述了某個(gè)信源符號(hào)通過(guò)傳輸后失真的大小不同的信源符號(hào)，其d不同。：描述了某一個(gè)單符號(hào)信源在某一試驗(yàn)信道傳輸下的失真，它不僅與單個(gè)符號(hào)的d有關(guān)，還與試驗(yàn)信道的統(tǒng)計(jì)特性有關(guān)。§4.2:失真的度量－7平均失真度N維信源符號(hào)序列的平均失真度：此時(shí)D為一rN×sN階的矩陣與：d（u，v）、p(u)、p(v|u)、N均有關(guān)§4.2:失真的度量－8平均失真度信源平均失真度信源、信道均無(wú)記憶時(shí)：信源平穩(wěn)時(shí)：序列中第l個(gè)分量的平均失真度§4.2:失真的度量－9保真度準(zhǔn)則給定D，若≤D，則稱(chēng)此為保真度準(zhǔn)則對(duì)于序列信源，保真度準(zhǔn)則為：≤ND§4.2:失真的度量－10試驗(yàn)信道：P(v|u)不是實(shí)際的信道特性矩陣，在此相當(dāng)于不同的編碼方法，不同的編碼方法，不同。定義：所有≤D的試驗(yàn)信道構(gòu)成D失真許可的試驗(yàn)信道集合BD§4.3:率失真函數(shù)－1問(wèn)題引出度量了失真，進(jìn)一步關(guān)心的問(wèn)題是：一定的失真D下，最小的信息傳輸率R是多少？一定的失真D下，收端再現(xiàn)信源需要的最低的平均信息量是多少？定義：（信息）率失真函數(shù)R(D)

對(duì)于N維序列信源：§4.3:率失真函數(shù)－2率失真函數(shù)的進(jìn)一步解釋單位：比特/信源符號(hào)（同互信息）離散無(wú)記憶信源：RN(D)=NR(D)P(v|u)無(wú)實(shí)際信道含義，只代表不同編碼方法求R(D)就是在D條件下，選擇一種編碼方法，使R最小。定義域：D∈[0,Dmax]R(D)的性質(zhì)：凸?fàn)钚詥握{(diào)遞減性連續(xù)性§4.3:率失真函數(shù)－3Dmax與R(Dmax)定義當(dāng)DDmax時(shí)，R(Dmax)=0使R(Dmax)=0的p(v|u)不止一個(gè)不同的p(v|u)有不同的|R(D)=0對(duì)我們有意義的：的最小值＝Dmax的p(v|u)利用該p(v|u)求得使R(Dmax)=0時(shí)的DmaxR=0時(shí)，U,V統(tǒng)計(jì)獨(dú)立p(v|u)只是v的函數(shù)則有：p(v|u)＝Q(v),Dmax=DmaxDR(D)R(D)>0R(D)=0§4.3:率失真函數(shù)－4R(D)的計(jì)算求解R(D)，--求解互信息的極小值互信息I(X,Y)是條件轉(zhuǎn)移概率的下凸函數(shù)極小值存在一般情況下很難得到R(D)的顯函數(shù)表達(dá)式，只能得到參量表達(dá)式具體計(jì)算很困難，一般利用計(jì)算機(jī)進(jìn)行迭代計(jì)算在一些特殊情況下，R(D)有顯式解。舉例(1)6.4PropertyofR(D)CalculationofR(D)ofbinarysymmetricsourceKnownconditions：二進(jìn)制對(duì)稱(chēng)信源U={0,1}，接收變量V={0,1}，允許的失真DP(u)=[ω，1－ω]，ω≤1/2漢明失真矩陣Stepstosolve：求Dmin=0

找到滿(mǎn)足最小失真的試驗(yàn)信道p(v|u),得到R(0)由漢明失真矩陣和失真度定義，計(jì)算最大允許的失真度Dmax=ω由Dmax，找到滿(mǎn)足最大失真的試驗(yàn)信道p,并得到R(Dmax)在一般條件下當(dāng)0<D<Dmax時(shí)，計(jì)算平均失真度=Pe選取一個(gè)信道，求互信息的最小值得到R(D)Verify：找到滿(mǎn)足R(D)的試驗(yàn)信道，驗(yàn)證其正確性Analysisoftheresult：R(D)曲線分析6.4PropertyofR(D)0.40.5DR(D)(比特/符號(hào)）ω＝0.3ω＝0.1ω＝0.2ω＝0.5對(duì)于同一個(gè)D：信源分布越均勻，R(D)就越大，信源壓縮的可能性越小反之，若信源分布越不均勻，即信源剩余度越大，R(D)就越小，壓縮的可能性就越大。二進(jìn)制對(duì)稱(chēng)信源的R(D)函數(shù)6.4PropertyofR(D)CalculationofR(D)ofGausssourceKnownconditions：高斯信源U，其均值為m，方差為σ2，接收變量V概密函數(shù)：失真函數(shù)：均方誤差失真，即：Stepstosolve：計(jì)算平均失真度當(dāng)≤D，求互信息求互信息的下限值得到包含有D和σ2的R(D)表達(dá)式討論D和σ2比值不同時(shí)R(D)的取值Verify：找到滿(mǎn)足R(D)的試驗(yàn)信道，驗(yàn)證其正確性Analysisoftheresult：R(D)曲線分析PropertyofR(D)0.00.81.0D/σ2R(D)(比特/自由度）當(dāng)D＝σ2時(shí)，R(D)＝0。即：如果允許失真等于信源的方差，則只需用均值m來(lái)表示信源輸出，而不需要傳送信源的任何實(shí)際輸出。當(dāng)D＝0時(shí)，R(D)∞。即：在連續(xù)信源情況下，要毫無(wú)失真地傳送連續(xù)信源必須要求信道具有無(wú)限大的容量。當(dāng)D＝0.25σ2時(shí),R(D)=1（比特/自由度）。即：允許均方誤差小于或等于σ2/4時(shí)，連續(xù)信號(hào)的每個(gè)樣本值最少需要用一個(gè)二元符號(hào)來(lái)傳輸。1.01.2高斯信源在均方誤差準(zhǔn)則下的R(D)函數(shù)Afourdimensionalsymmetricchannel,thesymbolreceivedis,itsdistortionmatrixis.Pleasecalculatethe,andthefunction,anddrawthegraphofittakingfourtofivepointswithit.Forn-dimensionalequalprobabilitysource,theratedistortionfunctionis.Inthisquestion,the.Sotheratedistortionfunctionis

.§4.4:限失真信源編碼定理－1限失真信源編碼定理限失真信源編碼定理的證明限失真信源編碼定理的實(shí)用意義§4.4:限失真信源編碼定理－2限失真信源編碼定理設(shè)R(D)為一離散無(wú)記憶平穩(wěn)信源的信息率失真函數(shù)，并且有有限的失真測(cè)度。對(duì)于任意D≥0，ε＞0，δ＞0以及任意足夠長(zhǎng)的碼長(zhǎng)n，則一定存在一種信源編碼C，其碼字個(gè)數(shù)為:M=exp{n［R(D)+ε］}而編碼后碼的平均失真度:d(C)≤D+δ如果用二元編碼，R(D)取比特為單位，則上式M可寫(xiě)成:M=2{n［R(D)+ε］}§4.4:限失真信源編碼定理－3定理解釋?zhuān)簩?duì)于任何失真度D≥0，只要碼長(zhǎng)n足夠長(zhǎng)，總可以找到一種編碼C，使編碼后每個(gè)信源符號(hào)的信息傳輸率:R′=logM/n=R(D)+ε即:R′≥R(D)而碼的平均失真度d(C)≤D。在允許失真D的條件下，信源最小的、可達(dá)的信息傳輸率是信源的R(D)?！?.4:限失真信源編碼定理－4限失真信源編碼定理的證明問(wèn)題：設(shè)有達(dá)到R(D)的試驗(yàn)信道p(v|u),要證明對(duì)于任意的R‘>R(D)時(shí)，存在一種信息傳輸率為R’的信源編碼，其平均失真度≤D+δ思路：產(chǎn)生碼書(shū)選取編譯碼方法計(jì)算失真度方法：產(chǎn)生碼書(shū)：在Vn空間隨機(jī)抽取M=2nR’個(gè)隨機(jī)序列v編碼方法：若存在與信源序列u構(gòu)成失真典型序列對(duì)的序列v(ω),則編碼uv(ω),否則編碼uv(1)譯碼：再現(xiàn)v(ω)失真度計(jì)算：在所有隨機(jī)碼書(shū)和Un空間統(tǒng)計(jì)平均的基礎(chǔ)上計(jì)算平均失真度§4.4:限失真信源編碼定理－5限失真信源編碼定理的幾點(diǎn)說(shuō)明只是一個(gè)存在性定理，沒(méi)有構(gòu)造方法存在問(wèn)題：符合實(shí)際信源的R(D)函數(shù)計(jì)算相當(dāng)困難信源統(tǒng)計(jì)特性的確切數(shù)學(xué)描述難得符合主客觀實(shí)際的失真測(cè)度難得R(D)計(jì)算本身困難即使求得了R(D)，還需研究最佳編碼方法才能達(dá)到極限值R(D)。§4.4:限失真信源編碼定理－6限失真信源編碼定理的實(shí)用意義如何進(jìn)行限失真信源編碼？舉例：R（D）的實(shí)用意義在允許一定失真的情況下，信源的R(D)函數(shù)可以作為衡量各種壓縮編碼方法性能優(yōu)劣的一種尺度。舉例：二進(jìn)制無(wú)記憶對(duì)稱(chēng)信源編譯碼：無(wú)噪無(wú)損信道傳輸舉例：結(jié)論

R’=1/3（比特/信源符號(hào)）該壓縮編碼方法下的信息傳輸率d(C)=1/4該壓縮編碼方法下的平均失真R(1/4)=1-H(1/4)=0.189(比特/信源符號(hào)）失真1/4下，最小的信息傳輸率R是0.189(比特/信源符號(hào)）R(1/4)<R’在1/4失真度下，該壓縮編碼方法不是最佳的，或該信源還可以壓縮§4.5:香農(nóng)三大定理的關(guān)系和比較－1

無(wú)失真信源編碼定理限失真信源編碼定理信源冗余度壓縮編碼信源的熵壓縮編碼無(wú)失真、保熵有失真、熵壓縮信源壓縮的極限值：信源熵H(S)信源壓縮的極限值：率失真函數(shù)R(D)存在性、構(gòu)造性存在性定理§4.4:香農(nóng)三大定理的關(guān)系和比較－2

信道編碼定理限失真信源編碼定理給定信道特性p=p(y|x)給定信源p=p(u)及失真測(cè)度d(u,v)對(duì)于假設(shè)的信源p=p(x)對(duì)于假設(shè)的試驗(yàn)信道p=p(v|u)尋求最優(yōu)的信道編碼C2尋求最優(yōu)的限失真編碼C3產(chǎn)生的誤碼率pe產(chǎn)生的最大失真D信道編碼存在的條件R<C限失真信源編碼存在的條件R>R(D)信道容量公式率失真函數(shù)公式存在符合條件的C2,使pe0存在符合條件的C3，使D’<D熵壓縮編碼重點(diǎn)介紹三種有代表性的方法1）量化標(biāo)量量化矢量量化2）變換編碼3）預(yù)測(cè)編碼習(xí)慣上對(duì)把矢量量化和變換編碼稱(chēng)為熵壓縮分組編碼，預(yù)測(cè)編碼稱(chēng)為熵壓縮樹(shù)碼前面提到就是允許一定D，把熵率壓縮最小，即，使率失真函數(shù)最小。Dmin123RD1為直接矢量量化；2為先作變換，再L-M算法；３對(duì)其各分量直接用L-M算法結(jié)論：矢量量化是熵壓縮分組編碼的最有效方法如圖①>②>③量化它包括標(biāo)量和矢量?jī)煞N，這是重點(diǎn)講標(biāo)量量化1

標(biāo)量量化適用范圍：連續(xù)無(wú)記憶信源2

標(biāo)量量化的概念：連續(xù)信號(hào)量化K個(gè)若干可能離散值舉例：A/D采集版量化量化概念A(yù)/D中的量化量化過(guò)程示意圖一個(gè)量化實(shí)例量化處理是使數(shù)據(jù)比特率下降的一個(gè)強(qiáng)有力的措施。量化輸入值動(dòng)態(tài)范圍很大，需要以多比特?cái)?shù)表示一個(gè)數(shù)值，量化輸出只能取有限個(gè)整數(shù)，稱(chēng)量化級(jí)。每個(gè)量化輸入被強(qiáng)迫歸一到與其接近的某個(gè)輸出，即量化到某個(gè)級(jí)。量化處理總是把一批輸入量化到一個(gè)輸出級(jí)上，所以量化是個(gè)多對(duì)一的處理過(guò)程，量化中由信息丟失，或者說(shuō)，會(huì)引起量化誤差（量化噪聲）。模擬量經(jīng)過(guò)A/D轉(zhuǎn)換，得到二進(jìn)制碼的過(guò)程，就是脈沖編碼調(diào)制（PCM）編碼過(guò)程，也稱(chēng)PCM編碼。A/D轉(zhuǎn)換中的采樣和量化分別是對(duì)時(shí)間和模擬量進(jìn)行數(shù)字化的過(guò)程。量化量化概念A(yù)/D中的量化量化過(guò)程示意圖一個(gè)量化實(shí)例輸入輸出閾值代表級(jí)量化曲線量化量化概念A(yù)/D中的量化量化過(guò)程示意圖一個(gè)量化實(shí)例24位標(biāo)準(zhǔn)圖像8位（256色）標(biāo)準(zhǔn)圖像量化量化概念A(yù)/D中的量化量化過(guò)程示意圖一個(gè)量化實(shí)例預(yù)測(cè)編碼方法基本原理從相鄰數(shù)據(jù)之間有很強(qiáng)的相關(guān)性特點(diǎn)考慮，可以利用前面已經(jīng)出現(xiàn)的數(shù)值，進(jìn)行預(yù)測(cè)（估計(jì)），得到一個(gè)預(yù)測(cè)值，將實(shí)際值與預(yù)測(cè)值求差，對(duì)這個(gè)差值信號(hào)進(jìn)行編碼、傳送，這種編碼方法即成為預(yù)測(cè)編碼方法。預(yù)測(cè)編碼最佳的預(yù)測(cè)編碼：en=yn-un最小有三種不同的標(biāo)準(zhǔn)：最小均方誤差；最小平均絕對(duì)誤差；最大零誤差概率；DPCM基本原理轉(zhuǎn)入f(i,j)e(i,j)量化器預(yù)測(cè)器預(yù)測(cè)器編碼器解碼器信道傳輸e’(i,j)f’(i,j)輸出f(i,j)f’(i,j)f’(i,j)f(i,j)DPCM編、解碼原理圖預(yù)測(cè)編碼不帶量化器的DPCM線性預(yù)測(cè)編碼，屬于無(wú)失真編碼系統(tǒng)；帶有量化器的DPCM線性預(yù)測(cè)編碼，屬于有失真編碼系統(tǒng)。DPCM線性預(yù)測(cè)系統(tǒng)是一個(gè)負(fù)反饋系統(tǒng)，對(duì)誤差有收斂性。發(fā)送端與接收端之間的誤差等于量化誤差。最佳量化器的設(shè)計(jì)，可利用人眼的視覺(jué)可見(jiàn)度閾值和視覺(jué)掩蔽效應(yīng)等生理特征，來(lái)確定量化器的級(jí)數(shù)和步距，使量化誤差總處于人眼難以覺(jué)察的范圍內(nèi)，達(dá)到主觀評(píng)定準(zhǔn)則的要求。

最佳量化預(yù)測(cè)編碼自適應(yīng)預(yù)測(cè)編碼ADPCM自適應(yīng)技術(shù)的概念是：預(yù)測(cè)器的預(yù)測(cè)系數(shù)和量化器的量化參數(shù)，能夠根據(jù)圖像的局部區(qū)域分布特點(diǎn)自動(dòng)調(diào)整。實(shí)踐證明，ADPCM編、解碼系統(tǒng)與DPCM編、解碼系統(tǒng)相比，不僅能改善恢復(fù)圖像的評(píng)測(cè)質(zhì)量和視覺(jué)效果，同時(shí)還能進(jìn)一步壓縮數(shù)據(jù)。ADPCM系統(tǒng)包括自適應(yīng)預(yù)測(cè)，即預(yù)測(cè)系數(shù)的自適應(yīng)調(diào)整和自適應(yīng)量化，即量化器參數(shù)的自適應(yīng)調(diào)整兩部分內(nèi)容。預(yù)測(cè)編碼變換編碼原理定義：將空域圖像信號(hào)映射變換到另一個(gè)正交矢量空間（變換域或頻域），產(chǎn)生一批變換系數(shù)，對(duì)系數(shù)進(jìn)行編碼處理原理：信號(hào)在時(shí)域描述時(shí)信息冗余度大，變換后，參數(shù)獨(dú)立，去掉相關(guān)性，減少