葉中行-信息論-第五章課件

第5章

限失真信源編碼和率失真函數(shù)1無失真信源編碼和有噪信道編碼表明：只要信道的信息傳輸速率小于信道容量，總能找到一種編碼方法，使得在該信道上的信息傳輸?shù)牟铄e(cuò)概率任意小；反之，若信道的信息傳輸速率大于信道容量，則不可能使信息傳輸差錯(cuò)概率任意?。牵瑹o失真的編碼并非總是必要的：例如在傳送語音信號時(shí)，由于人耳接受的帶寬和分辨率是有限的，從而可以把頻譜范圍從20Hz~8kHz的語音信號去掉低端和高端的頻率，視為帶寬只有從300Hz~3400Hz的信號；這樣，即使傳輸?shù)恼Z音信號有一些失真，人耳還是可以分辨或感覺出來，已滿足語音信號傳輸?shù)囊螅?在允許一定程度失真的條件下，能夠把信源信息壓縮到什么程度，即最少需要多少比特?cái)?shù)才能描述信源，是本章將要討論的問題．31.定義信源編碼器輸入X∈{x1,x2,…,xi,…,xn}輸出（復(fù)制）X^∈{x^1,x^2,…,x^j,…,x^n}若xi=x^j——?jiǎng)t無失真若xi≠x^j——?jiǎng)t有失真[定義][含義]衡量用x^代替x所引起的失真程度．

通常較小的d代表較小的失真，d＝0表示沒有失真—單符號失真度！5若信源變量X有n個(gè)符號，接收變量X^有n個(gè)符號，則d(x,x^)就有n×n個(gè),它可以排列成矩陣形式，即：它為失真矩陣D．6[例1]

離散對稱信源．信源變量x＝{x1,x2,…xn}，接收變量X^＝{x^1,x^2,…x^ｎ}。定義單個(gè)符號失真度：這種失真稱為漢明失真．漢明失真矩陣＿對角線上的元素為零，即：對二元對稱信源(n＝2)，信源X＝{0,1}，接收變量X^＝{0,1}．在漢明失真定義下，失真矩陣為：7[例２]對稱信源．信源變量Ｘ＝{ｘ1,ｘ2,…ｘｎ}，接收變量Ｘ^＝{ｘ^1,ｘ^2,…ｘ^ｎ}。失真度定義為：若信源符號代表信源輸出信號的幅度值，這就是一種以方差表示的失真度。它意味著幅度差值大的要比幅度差值小的所引起的失真更為嚴(yán)重，嚴(yán)重程度用平方來表示。當(dāng)ｎ＝3時(shí)，Ｘ＝{0,1,2}，Ｘ^＝{0,1,2}，則失真矩陣為：上述例子說明了具體失真度的定義．一般情況下根據(jù)實(shí)際信源的失真，可以定義不同的失真和誤差的度量．另外還可以按其他標(biāo)準(zhǔn)，如引起的損失、風(fēng)險(xiǎn)、主觀感覺上的差別大小等來定義失真度d(ｘ,ｘ^)．8二、平均失真測度信源Ｘ和信宿Ｘ^都是隨機(jī)變量，故單個(gè)符號失真度d(ｘ,ｘ^)也是隨機(jī)變量．顯然，規(guī)定了單個(gè)符號失真度后，傳輸一個(gè)符號引起的平均失真，即信源平均失真度：在離散情況下，信源Ｘ＝{x1,x2,…xn}，其概率分布P(x)＝[P(x1),P(x2),…P(xn)]，信宿X^＝{X^1,X^2,…X^n}．若已知試驗(yàn)信道的傳遞概率為P(x|x^)時(shí)，則平均失真度為：10[說明]①是在平均意義上，對系統(tǒng)失真的總體描述②是信源統(tǒng)計(jì)特性p(x)的函數(shù)是信道統(tǒng)計(jì)特性p(x/x^)的函數(shù)是規(guī)定失真度d(x,x^)的函數(shù)若保持p(x)、d(x,x^)不變，則平均失真度就是信道特性p(x/x^)的函數(shù)研究：在滿足保真度準(zhǔn)則前提下，求信息率最小值12三、信息率失真函數(shù)的定義

