葉中行信息論課件第五章

第5章

限失真信源編碼和率失真函數(shù)1葉中行信息論課件第五章共67頁，您現(xiàn)在瀏覽的是第1頁!無失真信源編碼和有噪信道編碼表明：只要信道的信息傳輸速率小于信道容量，總能找到一種編碼方法，使得在該信道上的信息傳輸?shù)牟铄e概率任意?。环粗?，若信道的信息傳輸速率大于信道容量，則不可能使信息傳輸差錯概率任意?。牵瑹o失真的編碼并非總是必要的：例如在傳送語音信號時，由于人耳接受的帶寬和分辨率是有限的，從而可以把頻譜范圍從20Hz~8kHz的語音信號去掉低端和高端的頻率，視為帶寬只有從300Hz~3400Hz的信號；這樣，即使傳輸?shù)恼Z音信號有一些失真，人耳還是可以分辨或感覺出來，已滿足語音信號傳輸?shù)囊螅?葉中行信息論課件第五章共67頁，您現(xiàn)在瀏覽的是第2頁!在允許一定程度失真的條件下，能夠把信源信息壓縮到什么程度，即最少需要多少比特數(shù)才能描述信源，是本章將要討論的問題．3葉中行信息論課件第五章共67頁，您現(xiàn)在瀏覽的是第3頁!

5.1限失真信源編碼模型和率失真函數(shù)一、失真測度從直觀感覺可知，若允許失真越大，信息傳輸率可越??；若允許失真越小，信息傳輸率需越大．所以信息傳輸率與信源編碼所引起的失真(或誤差)是有關(guān)的．4葉中行信息論課件第五章共67頁，您現(xiàn)在瀏覽的是第4頁!若信源變量X有n個符號，接收變量X^有n個符號，則d(x,x^)就有n×n個,它可以排列成矩陣形式，即：它為失真矩陣D．5葉中行信息論課件第五章共67頁，您現(xiàn)在瀏覽的是第5頁![例２]對稱信源．信源變量Ｘ＝{ｘ1,ｘ2,…ｘｎ}，接收變量Ｘ^＝{ｘ^1,ｘ^2,…ｘ^ｎ}。失真度定義為：若信源符號代表信源輸出信號的幅度值，這就是一種以方差表示的失真度。它意味著幅度差值大的要比幅度差值小的所引起的失真更為嚴(yán)重，嚴(yán)重程度用平方來表示。當(dāng)ｎ＝3時，Ｘ＝{0,1,2}，Ｘ^＝{0,1,2}，則失真矩陣為：上述例子說明了具體失真度的定義．一般情況下根據(jù)實際信源的失真，可以定義不同的失真和誤差的度量．另外還可以按其他標(biāo)準(zhǔn)，如引起的損失、風(fēng)險、主觀感覺上的差別大小等來定義失真度d(ｘ,ｘ^)．6葉中行信息論課件第五章共67頁，您現(xiàn)在瀏覽的是第6頁!二、平均失真測度信源Ｘ和信宿Ｘ^都是隨機變量，故單個符號失真度d(ｘ,ｘ^)也是隨機變量．顯然，規(guī)定了單個符號失真度后，傳輸一個符號引起的平均失真，即信源平均失真度：在離散情況下，信源Ｘ＝{x1,x2,…xn}，其概率分布P(x)＝[P(x1),P(x2),…P(xn)]，信宿X^＝{X^1,X^2,…X^n}．若已知試驗信道的傳遞概率為P(x|x^)時，則平均失真度為：7葉中行信息論課件第五章共67頁，您現(xiàn)在瀏覽的是第7頁![說明]①是在平均意義上，對系統(tǒng)失真的總體描述②是信源統(tǒng)計特性p(x)的函數(shù)是信道統(tǒng)計特性p(x/x^)的函數(shù)是規(guī)定失真度d(x,x^)的函數(shù)若保持p(x)、d(x,x^)不變，則平均失真度就是信道特性p(x/x^)的函數(shù)研究：在滿足保真度準(zhǔn)則前提下，求信息率最小值8葉中行信息論課件第五章共67頁，您現(xiàn)在瀏覽的是第8頁!三、信息率失真函數(shù)的定義

