信息論與編碼信息率失真函數(shù)與限失真編碼市公開課一等獎百校聯(lián)賽特等獎?wù)n件

1第5章信息率失真函數(shù)

與限失真編碼信道編碼定理即使告訴我們，有噪聲信道無失真編碼似乎是可能，不過，這里無失真只能無限迫近于0，而無法到達0，除非編碼分組長度是無窮大，所以從這個角度，有噪聲信道無失真要求也是不可能。然而在實際生活中，人們普通并不要求完全無失真恢復(fù)信息，通常要求在確保一定質(zhì)量(一定確保度)條件下再現(xiàn)原來消息，也就是說允許失真存在。學(xué)習得來終覺淺，絕知此事要自悟第1頁2

第5章信息率失真函數(shù)

與限失真編碼

不一樣要求允許不一樣大小失真存在，完全無失真通信既不可能也無必要，有必要進行將失真控制在一定程度內(nèi)壓縮編碼，我們稱為限失真編碼。

信息率失真理論是進行量化、數(shù)模轉(zhuǎn)換、頻帶壓縮和數(shù)據(jù)壓縮理論基礎(chǔ)。本章主要介紹信息率失真理論基本內(nèi)容及相關(guān)編碼方法。第2頁第5章信息率失真函數(shù)

與限失真編碼怎樣進行這種限失真編碼呢？考慮我們前面提出問題，假如要將有10萬位小數(shù)1-100之間數(shù)字進行壓縮，我們能夠采取四舍五入方法，將這個數(shù)轉(zhuǎn)換為只有10位小數(shù)數(shù)值，因為小數(shù)點10位之后數(shù)值都是微不足道，所以這種壓縮帶來失真并不大。我們能夠了解為將一個集合中元素映射為另外一個集合中壓縮，或者是映射為原集合中一部分元素。第3頁5.1失真測度5.1.1系統(tǒng)模型5.1.2失真度與平均失真度第4頁5.1.1系統(tǒng)模型經(jīng)過前面例子和討論，我們能夠建立研究限失真信源編碼（有損壓縮）系統(tǒng)模型：信源發(fā)出消息X經(jīng)過有失真信源編碼輸出為Y，因為是有失真編碼，所以X和Y元素不存在一一對應(yīng)關(guān)系，我們能夠假設(shè)X經(jīng)過一個信道輸出Y，這種假想信道我們稱為試驗信道。這么，我們就能夠經(jīng)過研究信道互信息來研究限失真編碼，而X和Y關(guān)系也能夠用轉(zhuǎn)移概率矩陣（信道矩陣）來表示。第5頁5.1.1系統(tǒng)模型圖5-1限失真編碼模型除了描述輸入輸出關(guān)系外，我們還關(guān)心怎樣才能限制失真問題，因為這一切都是建立在限失真要求之上，既然要限制失真，就需要相關(guān)于失真度量。第6頁5.1.2失真度與平均失真度怎樣來度量失真呢？我們先從最為簡單單個符號信源失真度量（distortionmeasure）開始，然后以此為基礎(chǔ)來建立更多符號失真度量。1.單個符號失真度設(shè)有離散無記憶信源信源符號經(jīng)過信道傳送到接收端Y，信道轉(zhuǎn)移概率矩陣第7頁對于每一對(xi，yj)，指定一個非負函數(shù)d(xi，yj)為單個符號失真度或失真函數(shù)（distortion-function）。用它來表示信源發(fā)出一個符號xi，而在接收端再現(xiàn)yj所引發(fā)誤差或失真。失真函數(shù)是依據(jù)人們實際需要和失真引發(fā)損失、風險、主觀感覺上差異大小等原因人為要求。有時候未必能夠證實為何采取這個函數(shù)是合理，其它函數(shù)沒有它好。我們假設(shè)發(fā)出一個符號，假如收到也是它，則失真為0，假如收到不是它，而是其它符號，則存在失真，失真函數(shù)大于0，即有：失真度還可表示成矩陣形式：[D]稱為失真矩陣。它是n×m階矩陣。（5-1）第8頁9均方失真：

相對失真：誤碼失真：絕對失真：前三種失真函數(shù)適合用于連續(xù)信源，后一個適合用于離散信源。最慣用失真函數(shù)

第9頁5.2信息率失真函數(shù)及其性質(zhì) 前面我們經(jīng)過簡單分析指出，要進行最大程度壓縮，依據(jù)香農(nóng)第一定理，壓縮極限為H(Y)=I(X;Y)。不過，我們必須考慮信息壓縮造成失真是在一定程度內(nèi)，所以，這個平均互信息量應(yīng)該在我們允許失真范圍內(nèi)盡可能小。從直觀感覺可知，若允許失真越大，信息傳輸率可越??；若允許失真越小，信息傳輸率需越大。所以信息傳輸率與信源編碼所引發(fā)失真(或誤差)是相關(guān)，對信息進行壓縮效果與失真也是相關(guān)。第10頁5.2信息率失真函數(shù)及其性質(zhì)5.2.1信息率失真函數(shù)定義5.2.2信息率失真函數(shù)性質(zhì)第11頁125.2.1

信息率失真函數(shù)定義

為了討論在允許一定失真D情況下，信源能夠壓縮極限應(yīng)該是一個與失真相關(guān)函數(shù)，我們能夠定義信息率失真函數(shù)（informationratedistortionfunction）為這一極限，簡稱率失真函數(shù)，記為R(D)。第12頁5.2.1

信息率失真函數(shù)定義在信源概率分布（P(X)給定）和失真度D給定以后，PD是滿足保真度準則試驗信道集合，即我們把X和Y當做信道輸入輸出話，這個信道集合中信道決定性參數(shù)就是信道傳遞（轉(zhuǎn)移）概率p(yj|xi)。第13頁5.2.1

信息率失真函數(shù)定義在信源和失真度給定以后，信道輸入和輸出平均互信息I(X;Y)是信道傳遞概率p(yj|xi)下凸函數(shù)，所以在這些滿足保真度準則PD集合中一定能夠找到某個試驗信道，使I(X;Y)到達最小，而這個最小值能夠從直觀上了解為，而且能夠被證實為在保真度準則下信源壓縮極限，即信息率失真函數(shù)R(D)，所以（5-12）第14頁5.2.1