信源給定，且又具體定義了失真函數(shù)以后，總希望在滿足一定失真的情況下，使信源傳輸給收信者的信息傳輸率R盡可能地小．即在滿足保真度準(zhǔn)則下，尋找信源必須傳輸給收信者的信息率R的下限值-------------這個(gè)下限值與D有關(guān)．從接收端來看，就是在滿足保真度準(zhǔn)則下，尋找再現(xiàn)信源消息所必須獲得的最低平均信息量．而接收端獲得的平均信息量可用平均互信息I(X;X^)來表示，這就變成了在滿足保真度準(zhǔn)則的條件下，尋找平均互信息I(X;X^)的最小值．14由于平均互信息I(U;V)是P(x^/

x)的凹函數(shù)，所以極小值存在．這個(gè)最小值就是在DˉD的條件下，信源必須傳輸?shù)淖钚∑骄畔⒘浚矗篟(D)-------信息率失真函數(shù)或簡稱率失真函數(shù)。單位是奈特／信源符號或比特／信源符號15率失真函數(shù)與信道容量的比較信道容量C率失真函數(shù)R(D)數(shù)學(xué)上固定p(x^/x),改變p(x),求得I(X;X^)最大值固定p(x),改變p(x^/xi),求得I(X;X^)最小值概念上(反映)固定信道，改變信源，使信息率最大（信道傳輸能力）固定信源，改變信道，使信息率最小（信源可壓縮程度）通信上使傳輸信息量最大，Pe→0——信道編碼用盡可能少的碼符號傳送——信源編碼16四、信息率失真函數(shù)的性質(zhì)允許失真度D的下限可以是零，即不允許任何失真的情況.1、R(D)的定義域R(D)的定義域?yàn)榍遥寒?dāng)失真矩陣中每行至少一個(gè)零元．1718上式中第二項(xiàng)最小，所以令，，可得對應(yīng)的試驗(yàn)信道轉(zhuǎn)移概率矩陣為204.1.3率失真函數(shù)R(D)性質(zhì)(續(xù))[計(jì)算][例４]離散二元信源，求Dmax[解]21

４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不小于Dmax23信息率失真函數(shù)的一般形狀24一、信息率失真函數(shù)的參量表述應(yīng)用拉格朗日乘子法，原則上可以求出解來．26但是，如果要求得到明顯的解析表達(dá)式，則比較困難，通常只能用參量形式來表達(dá)．即便如此，除簡單情況外，實(shí)際計(jì)算仍然是相當(dāng)困難的．尤其是第三個(gè)約束條件，它是求解R(D)函數(shù)最主要的障礙．因?yàn)閼?yīng)用拉格朗日乘子法解得的一個(gè)或某幾個(gè)P(x^|x)很可能是負(fù)的．在這情況下，必須假設(shè)某些P(x^|x)=0，然后重新計(jì)算，這就使得計(jì)算復(fù)雜化了．目前，可采用收斂的迭代算法在電子計(jì)算機(jī)上求解R(D)函數(shù)．下面介紹用拉格朗日乘子法求解R(D)函數(shù)，并用λ作為參量來表述率失真函數(shù)R(D)和失真函數(shù)D(λ)：27

由式(1)知，當(dāng)信源的概率分布P(x)固定，平均互信息僅僅是試驗(yàn)信道P(x^|x)的函數(shù).若先不考慮式(2)的約束，約束條件式(3)包含n個(gè)等式，取拉格朗日乘子α分別與之對應(yīng)；并取拉氏乘子λ

與式(4)對應(yīng).由此構(gòu)成輔助函數(shù)：(2)(3)(4)28對x^求和，得將（**）代入（*）得到乘P(x),對x求和，最后同除以P(x^)得到30解方程組可以求得P(x^).從而，代入（**）式求出β(x),從而將其代入（*）式得到P(x^|x).

31