信源給定，且又具體定義了失真函數(shù)以后，總希望在滿足一定失真的情況下，使信源傳輸給收信者的信息傳輸率R盡可能地?。丛跐M足保真度準(zhǔn)則下，尋找信源必須傳輸給收信者的信息率R的下限值-------------這個下限值與D有關(guān)．從接收端來看，就是在滿足保真度準(zhǔn)則下，尋找再現(xiàn)信源消息所必須獲得的最低平均信息量．而接收端獲得的平均信息量可用平均互信息I(X;X^)來表示，這就變成了在滿足保真度準(zhǔn)則的條件下，尋找平均互信息I(X;X^)的最小值．9葉中行信息論課件第五章共67頁，您現(xiàn)在瀏覽的是第9頁!率失真函數(shù)與信道容量的比較信道容量C率失真函數(shù)R(D)數(shù)學(xué)上固定p(x^/x),改變p(x),求得I(X;X^)最大值固定p(x),改變p(x^/xi),求得I(X;X^)最小值概念上(反映)固定信道，改變信源，使信息率最大（信道傳輸能力）固定信源，改變信道，使信息率最?。ㄐ旁纯蓧嚎s程度）通信上使傳輸信息量最大，Pe→0——信道編碼用盡可能少的碼符號傳送——信源編碼10葉中行信息論課件第五章共67頁，您現(xiàn)在瀏覽的是第10頁!11葉中行信息論課件第五章共67頁，您現(xiàn)在瀏覽的是第11頁!上式中第二項最小，所以令，，可得對應(yīng)的試驗信道轉(zhuǎn)移概率矩陣為12葉中行信息論課件第五章共67頁，您現(xiàn)在瀏覽的是第12頁!

2、R(D)是關(guān)于平均失真度D的（下）凸函數(shù)

設(shè)為任意兩個平均失真，，則有：3、R(D)是區(qū)間上的連續(xù)和嚴(yán)格單調(diào)遞減函數(shù)由信息率失真函數(shù)的下凸性可知，R(D)在上連續(xù)；又由R(D)函數(shù)的非增性且不為常數(shù)知，R(D)是區(qū)間上的嚴(yán)格單調(diào)遞減函數(shù)。13葉中行信息論課件第五章共67頁，您現(xiàn)在瀏覽的是第13頁!信息率失真函數(shù)的一般形狀14葉中行信息論課件第五章共67頁，您現(xiàn)在瀏覽的是第14頁!一、信息率失真函數(shù)的參量表述應(yīng)用拉格朗日乘子法，原則上可以求出解來．15葉中行信息論課件第五章共67頁，您現(xiàn)在瀏覽的是第15頁!

由式(1)知，當(dāng)信源的概率分布P(x)固定，平均互信息僅僅是試驗信道P(x^|x)的函數(shù).若先不考慮式(2)的約束，約束條件式(3)包含n個等式，取拉格朗日乘子α分別與之對應(yīng)；并取拉氏乘子λ與式(4)對應(yīng).由此構(gòu)成輔助函數(shù)：(2)(3)(4)16葉中行信息論課件第五章共67頁，您現(xiàn)在瀏覽的是第16頁!對x^求和，得將（**）代入（*）得到乘P(x),對x求和，最后同除以P(x^)得到17葉中行信息論課件第五章共67頁，您現(xiàn)在瀏覽的是第17頁!