信息率失真函數(shù)定義或者能夠直接地表述為：其中，R(D)單位是奈特/信源符號或比特/信源符號。關(guān)于上面定義式子為限失真編碼壓縮極限證實，能夠利用漸進等分性來證實，本章后面部分會給出證實。信息率失真函數(shù)這一命名也表達了信息壓縮極限是與允許失真D相對應(yīng)一個函數(shù)，所以下面我們將會討論這個函數(shù)性質(zhì)。假如說試驗信道說法可能會難于了解話，我們能夠?qū)⒃囼炐诺懒私鉃橄奘д嫘旁淳幋a器輸入X和輸出Y之間一個概率上映射關(guān)系，或者直接了解為概率p(yj|xi)。第15頁5.2.1

信息率失真函數(shù)定義 在離散無記憶平穩(wěn)信源情況下，可證得序列信源信息率失真函數(shù)：（5-13）從數(shù)學(xué)上來看，平均互信息是輸入信源概率分布∩型上凸函數(shù)，而平均互信息是信道傳遞概率p(yj|xi)U型下凸函數(shù)。所以，能夠認為信道容量C和信息率失真函數(shù)含有對偶性。第16頁5.2.1

信息率失真函數(shù)定義 研究信道容量C是為了處理在已知信道中傳送最大信息量。為了充分利用已給信道，使傳輸信息量最大而錯誤概率任意小，就是普通信道編碼問題。研究信息率失真函數(shù)是為了處理在已知信源和允許失真度D條件下，使信源必須傳送給用戶信息量最小。這個問題就是在能夠接收失真度D條件下，盡可能用最少碼符號來傳送信源消息，是信源信息盡快地傳送出去來提升通信有效性。這是信源編碼問題。第17頁它們之間對應(yīng)關(guān)系下表5-1所表示：表5-1信道容量C和R(D)比較

信道容量C率失真函數(shù)R(D)研究對象信道信源給定條件信道轉(zhuǎn)移概率p(yj|xi)信源分布p(x)選擇參數(shù)（變動參數(shù)）

信源分布p(x)試驗信道轉(zhuǎn)移概率或者信源編碼器映射關(guān)系p(yj|xi)結(jié)論求I(X;Y)最大值求I(X;Y)最小值概念上固定信道，改變信源，使信息率最大固定信源，改變信道，使信息率最小(反應(yīng))（信道傳輸能力）（信源可壓縮程度）通信上當使得錯誤概率Pe→0限制下，使傳輸信息量最大——信道編碼在給定D限制下，用盡可能少碼符號傳送——信源編碼對應(yīng)定理有噪信道編碼定理限失真信源編碼定理第18頁5.2.2

信息率失真函數(shù)性質(zhì)

下面我們來討論函數(shù)R(D)性質(zhì)，作為一個函數(shù)，其函數(shù)值處決于自變量，所以我們首先討論關(guān)于它自變量取值范圍，即定義域。1.信息率失真函數(shù)定義域R(D)自變量是允許平均失真度D，它是人們要求平均失真度上限值。這個值是否能夠任意選取呢？其實不然。因為平均失真度值是受制約，而且失真度與平均失真度均為非負值，顯然滿足下式：（5-14）（5-15）以上最小值計算方法都是直接求各個失真度最小值，然后按照概率加權(quán)平均，是否正確，為何？第19頁1）最小值對于離散信源，在普通情況下能夠采取我們前面定義，當X和Y一一對應(yīng)時候，此時平均失真度為0，而平均失真度顯然不可能小于0，所以Dmin為0，此時，R(Dmin)=R(0)=H(X)。對于連續(xù)信源，Dmin趨向于0時，R(Dmin)=R(0)=Hc(X)=∞。連續(xù)信源無失真時候，傳輸信息量是無窮大，實際信道容量總是有限，無失真?zhèn)魉瓦@種連續(xù)信息是不可能。只有當允許失真(R(D)為有限值)，傳送才是可能。第20頁2）最大值信源最大平均失真度Dmax：必須信息率越小，容忍失真就越大。當R(D)等于0時，對應(yīng)平均失真最大，也就是函數(shù)R(D)定義域上界值Dmax最大。因為信息率失真函數(shù)是平均互信息極小值，平均互信息量大于等于0，當R(D)=0時，即平均互信息極小值等于0。滿足信息率為0D值可能存在多個，不過鑒于我們總是希望失真度最小，存在各種選擇時候，總是選擇最小值，所以這里定義當R(D)=0時，D最小值為R(D)定義域上限，即Dmax是使R(D)=0最小平均失真度。第21頁R(D)=0時，X和Y相互獨立，所以，滿足X和Y相互獨立試驗信道有許多，對應(yīng)地可求出許多平均失真值，這類平均失真值下界就是Dmax。（5-16）令則（5-17）第22頁 上式是用不一樣概率分布{p(yj)}對Dj求數(shù)學(xué)期望，取數(shù)學(xué)期望當中最小一個，作為Dmax。實際上是用p(yj)對Dj進行線性分配，使線性分配結(jié)果最小。當p(xi)和失真矩陣已給定時，必可計算出Dj。Dj隨j改變而改變。p(yj)是任選，只需滿足非負性和歸一性。若Ds是全部Dj當中最小一個，我們可取p(ys)=1，其它p(yj)為零，此時Dj線性分配值（或數(shù)學(xué)期望）必定最小，即有（5-18）第23頁 通俗地說，當我們要進行最大程度壓縮時候，極端情況就是將輸出端符號壓縮為一個，我們能夠?qū)⑷我庑旁捶杧i都轉(zhuǎn)換為一個相同符號ys，因為對方接收到符號是確定，所以，能夠無需傳遞任何信息，或者說傳遞信息量為0。對于不一樣ys，會帶來不一樣失真度，我們當然會選擇失真度最小一個。實際上，不是有意去進行理性選擇，平均失真度值是能夠超出這一值。因為R(D)是非負函數(shù)，因為R(D)是用從中選出求得最小平均互信息，所以當D增大時，范圍增大，所求最小值小于范圍擴大前最小值，所以R(D)為D非增函數(shù)。當D增大時，R(D)可能減小，直到減小到R(D)=0，此時對應(yīng)著。假如當D>Dmax時，依然為零。第24頁我們有下面結(jié)論：當且僅當失真矩陣每一行最少有一個零元素時，，普通情況下失真矩陣均滿足此條件；可適當修改失真函數(shù)使得；和僅與和相關(guān)。第25頁例5-1設(shè)試驗信道輸入符號集，各符號對應(yīng)概率分別為1/3,1/3,1/3，失真矩陣以下所表示，求和以及對應(yīng)試驗信道轉(zhuǎn)移概率矩陣。解：第26頁令對應(yīng)最小失真度，其它為“0”，可得對應(yīng)試驗信道轉(zhuǎn)移概率矩陣為上式中第二項最小，所以令，，可得對應(yīng)試驗信道轉(zhuǎn)移概率矩陣為第27頁5.3離散無記憶信源信息率失真函數(shù)5.3.1*離散無記憶信源信息率失真函數(shù)5.3.2*連續(xù)無記憶信源信息率失真函數(shù)第28頁5.3.1*離散無記憶信源信息率失真函數(shù) 已知信源概率分布P(X)和失真函數(shù)d(x，y)，就可求得信源R(D)函數(shù)；標準上它與信道容量一樣，即在有約束條件下求極小值問題。也就是適當選取試驗信道P(y|x)使平均互信息最小化：（5-20）第29頁