由式(1)知，當(dāng)信源的概率分布P(x)固定，平均互信息僅僅是試驗(yàn)信道P(x^|x)的函數(shù)。若先不考慮式(2)的約束，約束條件式(3)包含n個(gè)等式，取拉格朗日乘子α分別與之對應(yīng)；并取拉氏乘子λ

與式(4)對應(yīng).由此構(gòu)成輔助函數(shù)：(2)(3)(4)32得到率失真函數(shù)和平均失真函數(shù)：33注：這時(shí)所得的結(jié)果是以λ為參量的表達(dá)式，而不是顯式表達(dá)式，因而所得到的R(D)的表達(dá)式也是以λ為參量的表達(dá)式．參量λ對應(yīng)的限制條件為式(4)，它與允許的失真度D有關(guān)，所以以λ為參量就相當(dāng)于以D為參量．34例題

設(shè)信源，相應(yīng)的概率分布為漢明失真求此信源的，并給出其率失真分布．解：利用式子計(jì)算范例展示35對x^求和，得將（**）代入（*）得到乘P(X),對x求和，最后同除以P(x^)得到兩端同乘P(x)，對x求和：36解得：利用結(jié)果（**），可得37對x^求和，得將（**）代入（*）得到乘P(X),對x求和，最后同除以P(x^)得到38解得：利用結(jié)果（**），可得39將上述結(jié)果代入式子中，得40得到率失真函數(shù)和平均失真函數(shù)：41將上述結(jié)果代入式子中，得由于λ取負(fù)值，所以.又要滿足解得而.所以，當(dāng)時(shí)，必有因此分兩個(gè)區(qū)間計(jì)算率失真函數(shù).1）422）利用結(jié)果（**），可得43計(jì)算得：綜上所述，得44二、二進(jìn)對稱信源的率失真函數(shù)它的率失真函數(shù)：對應(yīng)的率失真分布：45三、r元等概分布對稱信源的率失真函數(shù)對應(yīng)的率失真分布：46習(xí)題：一個(gè)四元對稱信道接收符號為其失真矩陣為求信源的R(D)函數(shù)47因?yàn)槭撬脑獙ΨQ信道，又是等概率分布，所以根據(jù)四元離散對稱信源可得485.3限失真信源編碼定理

定理5.3.1(限失真信源編碼定理，香農(nóng)第三極限定理)設(shè)R(D)為一離散無記憶信源的率失真函數(shù)，并且有有限的失真測度D．對于任意，以及任意長的碼長n，一定存在一種信源編碼C，其碼字個(gè)數(shù)為使編碼后碼的平均失真度．49定理的含義是：只要碼長n足夠長，總可以找到一種信源編碼，使編碼后的信息傳輸率略大于(直至無限逼近)率失真函數(shù)R(D)，而碼的平均失真度不大于給定的允許失真度，即：由于R(D)為給定D前提下信源編碼可能達(dá)到的下限，所以香農(nóng)第三定理即說明了：達(dá)到此下限的最佳信源編碼是存在的．50實(shí)際的信源編碼(無失真編碼或先限失真編碼后無失真編碼)的最終目標(biāo)是盡量接近最佳編碼，使編碼信息傳輸率接近最大值logr，而同時(shí)又保證譯碼后能無失真地恢復(fù)信源的全部信息量H(X)或限失真條件下的必要信息量R(D)．編碼后信息傳輸率的提高使每個(gè)編碼符號能攜帶盡可能多的信息量，-----使得傳輸同樣多的信源總信息量所需的碼符號數(shù)大大減少；------使信道容量C不變的前提下使傳輸時(shí)間大大縮短，從而提高了通信的效率．51香農(nóng)第三定理仍然只是個(gè)存在性定理，至于最佳編碼方法如何尋找，定理中并沒有給出，因此有關(guān)理論的實(shí)際應(yīng)用有待于進(jìn)一步研究．如何計(jì)算符合實(shí)際信源的信息率失真函數(shù)R(D)?如何尋找最佳編碼方法才能達(dá)到信息壓縮的極限值R(D)?這是該定理在實(shí)際應(yīng)用中存在的兩大問題，它們的徹底解決還有賴于繼續(xù)的努力．盡管如此，香農(nóng)第三定理畢竟對最佳限失真信源編碼方法的存在給出了肯定的回答，它為今后人們在該領(lǐng)域的不斷深入探索提供了堅(jiān)定的信心．52香農(nóng)信息論三個(gè)基本概念——信源熵、信道容量、率失真函數(shù)，都是臨界值三個(gè)極限定理——無失真信源編碼定理、限失真信源編碼定理、信道編碼定理，都是存在性定理53平均損失和信息價(jià)值香農(nóng)信息論的信息量——客觀信息量的重要性因人而異——主觀把平均失真理解為平均損失，便可衡量價(jià)值;一、例——某廠生產(chǎn)：合格品—x1，p(x1)=0.99廢品—x2，p(x2)=0.01檢驗(yàn)：合格品—y1，合格品報(bào)廢—損失1元廢品—y2，廢品出廠—損失100元建模型檢驗(yàn)不正確引起的損失——信道傳輸失真信息量相同，但價(jià)值不同信源信道X(生產(chǎn))(檢驗(yàn))Y541.產(chǎn)品未經(jīng)檢驗(yàn)全部出廠p(y1/x1)=p(y1/x2)=1p(y2/x1)=p(y2/x2)=0