由式(1)知，當(dāng)信源的概率分布P(x)固定，平均互信息僅僅是試驗信道P(x^|x)的函數(shù)。若先不考慮式(2)的約束，約束條件式(3)包含n個等式，取拉格朗日乘子α分別與之對應(yīng)；并取拉氏乘子λ與式(4)對應(yīng).由此構(gòu)成輔助函數(shù)：(2)(3)(4)18葉中行信息論課件第五章共67頁，您現(xiàn)在瀏覽的是第18頁!注：這時所得的結(jié)果是以λ為參量的表達(dá)式，而不是顯式表達(dá)式，因而所得到的R(D)的表達(dá)式也是以λ為參量的表達(dá)式．參量λ對應(yīng)的限制條件為式(4)，它與允許的失真度D有關(guān)，所以以λ為參量就相當(dāng)于以D為參量．19葉中行信息論課件第五章共67頁，您現(xiàn)在瀏覽的是第19頁!對x^求和，得將（**）代入（*）得到乘P(X),對x求和，最后同除以P(x^)得到兩端同乘P(x)，對x求和：20葉中行信息論課件第五章共67頁，您現(xiàn)在瀏覽的是第20頁!對x^求和，得將（**）代入（*）得到乘P(X),對x求和，最后同除以P(x^)得到21葉中行信息論課件第五章共67頁，您現(xiàn)在瀏覽的是第21頁!將上述結(jié)果代入式子中，得22葉中行信息論課件第五章共67頁，您現(xiàn)在瀏覽的是第22頁!將上述結(jié)果代入式子中，得由于λ取負(fù)值，所以.又要滿足解得而.所以，當(dāng)時，必有因此分兩個區(qū)間計算率失真函數(shù).1）23葉中行信息論課件第五章共67頁，您現(xiàn)在瀏覽的是第23頁!計算得：綜上所述，得24葉中行信息論課件第五章共67頁，您現(xiàn)在瀏覽的是第24頁!三、r元等概分布對稱信源的率失真函數(shù)對應(yīng)的率失真分布：25葉中行信息論課件第五章共67頁，您現(xiàn)在瀏覽的是第25頁!因為是四元對稱信道，又是等概率分布，所以根據(jù)四元離散對稱信源可得26葉中行信息論課件第五章共67頁，您現(xiàn)在瀏覽的是第26頁!定理的含義是：只要碼長n足夠長，總可以找到一種信源編碼，使編碼后的信息傳輸率略大于(直至無限逼近)率失真函數(shù)R(D)，而碼的平均失真度不大于給定的允許失真度，即：由于R(D)為給定D前提下信源編碼可能達(dá)到的下限，所以香農(nóng)第三定理即說明了：達(dá)到此下限的最佳信源編碼是存在的．27葉中行信息論課件第五章共67頁，您現(xiàn)在瀏覽的是第27頁!香農(nóng)第三定理仍然只是個存在性定理，至于最佳編碼方法如何尋找，定理中并沒有給出，因此有關(guān)理論的實際應(yīng)用有待于進(jìn)一步研究．如何計算符合實際信源的信息率失真函數(shù)R(D)?如何尋找最佳編碼方法才能達(dá)到信息壓縮的極限值R(D)?這是該定理在實際應(yīng)用中存在的兩大問題，它們的徹底解決還有賴于繼續(xù)的努力．盡管如此，香農(nóng)第三定理畢竟對最佳限失真信源編碼方法的存在給出了肯定的回答，它為今后人們在該領(lǐng)域的不斷深入探索提供了堅定的信心．28葉中行信息論課件第五章共67頁，您現(xiàn)在瀏覽的是第28頁!平均損失和信息價值香農(nóng)信息論的信息量——客觀信息量的重要性因人而異——主觀把平均失真理解為平均損失，便可衡量價值;一、例——某廠生產(chǎn)：合格品—x1，p(x1)=0.99廢品—x2，p(x2)=0.01檢驗：合格品—y1，合格品報廢—損失1元廢品—y2，廢品出廠—損失100元建模型檢驗不正確引起的損失——信道傳輸失真信息量相同，但價值不同信源信道X(生產(chǎn))(檢驗)Y29葉中行信息論課件第五章共67頁，您現(xiàn)在瀏覽的是第29頁!2.產(chǎn)品未經(jīng)檢驗全部報廢p(y1/x1)=p(y1/x2)=0p(y2/x1)=p(y2/x2)=1[結(jié)論]①產(chǎn)品未經(jīng)檢驗全部報廢引起損失0.99元②出廠一個廢品比報廢99個合格品的損失大③根據(jù)Dmax定義，Dmax=0.99④若允許損失為0.99元，則無需檢驗，把產(chǎn)品報廢即可信源信道X(生產(chǎn))(檢驗)Y平均損失和信息價值30葉中行信息論課件第五章共67頁，您現(xiàn)在瀏覽的是第30頁!4.檢驗有一定誤差(設(shè)錯判概率為0.1)p(y1/x1)=p(y2/x2)=0.9p(y2/x1)=p(y1/x2)=0.1[結(jié)論1]比最大損失(0.99元)減少了0.791元，原因是檢驗獲得了信息量I(X;Y)p(x1)0.99p(x2)0.01p(y1)p(y2)0.90.90.10.1平均損失和信息價值31葉中行信息論課件第五章共67頁，您現(xiàn)在瀏覽的是第31頁![結(jié)論2]有差檢驗的信息價值比無差檢驗的高！可畫出信息(R)～損失(D)曲線反之，D(R)——信息率為R時的平均損失00.199