其約束條件除了保真度準則外，還包含轉(zhuǎn)移概率必定滿足一些基本條件，比如非負性、歸一化條件：第30頁 求解這類極值有好幾個方法：如變分法、拉氏乘子（拉格朗日乘子，Lagrangemultiplier）法、凸規(guī)劃方法等等。應(yīng)用上述方法，嚴格地說能夠求出解來，不過，假如要求得到顯著解析表示式，則比較困難，通常只能用參量形式來表示。這種非顯式表示式依然不能直接求解信息率失真函數(shù)，必須采取收斂迭代算法求解信息率失真函數(shù)。 假如信源和失真矩陣存在某種對稱性，則能夠大大簡化信息率失真函數(shù)計算。這里我們先討論一些簡單情形下信息率失真函數(shù)計算。 以上求解思緒是否能夠處理全部問題？得到解就是進行限失真編碼時，某一失真度限制下最合理解嗎？第31頁 對于等概、對稱失真信源，存在一個與失真矩陣含有相同對稱性轉(zhuǎn)移概率矩陣分布到達信息率失真函數(shù)值。對于n元等概率信源，各個信源符號概率均為1/n，當失真函數(shù)對稱時，即第32頁

定理5-1設(shè)信源概率分布為P={p(a1),p(a2),…,p(ar)}，失真矩陣為{d(ai,bj)}r×s。π為{1,2,…,r}上一個置換，使得p(ai)=pπ(ai),i=1,2,…,r，ρ為{1,2,…,s}上一個置換，使得d(ai,bj)=d(π(ai),ρ(bj))，i=1,2,…,r,j=1,2,…,s，則存在一個到達信息率失真函數(shù)信道轉(zhuǎn)移概率分布Q={q(bj|ai)含有與{d(ai,bj)}r×s相同對稱性，即q(bj|ai)=q(ρ(bj)|π(ai))。該定理證實略。第33頁 利用這種性質(zhì)我們能夠降低信道轉(zhuǎn)移概率矩陣未知參數(shù)，便于求解。當然，以上定理依然顯得復(fù)雜，為了確保信源概率分布重排后一定能夠與原排列一一對應(yīng)相等，我們能夠直接要求信源等概率分布。此時假如失真矩陣對稱，則滿足上述定理條件。 我們還能夠發(fā)覺，漢明失真含有對稱性，當信源等概率分布，且失真矩陣為漢明失真矩陣時，即： 顯然滿足上述條件，能夠利用以上定理來簡化問題。第34頁例5-5有一個二元等概率平穩(wěn)無記憶信源U={0,1}，接收符號集V={0,1，3}，失真矩陣為

試求其信息率失真函數(shù)R(D)。解：求定義域因為信源等概率分布，失真矩陣含有對稱性，所以存在著與失真矩陣含有一樣對稱性轉(zhuǎn)移概率分布到達信息率失真函數(shù)。由為了運算方便，取上式中，因為信源等概率，所以（允許失真）給定。第35頁則一一對應(yīng)，要失真為有限值，兩個無窮∞對應(yīng)概率必定為0，轉(zhuǎn)移概率矩陣與失真矩陣對應(yīng)關(guān)系為0對應(yīng)A，1對應(yīng)B，考慮歸一性，B=1-A，∞對應(yīng)0，所以依據(jù)對應(yīng)關(guān)系，可得代入上述公式，有再將它代入轉(zhuǎn)移概率公式中：第36頁由：接收端概率分布，得：三個概率則:平均失真度D一定時候，第37頁

圖5-4信息率失真函數(shù)曲線第38頁5.3.2*連續(xù)無記憶信源信息率失真函數(shù)補充知識：設(shè)為實數(shù)有界集合。若:(1)每一個滿足不等式;(2)對于任何，存在有，使，則數(shù)稱為集合X下確界。通俗地了解：假如有最小值m，則其最小值就是其下確界，假如其集合中較小值大于m，且無限地趨向于m，則m也是其下確界。與這類似，有上確界概念。第39頁連續(xù)信源信息量為無限大（取值無限），假如要進行無失真信源編碼，編碼長度為無窮大，所以連續(xù)信源無法進行無失真編碼，而必定采取限失真編碼。連續(xù)信源信息率失真函數(shù)定義與離散信源信息率失真函數(shù)相類似，不過需要對應(yīng)地將只需將概率換為概率密度,因為連續(xù)性，需要將求和換為積分（本質(zhì)上是一個求和形式），而失真表示也表示為連續(xù)形式,離散信源下最小值替換為下確界。假設(shè)連續(xù)信源為X，試驗信道輸出為連續(xù)隨機變量Y，連續(xù)信源平均失真度定義為：(5-21)經(jīng)過試驗信道取得平均互信息為：一樣，確定一允許失真度D，凡滿足平均失真小于D全部試驗信道集合記為PD，則連續(xù)信源信息率失真函數(shù)定義為：(5-22)第40頁嚴格地說，連續(xù)信源情況下，可能不存在極小值，不過下確界是存在，如我們上面討論無限趨向于下確界。連續(xù)信源信息率失真函數(shù)依然滿足前面信息率失真函數(shù)性質(zhì)（針對于離散信源討論）。對于N維連續(xù)隨機序列平均失真度和信息率失真函數(shù)也能夠類似進行定義。連續(xù)信源信息率失真函數(shù)計算依然是求極值問題，一樣能夠采取拉格朗日乘子法進行，較為復(fù)雜。這里討論較為簡單高斯信源情形，對高斯信源，在普通失真函數(shù)下，其率失真函數(shù)是極難求得，但在平方誤差失真度量下，其率失真函數(shù)有簡單封閉表示式。對平方誤差失真，試驗信道輸入符號和輸出符號之間失真為：對應(yīng)平均失真度為：第41頁在平方誤差失真下，設(shè)允許失真為D，則高斯信源率失真函數(shù)為：(5-23)其曲線以下列圖5-6所表示。圖5-6高斯信源在均方誤差準則下R(D)函數(shù)第42頁實際上，我們還能夠證實在平均功率受限條件下，正態(tài)分布R(D)函數(shù)值最大，它是其它一切分布上限值，也是信源壓縮比中最小，所以人們往往將它作為連續(xù)信源壓縮比中最保守預(yù)計值。詳細見下面定理。第43頁定理5-2:對任一連續(xù)非正態(tài)信源，若已知其方差為,熵為,并要求失真函數(shù)為,則其R(D)滿足以下不等式：（正態(tài)是上限）（5-24）第44頁5.4保真度準則下信源編碼定理5.4.1*失真ε經(jīng)典序列5.4.2*保真度準則下信源編碼定理證實5.4.3*保真度準則下信源編碼逆定理證實第45頁5.4保真度準則下信源編碼定理 信息率失真函數(shù)R(D)是滿足保真度準則（D）時所必須含有最小信息率，在進行信源壓縮之類處理時，R(D)就成為一個界限，不能讓實際信息率低于R(D)。把相關(guān)結(jié)論用定理形式給出，即限失真信源編碼定理，又稱為保真度準則下信源編碼定理，也就是通常所說香農(nóng)第三編碼定理。 本節(jié)中，我們將闡述相關(guān)定理，而且從數(shù)學(xué)上嚴格證實。為了簡化問題，這里我們討論限于離散無記憶平穩(wěn)信源，不過所述定理能夠推廣到連續(xù)信源，有記憶信源等普通情況。定理通俗形式以下：第46頁

定理5-3：設(shè)離散無記憶平穩(wěn)信源信息率失真函數(shù)為R(D)，只要滿足R<R(D)，而且失真度是有限，當信源系列長度L足夠長時，一定存在一個編碼方法，其譯碼失真小于或等于D+ε，其中ε是任意小正數(shù)；反過來，若R<R(D)，則不論采取什么樣編碼方法，其譯碼失真必大于D。第47頁 該定理包含兩部分：R>R(D)情形稱為正定理，R<R(D)情形稱為逆定理。經(jīng)過正逆定理說明這個R(D)不大不小，恰好是限失真信源編碼界。 另外，該定理與香農(nóng)第二編碼定理（即信道編碼定理）一樣，只是碼存在性定理。正定理告訴我們，R>R(D)時，譯碼失真小于或等于D+ε碼必定存在，但定理本身并未通知碼詳細結(jié)構(gòu)方法。普通來說，要找到滿足條件碼，只能用優(yōu)化思緒去尋求，迄今為止，尚無適當系統(tǒng)編碼方法來靠近香農(nóng)給出界R(D)。反定理告訴我們，R<R(D)時，譯碼失真必大于D，必定找不到滿足條件碼，所以用不著浪費時間和精力。第48頁 總結(jié)起來，香農(nóng)信息論三個基本概念——信源熵、信道容量和信息率失真函數(shù)，都是臨界值，是從理論上衡量通信能否滿足要求主要極限。對應(yīng)這三個基本概念是香農(nóng)三個基本編碼定理——無失真信源編碼定理、信道編碼定理和限失真信源編碼定理，分別又稱為香農(nóng)第一、第二和第三編碼定理，或第一、第二、第三極限定理。這是三個理想編碼存在性定理，它們并不能直接得出對應(yīng)編碼方法，不過對編碼含有指導(dǎo)意義。第49頁為便于后續(xù)證實，將正定理和逆定理分別轉(zhuǎn)換為嚴格數(shù)學(xué)形式：定理5-4保真度準則下（限失真）信源編碼正定理：設(shè)R(D)為一離散無記憶信源信息率失真函數(shù)，而且有有限失真測度。對于任意以及任意足夠長碼長n，則一定存在一個信源編碼C，其碼字個數(shù)為：（5-25）而編碼后平均失真度，其中R(D)以h為底，h為編碼進制數(shù)。假如用二元編碼，且R(D)計算以二為底，即以bit為單位，則：。它告訴我們，對于任何失真度，只要碼長n足夠長，總能夠找到一個編碼C，使編碼后每個信源符號信息傳輸率，即。而碼平均失真度。定理說明在允許失真D條件下，信源最小、可到達信息傳輸率是信源。第50頁定理5-5保真度準則下（限失真）信源編碼逆定理：不存在平均失真度為D，而平均信息傳輸率，任何信源碼。即對任意碼長為n信源碼C，若碼字個數(shù)，一定有:逆定理告訴我們：假如編碼后平均每個信源符號信息傳輸率小于信息率失真函數(shù),就不能在保真度準則下再現(xiàn)信源消息，即失真必定超出D。第51頁5.4.1*失真ε經(jīng)典序列 正定理證實也可采取聯(lián)合經(jīng)典序列及聯(lián)合漸近等分割性。利用當序列長度趨向于無窮大時候表達出來大數(shù)定律性質(zhì)。當序列長度趨向于無窮長時候，有些序列表達出均等化性質(zhì)，而且這些序列概率和趨向于1，我們稱為經(jīng)典序列，而其它序列概率則趨向于0，能夠忽略，限失真編碼壓縮就表達在對這些非經(jīng)典序列忽略上。在對于限失真編碼討論中新增了失真測度條件。所以，在證實定理前，我們先給出失真經(jīng)典序列和證實定理所需用到定義、結(jié)論。第52頁定義:設(shè)單符號空間聯(lián)合概率分布為P(x,y)。其失真度為d（x，y）。若任意>0，有n長序列對滿足：（5-26）（5-27）（5-28）（5-29）則稱為失真ε經(jīng)典序列或簡稱失真經(jīng)典序列。第53頁序列信源單個符號失真度：（5-30）序列聯(lián)合概率等于單個符號聯(lián)合概率累積結(jié)果=（5-31）所以，依據(jù)大數(shù)定律，以概率（也稱為依概率）收斂于單個隨機變量均值第54頁引理5-1:設(shè)隨機序列和，它們各分量之間都是相互統(tǒng)計獨立且同分布，而且滿足=當，則（5-32）引理5-2：對全部，有（5-33）香農(nóng)第三定理證實中要用到下面一個有趣不等式。引理5-3：對于，有（5-34）說明：其中e為自然常數(shù)e=2.71828……。第55頁5.4.2*保真度準則下信源編碼定理證實 定義了失真經(jīng)典序列后，我們能夠來證實信源編碼定理，證實R(D)是在允許失真D條件下信源最大信息傳輸率。第56頁證實：設(shè)信源序列是統(tǒng)計獨立等同分布隨機序列，其概率分布為。又設(shè)此單個符號信源失真測度為，信源率失真函數(shù)為。設(shè)到達試驗信道為，在這試驗信道中。現(xiàn)需證實，對于任意時，存在一個信源符號信息傳輸率為信源編碼。其平均失真度小于或等于。第57頁對于某固定碼書C和>0，我們將信源序列空間中信源序列分成兩大類型：（1）信源序列：在碼書中存在一個碼字，使其。這是因為，與是組成失真經(jīng)典序列對，所以它們是親密相關(guān)，而且滿足<則得又因這些失真經(jīng)典序列總體出現(xiàn)概率靠近等于1，所以這些失真經(jīng)典序列對平均失真度貢獻最多等于（2）另一類信源序列：在碼書中不存在一個碼字，使與組成失真經(jīng)典序列對。即，。設(shè)這些序列總體出現(xiàn)概率為。因為每個信源序列最大失真為，所以這類信源序列對平均失真貢獻最多是。所以，由得（5-37）以上提到，為了讓失真滿足保真度準則，就需要趨向于0。第58頁計算：為了計算，我們設(shè)為碼中最少有一個碼字與信源序列組成失真經(jīng)典序列正確全部信源序列集合，即（5-38）所以，是因為引發(fā)，則（5-39）上式表示，全部不能用碼字來描述那些信源序列概率對全部可能產(chǎn)生隨機碼書進行統(tǒng)計平均，對上式（5-39）交換求和號。這么能夠解釋為，選擇沒有碼字能描述信源序列隨機碼書出現(xiàn)概率對全部信源序列進行統(tǒng)計平均。則（5-40）定義函數(shù)（5-41）第59頁碼書C中碼字是在空間中依據(jù)概率來隨即地選取。對于在中隨機選取某個碼字不與信源序列組成失真經(jīng)典序列正確概率應(yīng)等于=（5-42）碼書C中共有個碼字，而且是獨立地、隨機地選擇。所以，碼書中沒有碼字能描述信源序列隨機碼書出現(xiàn)概率為（5-43）將上式代入式（5-40）得（5-44）利用引理5-2得（5-45）代入式（5-44）得（5-46）第60頁又依據(jù)引理5-3，將中n用代替，x用代替，y用代替，得（5-47）代入式（5-46）得（5-48）觀察上式（5-48）中最終一項，當選擇另若我們選取試驗信道恰好是使平均互信息到達試驗信道，所以，。所以，當，足夠小時，時，最終一項趨于零。第61頁式（5-48）中前兩項是聯(lián)合概率分布為序列對不是失真經(jīng)典序列正確概率。由引理5-1得，當n足夠大時（5-49）所以，適當?shù)剡x擇和可使盡可能地小?？偠灾?，對全部隨機編碼碼書C當，任意選取，只要選擇足夠大，及適當小，可使（5-50）所以，最少存在一個碼書C，其碼字個數(shù)，即信源符號信息傳輸率，而碼平均失真度。第62頁5.4.3*保真度準則下信源編碼逆定理證實逆定理是一個不可能形式，顯然我們直接去證實極難著手，對于這種結(jié)論，普通用反證法先假設(shè)其成立，然后得出矛盾來證實。第63頁證實：假設(shè)存在一個信源編碼C，有M個碼字，，而且M個碼字是從空間中選取序列，它能使得。編碼方法仍采取前面所述方法，將全部信源序列映射成碼字，而使。依據(jù)失真經(jīng)典序列定義，與是組成失真經(jīng)典序列，所以她們是彼此經(jīng)常聯(lián)合出現(xiàn)序列對。而且又滿足<，所以它們之間失真。這種編碼方法可看成一個特殊試驗信道：（5-51）依據(jù)假設(shè)則在這個試驗信道中，可得又因在這信道中=0，所以平均互信息（5-52）上式（5-52）中不等式是因為在編碼范圍內(nèi)，最多只有M個，所以空間最大熵值為。又因為信源是離散無記憶信源，所以有（5-53）第64頁設(shè)以平均失真再現(xiàn)，則必有又依據(jù)信息率失真函數(shù)U型凸狀性和單調(diào)遞減性得（5-54）上式最終一項是依據(jù)離散無記憶平穩(wěn)信源求得。所以得或者這個結(jié)果與定理假設(shè)相矛盾，所以逆定理成立。（5-55）第65頁正如前面所述，保真度準則下信源編碼定理及其逆定理是有失真信源壓縮理論基礎(chǔ)。這兩個定理證實了允許失真D確定后，總存在一個編碼方法，使編碼信息傳輸率，那么編碼平均失真度將大于D。假如用二元碼符號來進行編碼話，在允許一定量失真D情況下，平均每個信源符號所需二元碼符號下限值就是R(D)。可見，從香農(nóng)第三定理可知，R(D)確實是允許失真度為D情況下信源信息壓縮下限值。比較香農(nóng)第一定理和第三定理可知，當信源給定后，無失真信源壓縮極限值是信源熵H(S)；而有失真信源壓縮極限值是信息率失真函數(shù)R(D)。在給定某D后，普通R(D)<H(S)。無失真信源編碼能夠看成是限失真編碼一個特例，依據(jù)我們對失真正常定義，普通當輸入和輸出符號一一對應(yīng)時，失真才為0，此時，R(0)=H(S)，能夠經(jīng)過限失真信源編碼定理來證實無失真信源編碼定理。5.5限失真信源編碼定理實用意義第66頁5.5限失真信源編碼定理實用意義類似于無失真信源編碼利用信源熵來衡量編碼效率一樣，信息率失真函數(shù)能夠用來度量限失真編碼在某一失真下編碼效率。信源R(D)函數(shù)能夠作為衡量各種壓縮編碼方法性能優(yōu)劣一個尺度。但香農(nóng)第三定理一樣只給出了一個存在定理。至于怎樣尋找這種最正確壓縮編碼方法，定理中并沒有給出。在實際應(yīng)用中，該理論主要存在著幾類問題。在實際應(yīng)用中，該定理主要存在以下兩大類問題：第一類問題是符合實際信源R(D)函數(shù)計算相當困難。（1）需要對實際信源統(tǒng)計特征有確切數(shù)學(xué)描述，即概率分布明確；（2）需要對符合主客觀實際失真給與正確度量，不然不能求得符號主客觀實際R(D)函數(shù)。比如，通常采取均方誤差來表示信源平均失真度。但對于圖像信源來說，均方誤差較小編碼方法，而人們視覺感到失真較大。所以，人們?nèi)圆扇≈饔^觀察來評價編碼方法好壞。所以，怎樣定義符合主觀和客觀實際情況失真測度就是件較困難事。（3）即便對實際信源有了確切數(shù)學(xué)描述，又有符合主客觀實際情況失真測度，而失真率函數(shù)R(D)計算也還較困難。第67頁 第二類問題是即便求得了符合實際信息率失真函數(shù)，還需研究采取何種實用最正確編碼方法才能到達極限值R(D)。當前，這兩方面工作都有進展。尤其是對實際信源各種壓縮方法，如對語音信號、電視信號和遙感圖像等信源各種壓縮方法有了較大進展。 第三類問題是信息率失真函數(shù)求解是在給定試用信道輸入輸出及其失真矩陣情況下計算，當輸出符號集未定時候，我們不能確定到底怎么樣符號集才是最優(yōu)，即使得信息率失真函數(shù)值最低。5.5限失真信源編碼定理實用意義第68頁在信息論中，尤其是信息熵中，許多時候?qū)⒏鱾€信源符號一視同仁地對待，不過實際上，各個符號有它們語義和語用，在數(shù)值上是不一樣。這當然帶來對應(yīng)不足，信息率失真函數(shù)中失真度量，實際上能夠認為是一個很好補充，用于填補對于語義和語用度量缺失，比如，陰天、晴天、大雨、中雨、小雨所代表降雨量、陽光強弱是不一樣，且是有不一樣幅度差異。現(xiàn)在信息率失真函數(shù)也用于度量損失和信息價值，實際上還能夠做深入推廣。5.5限失真信源編碼定理實用意義第69頁5.6限失真信源編碼限失真信源編碼定理指出：在允許一定失真度D情況下，信源輸出信息傳輸率可壓縮到R(D)值，這就從理論上給出了信息傳輸率與允許失真之間關(guān)系，奠定了信息率失真理論基礎(chǔ)。不過它并沒有告訴我們怎樣進行編碼能夠到達這一極限值。普通情況下信源編碼可分為離散信源編碼，連續(xù)信源編碼和相關(guān)信源編碼三類。前兩類編碼方法主要討論獨立信源編碼問題，后一類編碼方法討論非獨立信源編碼問題。離散信源可做到無失真編碼，而連續(xù)信源則只能做到限失真信源編碼，通常我們將限失真信源編碼簡稱限失真編碼。無失真編碼和限失真編碼本身也含有相通之處，有些方法和思想本質(zhì)上能夠同時用于限失真編碼和無失真編碼。采取限失真編碼采取方法主要有矢量量化、預(yù)測編碼和變換編碼。第70頁5.6限失真信源編碼5.6.1矢量量化編碼5.6.2預(yù)測編碼5.6.3變換編碼第71頁5.6.1矢量量化編碼 量化(Quantization)就是把經(jīng)過抽樣得到瞬時值將其幅度離散，即用一組要求電平，把瞬時抽樣值用最靠近電平值來表示。量化普通用于連續(xù)信源編碼，不過它也能夠用于離散信源編碼。對小數(shù)、實數(shù)進行四舍五入，就是一個最為簡單通俗例子，比如經(jīng)過四舍五入取整，會將區(qū)間[1.5,2.5)數(shù)值都量化為2。 按照量化級劃分方式分，有均勻量化（uniformquantization）和非均勻量化。其中最為簡單是均勻量化，也稱為線性量化，它將輸入信號取值域等間隔分割量化。反之，則稱為非均勻量化，其范圍劃分不均勻，普通用類似指數(shù)曲線進行量化。非均勻量化是針對均勻量化提出，為了適應(yīng)幅度大輸人信號，同時又要滿足精度要求，就需要增加樣本位數(shù)。不過，對話音信號來說，大信號出現(xiàn)機會并不多，增加樣本位數(shù)沒有充分利用。為了克服這個不足，出現(xiàn)了非均勻量化方法，這種方法也叫做非線性量化。非均勻量化基本想法是，對輸人信號進行量化時，大輸入信號（概率?。┎扇〈罅炕g隔，小輸入信號采取小量化間隔。這么就能夠在滿足精度要求情況下，用較少位數(shù)來表示。聲音數(shù)據(jù)還原時，采取相同規(guī)則。常見非均勻量化有A律和μ率等，它們區(qū)分在于量化曲線不一樣。均勻量化好處就是編解碼很輕易，但要到達相同信噪比占用帶寬要大。當代通訊系統(tǒng)中都用非均勻量化。第72頁5.6.1矢量量化編碼 按照量化維數(shù)分，量化分為標量量化(scalarquantization,SQ)和矢量量化(vectorquantization,VQ)...。標量量化是一維量化，一個幅度值對應(yīng)一個量化結(jié)果。而矢量量化是二維甚至多維量化，兩個或兩個以上幅度值作為一個整體決定一個量化結(jié)果。以二維情況為例，兩個幅度決定了平面上一點。而這個平面事先按照概率已經(jīng)劃分為N個小區(qū)域，每個區(qū)域?qū)?yīng)著一個輸出結(jié)果。由輸入確定那一點落在了哪個區(qū)域內(nèi)，矢量量化器就會輸出那個區(qū)域?qū)?yīng)碼字。無失真信源編碼中我們能夠看到，對單個符號進行對應(yīng)信源編碼壓縮效果比對序列進行信源編碼效果要差，類似地，矢量量化因為考慮將一個序列當做整體來對待，能夠消除序列內(nèi)部相關(guān)性影響，普通會比標量量化效率更高。 矢量量化中碼書碼字越多，維數(shù)越大，失真就越小。只要適當?shù)剡x擇碼字數(shù)量，就能控制失真量不超出某一給定值，所以碼書控制著矢量大小。第73頁5.6.1矢量量化編碼 試驗證實，即使各信源符號相互獨立，多維量化通常也可壓縮信息率。因而矢量量化引發(fā)人們興趣而成為當前連續(xù)信源編碼一個熱點?？墒钱斁S數(shù)較大時，矢量量化尚無解析方法，只能求援于數(shù)值計算；而且聯(lián)合概率密度也不易測定，還需采取諸如訓(xùn)練序列方法。普通來說，高維矢量聯(lián)合是很復(fù)雜，雖已經(jīng)有不少方法，但其實現(xiàn)還有不少困難，有待深入研究。第74頁5.6.2預(yù)測編碼慣用解除相關(guān)性辦法是預(yù)測和變換，其實質(zhì)都是進行序列一個映射。普通來說，預(yù)測編碼有可能完全解除序列相關(guān)性，但必需確知序列概率特征；變換編碼普通只解除矢量內(nèi)部相關(guān)性，但它可有許多可供選擇變換方法，以適應(yīng)不一樣信源特征。下面介紹預(yù)測編碼普通理論與方法。第75頁5.6.2預(yù)測編碼預(yù)測編碼（predictioncoding）是數(shù)據(jù)壓縮三大經(jīng)典技術(shù)(統(tǒng)計編碼，預(yù)測編碼，變換編碼)之一，它是建立在信源數(shù)據(jù)相關(guān)性之上，由信息理論可知，對于相關(guān)性很強信源，條件熵可遠小于無條件熵，所以人們常采取盡可能解除相關(guān)性方法，使信源輸出轉(zhuǎn)化為獨立序列，以利于深入壓縮碼率。我們能夠從預(yù)測這個名字上來了解預(yù)測編碼，假如一個序列后面符號由前面若干個符號決定，我們能夠認為前面符號能夠預(yù)測后面符號，這么，我們只需要發(fā)送前面符號，后面符號完全能夠預(yù)測出來。顯而易見，這種可預(yù)測性是因為符號之間含有相關(guān)性。這是一個極端情況，實際上，序列之間相關(guān)性可能存在，不過它不足以完全決定后面符號，可能只是能夠降低后面符號不確定性，此時從信息論角度來說，前面符號提供了后面符號信息，利用這種相關(guān)性也能夠進行預(yù)測。再舉一個例子，一個單一正弦波形，一旦知道了一個周期之內(nèi)波形，就能夠依據(jù)周期性重復(fù)這個波形來預(yù)測后面波形。一樣是這個例子，經(jīng)過波形中若干點能夠確定整個波形，所以，我們能夠利用這些點完全地預(yù)測后面各個位置波形。第76頁5.6.2預(yù)測編碼預(yù)測編碼基本思想是經(jīng)過提取與每個信源符號相關(guān)新信息，并對這些新信息進行編碼來消除信源符號之間相關(guān)性。實際中慣用新信息為信源符號當前值與預(yù)測值差值，這里正是因為信源符號間存在相關(guān)性，所以才使預(yù)測成為可能，對于獨立信源，預(yù)測就沒有可能。預(yù)測理論基礎(chǔ)主要是預(yù)計理論。所謂預(yù)計就是用試驗數(shù)據(jù)組成一個統(tǒng)計量作為某一物理量估值或預(yù)測值，若估值數(shù)學(xué)期望等于原來物理量，就稱這種預(yù)計為無偏預(yù)計；若估值與原物理量之間均方誤差最小，就稱之為最正確預(yù)計，基于這種方法進行預(yù)測，就稱為最小均方誤差預(yù)測，所以也就認為這種預(yù)測是最正確。第77頁5.6.2預(yù)測編碼在詳細預(yù)測編碼實現(xiàn)過程中，編碼器和譯碼器都存貯有過去信號值，并以此來預(yù)測或預(yù)計未來信號值。在編碼器發(fā)出不是信源信號本身，而是信源信號與預(yù)測值之差；在譯碼端，譯碼器將接收到這一差值與譯碼器預(yù)測值相加，從而恢復(fù)信號。要實現(xiàn)最正確預(yù)測就是要找到計算預(yù)測值預(yù)測函數(shù)。這個函數(shù)依據(jù)數(shù)據(jù)相關(guān)性來決定。第78頁5.6.2預(yù)測編碼設(shè)有信源序列，k階預(yù)測就是由前k個數(shù)據(jù)來預(yù)測。可令預(yù)測值為：式中函數(shù)是待定預(yù)測函數(shù)。要使預(yù)測值含有最小均方誤差，必須確知k個變量聯(lián)合概率密度函數(shù)，這在普通情況下較難得到，因而慣用比較簡單線性預(yù)測方法。線性預(yù)測（linearprediction）是取預(yù)測函數(shù)為各已知信源符號線性函數(shù)，即取預(yù)測值為：（5-56）其中為預(yù)測系數(shù)。最簡單預(yù)測是令 ，稱為前值預(yù)測，慣用差值預(yù)測就屬于這類。第79頁5.6.2預(yù)測編碼 利用預(yù)測值來編碼方法可分為兩類：一類是對實際值與預(yù)測值之差進行編碼，也叫差值預(yù)測編碼；另一類方法是依據(jù)差值大小，決定是否需傳送該信源符號。比如，可要求某一閾值T，當差值小于T時可不傳送，對于相關(guān)性很強信源序列，常有很長一串符號差值能夠不傳送，此時只需傳送這串符號個數(shù)，這么能大量壓縮碼率。這類方法普通是按信宿要求來設(shè)計，也就是壓縮碼率引發(fā)失真應(yīng)能滿足信宿需求。 實現(xiàn)預(yù)測編碼要深入考慮3個方面問題： ⑴預(yù)測誤差準則選取，比如采取使預(yù)測誤差均方值到達最小作為準則，或者絕對誤差均值最小等。 ⑵預(yù)測函數(shù)選??； ⑶預(yù)測器輸入數(shù)據(jù)選取。第80頁5.6.3變換編碼預(yù)測編碼認為冗余度是數(shù)據(jù)固有，經(jīng)過對信源建模來盡可能準確地預(yù)測源數(shù)據(jù)，去除數(shù)據(jù)時間冗余度。不過冗余度有時與不一樣表示方法也有很大關(guān)系，變換編碼是將原始數(shù)據(jù)“變換”到另一個更為緊湊表示空間，去除數(shù)據(jù)空間冗余度，可得到比預(yù)測編碼更高數(shù)據(jù)壓縮。能量集中是指對N維矢量信號進行變換后，最大方差見集中在前M個低次分量之中（M<N）。第81頁5.6.3變換編碼變換編碼（transformcoding）基本原理是將原來在空間(時間)域上描述信號，經(jīng)過一個數(shù)學(xué)變換(比如傅里葉變換等)，將信號變到變換域(比如頻域等)中進行描述，在變換域中，變換系數(shù)之間相關(guān)性經(jīng)常顯著下降，并常有能量集中于低頻或低序系數(shù)區(qū)域特點，這么就輕易實現(xiàn)碼率壓縮，并還可大大降低數(shù)據(jù)壓縮難度。第82頁5.6.3變換編碼高性能變換編碼方法不但能使輸出壓縮信源矢量中各分量之間相關(guān)性大大減弱，而且使能量集中到少數(shù)幾個分量上，在其它分量上數(shù)值很小，甚至為"0"。所以在對變換后分量(系數(shù))進行量化再編碼時，因為在量化后等于"0"系數(shù)能夠不傳送，所以在一定保真度準則下可到達壓縮數(shù)據(jù)率目標，量化參數(shù)選取主要依據(jù)保真度要求或恢復(fù)信號主觀評價效果來確定。第83頁5.6.3變換編碼 下面我們首先介紹變換編碼基本原理，然后介紹變換編碼中慣用幾個變換。 1.正交變換編碼基本原理 設(shè)信源連續(xù)發(fā)出兩個信源符號s1與s2之間存在相關(guān)性，假如均為3比特量化，即它們各有八種可能取值，那么s1與s2之間相關(guān)特征可用圖5-7表示。第84頁圖5-7s1與s2之間相關(guān)特征圖圖5-7中橢圓區(qū)域表示s1與s2相關(guān)程度較高區(qū)域，此相關(guān)區(qū)關(guān)于s1軸和s2軸對稱。顯然假如s1與s2相關(guān)性越強，則橢圓形狀越扁長，而且變量s1與s2幅度取值相等可能性也越大，二者方差近似相等，即 。第85頁假如我們將s1與s2坐標軸逆時針旋轉(zhuǎn)45°，變成平面，則橢圓區(qū)域長軸落在 軸上，此時當 取值變動較大時，所受影響很小，說明 與之間相關(guān)性大大減弱。同時由圖5-7能夠看出：隨機變量與能量分布也發(fā)生了很大改變，在相關(guān)區(qū)域內(nèi)大部分點上方差均大于方差，即 。另外，因為點與坐標原點o距離不變，所以坐標變換不會使總能量發(fā)生改變，所以有：=（5-57）由此可見，經(jīng)過上述坐標變換，使變換后得到新變量，展現(xiàn)兩個主要特點：（1）變量間相關(guān)性大大減弱，如其中一個改變時，另外一個幾乎不變;（2）能量更集中，即 ，且小到幾乎可忽略。這兩個特點正是變換編碼能夠?qū)崿F(xiàn)數(shù)據(jù)壓縮主要依據(jù)，即數(shù)據(jù)能夠忽略。第86頁上述坐標旋轉(zhuǎn)對應(yīng)變換方程為：因為所以，坐標旋轉(zhuǎn)變換矩陣是一個正交矩陣，由正交矩陣決定變換稱為正交變換。進行正交變換目標是使得變換后各個分量相互獨立。按照均方誤差最小準則來計算相關(guān)參數(shù)，如θ，得到一個正交變換叫做K-L變換，不過使用KL變換需要知道信源協(xié)方差矩陣，再求出協(xié)方差矩陣特征值和特征矢量，然后據(jù)此結(jié)構(gòu)正交變換矩陣；但求特征值和特征矢量是相當困難，尤其是在高維信源情況下，甚至求不出來。即使借助于計算機求解，也難于滿足實時處理要求。第87頁

K-L變換含有以下特征：（1）去相關(guān)特征。K-L變換是變換后矢量信號Y分量互不相關(guān)。（2）使得能量集中于個別分量中。（3）最正確特征。K-L變換是在均方誤差測度下，失真最小一個變換，其失真為被略去各分量之和。因為這一特征，K-L變換被稱為最正確變換。許多其它變換都將K-L變換作為性能上比較參考標準。除了用于數(shù)據(jù)壓縮，利用K-L變換還能夠進行人臉圖象識別和人臉圖象合成。這些功效與K-L變換冗余控制能力和提取關(guān)鍵信息能力顯然是相關(guān)。人臉圖象識別步驟簡述為：首先搜集要識別人人臉圖像，建立人臉圖像庫，然后利用K-L變換確定對應(yīng)人臉基圖像，再反過來用這些基圖像對人臉圖像庫中有些人臉圖像進行K-L變換，從而得到每幅圖像參數(shù)向量并將每幅圖參數(shù)向量存起來。在識別時，先對一張所輸入臉圖像進行必要規(guī)范化，再進行K-L變換分析，得到其參數(shù)向量。將這個參數(shù)向量與庫中