[結(jié)論]產(chǎn)品未經(jīng)檢驗(yàn)全部出廠引起損失1元信源信道X(生產(chǎn))(檢驗(yàn))Y平均損失和信息價(jià)值552.產(chǎn)品未經(jīng)檢驗(yàn)全部報(bào)廢p(y1/x1)=p(y1/x2)=0p(y2/x1)=p(y2/x2)=1[結(jié)論]①產(chǎn)品未經(jīng)檢驗(yàn)全部報(bào)廢引起損失0.99元②出廠一個(gè)廢品比報(bào)廢99個(gè)合格品的損失大③根據(jù)Dmax定義，Dmax=0.99④若允許損失為0.99元，則無需檢驗(yàn)，把產(chǎn)品報(bào)廢即可信源信道X(生產(chǎn))(檢驗(yàn))Y平均損失和信息價(jià)值563.檢驗(yàn)完全正確p(y1/x1)=p(y2/x2)=1p(y2/x1)=p(y1/x2)=0[結(jié)論]①為達(dá)無錯(cuò)檢驗(yàn)，需要0.081bit信息量②0.081bit信息量避免了0.99元的損失每bit價(jià)值=0.99/0.081=12.2元/bit信源信道X(生產(chǎn))(檢驗(yàn))Y平均損失和信息價(jià)值574.檢驗(yàn)有一定誤差(設(shè)錯(cuò)判概率為0.1)p(y1/x1)=p(y2/x2)=0.9p(y2/x1)=p(y1/x2)=0.1[結(jié)論1]比最大損失(0.99元)減少了0.791元，原因是檢驗(yàn)獲得了信息量I(X;Y)p(x1)0.99p(x2)0.01p(y1)p(y2)0.90.90.10.1平均損失和信息價(jià)值58[結(jié)論1]每bit價(jià)值=0.791/0.025=31.6元/bitp(x1)0.99p(x2)0.01p(y1)p(y2)0.90.90.10.1平均損失和信息價(jià)值59[結(jié)論2]有差檢驗(yàn)的信息價(jià)值比無差檢驗(yàn)的高！可畫出信息(R)～損失(D)曲線反之，D(R)——信息率為R時(shí)的平均損失00.199

0.99

D(元)R(D)(bit)H(X)0.0810.025Dmax平均損失和信息價(jià)值60

所謂3G，其實(shí)它的全稱為3rdGeneration，是指第三代數(shù)字通信.1995年問世的第一代模擬制式手機(jī)（1G）只能進(jìn)行語音通話；1996到1997年出現(xiàn)的第二代GSM等數(shù)字制式手機(jī)（2G）便增加了接收數(shù)據(jù)的功能，如接受