0.99

D(元)R(D)(bit)H(X)0.0810.025Dmax平均損失和信息價值32葉中行信息論課件第五章共67頁，您現(xiàn)在瀏覽的是第32頁!基站控制器

無線基站子系統(tǒng)公用陸地移動通信網(wǎng)

公共交換電話網(wǎng)絡(luò)33葉中行信息論課件第五章共67頁，您現(xiàn)在瀏覽的是第33頁!目前已經(jīng)進(jìn)行商業(yè)應(yīng)用的2.5G移動通信技術(shù)是從2G邁向3G的銜接性技術(shù);GPRS、WAP、藍(lán)牙(Bluetooth)等技術(shù)都是2.5G技術(shù).

34葉中行信息論課件第五章共67頁，您現(xiàn)在瀏覽的是第34頁!WAP（WirelessApplicationProtocol，無線應(yīng)用通訊協(xié)議）是移動通信與互聯(lián)網(wǎng)結(jié)合的階段性產(chǎn)物，也是大家聽說最多的。這項技術(shù)讓使用者可以用手機之類的無線裝置上網(wǎng)，透過小型屏幕遍游在各個同站之間;35葉中行信息論課件第五章共67頁，您現(xiàn)在瀏覽的是第35頁!1.定義信源編碼器輸入X∈{x1,x2,…,xi,…,xn}輸出（復(fù)制）X^∈{x^1,x^2,…,x^j,…,x^n}若xi=x^j——則無失真若xi≠x^j——則有失真[定義][含義]衡量用x^代替x所引起的失真程度．

通常較小的d代表較小的失真，d＝0表示沒有失真—單符號失真度！36葉中行信息論課件第五章共67頁，您現(xiàn)在瀏覽的是第36頁![例1]

離散對稱信源．信源變量x＝{x1,x2,…xn}，接收變量X^＝{x^1,x^2,…x^ｎ}。定義單個符號失真度：這種失真稱為漢明失真．漢明失真矩陣＿對角線上的元素為零，即：對二元對稱信源(n＝2)，信源X＝{0,1}，接收變量X^＝{0,1}．在漢明失真定義下，失真矩陣為：37葉中行信息論課件第五章共67頁，您現(xiàn)在瀏覽的是第37頁!須強調(diào):假設(shè)Ｘ是信源，Ｘ^是信宿，那么兩者之間必有信道：轉(zhuǎn)移概率p(ｘ^|ｘ)實際這里Ｘ指的是原始的未失真信源，而Ｘ^是指失真以后的信源．有時又把p(ｘ^|ｘ)稱為試驗信道的轉(zhuǎn)移概率，如圖所示：原始信源失真信源試驗信道信道ＸＸ^p(ｘ^|ｘ)38葉中行信息論課件第五章共67頁，您現(xiàn)在瀏覽的是第38頁!若平均失真度D不大于我們所允許的失真D，即：DD稱此為保真度準(zhǔn)則（定義5.1.2）．信源固定(給定P(x))，單個符號失真度固定時(給定d(x,x^))，選擇不同試驗信道，相當(dāng)于不同的編碼方法，所得的平均失真度是不同的。有些試驗信道滿足DD，而有些試驗信道D＞D.凡滿足保真度準(zhǔn)則----平均失真度DD的試驗信通稱為---D失真許可的試驗信道．平均失真是對給定信源分布,在給定轉(zhuǎn)移概率分布的信道中傳輸時的失真的總體量度39葉中行信息論課件第五章共67頁，您現(xiàn)在瀏覽的是第39頁!三、信息率失真函數(shù)的定義1.率失真函數(shù)問題產(chǎn)生?

對于信息容量為C的信道傳輸信息傳輸率為R的信源時，如果R＞C，就必須對信源壓縮，使其壓縮后信息傳輸率R’小于信道容量C，但同時要保證壓縮所引人的失真不超過預(yù)先規(guī)定的限度——信息壓縮問題就是對于給定的信源，在滿足平均失真

的前提下，使信息率盡可能小。40葉中行信息論課件第五章共67頁，您現(xiàn)在瀏覽的是第40頁!由于平均互信息I(U;V)是P(x^/

x)的凹函數(shù)，所以極小值存在．這個最小值就是在DˉD的條件下，信源必須傳輸?shù)淖钚∑骄畔⒘浚矗篟(D)-------信息率失真函數(shù)或簡稱率失真函數(shù)。單位是奈特／信源符號或比特／信源符號41葉中行信息論課件第五章共67頁，您現(xiàn)在瀏覽的是第41頁!四、信息率失真函數(shù)的性質(zhì)允許失真度D的下限可以是零，即不允許任何失真的情況.1、R(D)的定義域R(D)的定義域為且：當(dāng)失真矩陣中每行至少一個零元．42葉中行信息論課件第五章共67頁，您現(xiàn)在瀏覽的是第42頁!解：[例３]

設(shè)試驗信道輸入符號集，各符號對應(yīng)概率分別為)={1/3,1/3,1/3}，失真矩陣如下所示，求和以及相應(yīng)的試驗信道的轉(zhuǎn)移概率矩陣。

令對應(yīng)最小失真度的，其它為“0”，可得對應(yīng)的試驗信道轉(zhuǎn)移概率矩陣為

43葉中行信息論課件第五章共67頁，您現(xiàn)在瀏覽的是第43頁!4.1.3率失真函數(shù)R(D)性質(zhì)(續(xù))[計算][例４]離散二元信源，求Dmax[解]44葉中行信息論課件第五章共67頁，您現(xiàn)在瀏覽的是第44頁!

４R(D)的值域

①

R(D)min=0

②

R(D)max=R(0)，D=0即無失真?zhèn)鬏敗乇３志幋a(1)對離散信源、無噪信道，R(D)max=H(X)(2)對連續(xù)信源，R(D)max→H∞

當(dāng)且僅當(dāng)D不小于Dmax45葉中行信息論課件第五章共67頁，您現(xiàn)在瀏覽的是第45頁!5.2離散信源率失真函數(shù)的計算已知信源的概率分布P(X)和失真函數(shù)d(x,x^)，就可求得信源的R(D)函數(shù)；原則上它與信道容量一樣，即在有約束條件下求極小值的問題．

也就是適當(dāng)選取試驗信道P(x^|x)使平均互信息最小化：其約束條件為：

46葉中行信息論課件第五章共67頁，您現(xiàn)在瀏覽的是第46頁!但是，如果要求得到明顯的解析表達(dá)式，則比較困難，通常只能用參量形式來表達(dá)．即便如此，除簡單情況外，實際計算仍然是相當(dāng)困難的．尤其是第三個約束條件，它是求解R(D)函數(shù)最主要的障礙．因為應(yīng)用拉格朗日乘子法解得的一個或某幾個P(x^|x)很可能是負(fù)的．在這情況下，必須假設(shè)某些P(x^|x)=0，然后重新計算，這就使得計算復(fù)雜化了．目前，可采用收斂的迭代算法在電子計算機上求解R(D)函數(shù)．下面介紹用拉格朗日乘子法求解R(D)函數(shù)，并用λ作為參量來表述率失真函數(shù)R(D)和失真函數(shù)D(λ)：47葉中行信息論課件第五章共67頁，您現(xiàn)在瀏覽的是第47頁!求極值，就是求輔助函數(shù)一階導(dǎo)數(shù)等于零的方程組的解.即求：所以原則上只需求解式(6)、(3)和(4)的方程組，即可求出I(U;V)在約束條件下的極小值．令代入（6）得到48葉中行信息論課件第五章共67頁，您現(xiàn)在瀏覽的是第48頁!解方程組可以求得P(x^).從而，代入（**）式求出β(x),從而將其代入（*）式得到P(x^|x).

49葉中行信息論課件第五章共67頁，您現(xiàn)在瀏覽的是第49頁!得到率失真函數(shù)和平均失真函數(shù)：50葉中行信息論課件第五章共67頁，您現(xiàn)在瀏覽的是第50頁!例題

設(shè)信源，相應(yīng)的概率分布為漢明失真求此信源的，并給出其率失真分布．解：利用式子計算范例展示51葉中行信息論課件第五章共67頁，您現(xiàn)在瀏覽的是第51頁!解得：利用結(jié)果（**），可得52葉中行信息論課件第五章共67頁，您現(xiàn)在瀏覽的是第52頁!解得：利用結(jié)果（**），可得53葉中行信息論課件第五章共67頁，您現(xiàn)在瀏覽的是第53頁!得到率失真函數(shù)和平均失真函數(shù)：54葉中行信息論課件第五章共67頁，您現(xiàn)在瀏覽的是第54頁!2）利用結(jié)果（**），可得55葉中行信息論課件第五章共67頁，您現(xiàn)在瀏覽的是第55頁!二、二進(jìn)對稱信源的率失真函數(shù)它的率失真函數(shù)：對應(yīng)的率失真分布：56葉中行信息論課件第五章共67頁，您現(xiàn)在瀏覽的是第56頁!習(xí)題：一個四元對稱信道接收符號為其失真矩陣為求信源的R(D)函數(shù)57葉中行信息論課件第五章共67頁，您現(xiàn)在瀏覽的是第57頁!5.3限失真信源編碼定理

定理5.3.1(限失真信源編碼定理，香農(nóng)第三極限定理)設(shè)R(D)為一離散無記憶信源的率失真函數(shù)，并且有有限的失真測度D．對于任意，以及任意長的碼長n，一定存在一種信源編碼C，其碼字個數(shù)為使編碼后碼的平均失真度．58葉中行信息論課件第五章共67頁，您現(xiàn)在瀏覽的是第58頁!實際的信源編碼(無失真編碼或先限失真編碼后無失真編碼)的最終目標(biāo)是盡量接近最佳編碼，使編碼信息傳輸率接近最大值logr，而同時又保證譯碼后能無失真地恢復(fù)信源的全部信息量H(X)或限失真條件下的必要信息量R(D)．編碼后信息傳輸率的提高使每個編碼符號能攜帶盡可能多的信息量，-----使得傳輸同樣多的信源總信息量所需的碼符號數(shù)大大減少；------使信道容量C不變的前提下使傳輸時間大大縮短，從而提高了通信的效率．59葉中行信息論課件第五章共67頁，您現(xiàn)在瀏覽的是第59頁!香農(nóng)信息論三個基本概念——信源熵、信道容量、率失真函數(shù)，都是臨界值三個極限定理——無失真信源編碼定理、限失真信源編碼定理、信道編碼定理，都是存在性定理60葉中行信息論課件第五章共67頁，您現(xiàn)在瀏覽的是第60頁!1.產(chǎn)品未經(jīng)檢驗全部出廠p(y1/x1)=p(y1/x2)=1p(y2/x1)=p(y2/x2)=0

[結(jié)論]產(chǎn)品未經(jīng)檢驗全部出廠引起損失1元信源信道X(生產(chǎn))(檢驗)Y平均損失和信息價值61葉中行信息論課件第五章共67頁，您現(xiàn)在瀏覽的是第61頁!3.檢驗完全正確p(y1/x1)=p(y2/x2)=1