信息論傅祖蕓9--

1、第七章第七章 保真度準則下的信源編碼保真度準則下的信源編碼第一節(jié) 失真度和平均失真度第二節(jié) 信息率失真函數(shù)及其性質(zhì)第三節(jié) 二元信源和離散對稱信源的R(D)函數(shù) 第四節(jié) 保真度準則下的信源編碼定理 第五節(jié) 聯(lián)合有失真信源信道編碼定理第六節(jié) 有失真信源編碼定理的實用意義第一節(jié)第一節(jié) 失真度和平均失真度失真度和平均失真度 在實際生活中，人們不一定要求完全無失真的恢復消息，也就是允許有一定的失真。 那么在允許一定程度失真的條件下，能夠把信源信息壓縮到什么程度，也就是，允許一定程度失真的條件下，如何能快速的傳輸信息，這就是本章所要討論的問題。 本章所討論的內(nèi)容是量化、數(shù)模轉(zhuǎn)換、頻帶壓縮和數(shù)據(jù)壓縮的理論基

2、礎(chǔ)。 1、失真度信源信源編碼信道編碼信道信道譯碼信源譯碼信宿干擾 根據(jù)信道編碼定理，我們可以把信道編碼、信道和信道解碼等價成是一個沒有任何干擾的廣義信道，這樣收信者收到消息后，所產(chǎn)生的失真只是由信源編碼帶來的。我們也可以把信源編碼和信源譯碼等價成一個信道。第一節(jié)第一節(jié) 失真度和平均失真度失真度和平均失真度信源信宿第一節(jié)第一節(jié) 失真度和平均失真度失真度和平均失真度試驗信道 我們稱此信道為試驗信道試驗信道?，F(xiàn)在我們要研究在給定允許失真的條件下，是否可以設(shè)計一種信源編碼使信息傳輸率為最低。為此，我們首先討論失真的測度。 設(shè)信源變量為 ，其概率分布為 12,.rUu uu1( ) (). ()rP u

3、P uP u對于每一對(u,v)，我們指定一個非負的函數(shù)( ,)0ijd u v稱為單個符號的失真度（或稱失真函數(shù)） 接受端變量為 ，12,.sVv vv第一節(jié)第一節(jié) 失真度和平均失真度失真度和平均失真度 失真函數(shù)用來表征信源發(fā)出一個符號 ，而在接收端再現(xiàn)成符號 所引起的誤差或失真。d越小表示失真越小，等于0表示沒有失真。 可以將所有的失真函數(shù)排列成矩陣的形式：iujv111212122212( ,)( ,).( ,)(,)(,).(,).(,)(,).(,)ssrrrsd u vd u vd u vd u vd u vd u vDd u vd u vd u v我們稱它為失真矩陣。第一節(jié)第一節(jié)

4、 失真度和平均失真度失真度和平均失真度例1：0( ,)1ijd u vijij當uv當uv失真矩陣為：01.110.1.11.0D這種失真成為漢明失真在二元情況下：1001D第一節(jié)第一節(jié) 失真度和平均失真度失真度和平均失真度例2：刪除信源1sr0( ,)1(1/2()ijijd u vijjsi除j=s以外的所有i和所有j）所有對于二元刪除信源r=2,s=301/2111/20D第一節(jié)第一節(jié) 失真度和平均失真度失真度和平均失真度例3：對稱信源r=s，定義失真度為：2( ,)()ijjid u vvu當r=s=3時，012U 012V 失真矩陣為：014101410D第一節(jié)第一節(jié) 失真度和平均失

5、真度失真度和平均失真度2、平均失真度 ( ,)ijDE d u v若已知試驗信道的傳遞概率，則平均失真度為：,11( , ) ( , )( ) (/) ( ,)rsijiijU VijDP u v d u vP u P vu d u v 若平均失真度 不大于我們所允許的失真D，我們稱此為保真度準則。DDD凡滿足保真度準則的這些試驗信道稱為D失真許可的試驗信道。把所有D失真許可的試驗信道組成一個集合，用符號 表示。DB第二節(jié)第二節(jié) 信息率失真函數(shù)及其性質(zhì)信息率失真函數(shù)及其性質(zhì)1、信息率失真函數(shù) 當信源和失真函數(shù)給定后，我們總希望在滿足保真度準則下尋找平均互信息的最小值。也就是在 中找一個信道，使

6、平均互信息取極小值。這個最小值就是在 的條件下，信源必須傳輸?shù)淖钚∑骄畔⒘俊?DB()min ( ; )DBR DI U VDD 改變試驗信道求平均互信息的最小值，實質(zhì)上是選擇一種編碼方式使信息傳輸率為最小。第二節(jié)第二節(jié) 信息率失真函數(shù)及其性質(zhì)信息率失真函數(shù)及其性質(zhì)2、信息率失真函數(shù)的性質(zhì) 1)、R(D)的定義域是max(0,)D (1)、 和m inDmin()R D 允許失真度D的最小值為0，即不允許有失真，這要求失真矩陣中每行至少有一個為0。 R(0)的最小值為H(U)，即信息傳輸率至少為信源的信息熵例：011/2101/2Dmin1( ) 00riiDP u第二節(jié)第二節(jié) 信息率失真函

7、數(shù)及其性質(zhì)信息率失真函數(shù)及其性質(zhì) 滿足最小失真度的試驗信道是一個無噪無損信道：100010P(2)maxmax()DR D和因為D越大，R(D)越小，最小為0，當D再大時，R(D)a也只能為0，此時，發(fā)送與接收統(tǒng)計獨立，即：( / )( )P v uQ v失真度函數(shù)變?yōu)椋?( ) ( ) ( , )U VDP u Q v d u v第二節(jié)第二節(jié) 信息率失真函數(shù)及其性質(zhì)信息率失真函數(shù)及其性質(zhì) 所以， 就是在R(D)=0的情況下，求 的最小值max( ),min( ) ( ) ( , )Q vU VDP u Q v d u v當 時， 而當 時maxDD()0,R D minmaxDDD( )()

8、0H UR DmaxDD上式可改寫為max( )( )min( )( ) ( , )min( )( )Q vQ vVUVDQ vP u d u vQ v d v 可以這樣選 ，當 最小時，取 等于1，則：()Qv()Qv( )d vmaxmin( )min( ) ( , )VVUDd vP u d u v第二節(jié)第二節(jié) 信息率失真函數(shù)及其性質(zhì)信息率失真函數(shù)及其性質(zhì)2)、 R(D)函數(shù)的單調(diào)遞減性和連續(xù)性0DR(D)minDmaxD第三節(jié) 二元信源和離散對稱信源的R(D)函數(shù)1、二元對稱信源的R(D)函數(shù) 設(shè)二元信源U=0,1，其分布概率 ，( ) ,1P u12而接收變量v=0,1，設(shè)漢明失真矩

9、陣為：0110D 因而最小失真度 。并能找到滿足該最小失真的試驗信道，且是一個無噪無損信道，其信道矩陣為：min0D1001P(0)( ; )( )RI U VH第三節(jié) 二元信源和離散對稱信源的R(D)函數(shù)maxmin( ) ( , )VUDP u d u vmin (0) (0,0)(1) (1,0); (0) (0,1)(1) (1,1)VPdPdPdPdmin(1), 要達到最大允許失真，唯一確定 0101P此時，可計算得信息傳輸率( ; )0I U V 一般情況下，當 時，max0DD, ( , ) ( , )U VDE dp u v d u v(0,1)(1,0)EP uvP uvP

10、第三節(jié) 二元信源和離散對稱信源的R(D)函數(shù)可以計算得：二元信源得信息率失真函數(shù)為()( )()R DHH D例：0.40.2D 在漢明失真條件下，( )()0()0HH DDR DD()(0.4)(0.2)0.249R DHH第三節(jié) 二元信源和離散對稱信源的R(D)函數(shù) 對于離散對稱信源，在漢明失真條件下：1loglog(1)()01()101rDrH DDrR DDr 第四節(jié) 保真度準則下的信源編碼定理 定理7.1 保真度準則下的信源編碼定理 設(shè)R(D)為一離散無記憶信源的信息率失真函數(shù)，并且有有限的失真測度。對于任意的 ，以及任意足夠長的碼長n，則一定存在一種信源編碼C，其碼字個數(shù)為0

11、,0 ,0D ()n R DMe而編碼后的平均失真度( )d CD如果用二元編碼，則： ()2n R DM 該定理稱為香農(nóng)第三定理。它告訴我們，對于任何失真度D，只要碼長足夠長，總可以找到一種編碼C，使編碼后的每個信源符號的信息傳輸率log()MRR Dn第四節(jié)保真度準則下的信源編碼定理 定理7.2（信源編碼逆定理）不存在平均失真度D，而平均信息傳輸率 的任何信源編碼。即對任意碼長n的信源碼C，若碼字個數(shù) ，一定()RR D ( )2n R DM( )d CD 該定理告訴我們：如果編碼后平均每個信源符號的信息傳輸率 小于信息率失真函數(shù) ，就不能在保真度準則下再現(xiàn)信源的消息。R()R D第五節(jié)

12、聯(lián)合有失真信源信道編碼定理 定理7.3 （信息傳輸定理）離散無記憶信源的S的信息率失真函數(shù)為R(D)，離散無記憶信道的信道容量C，若滿足()CR D 則信源輸出的信源序列能在此信道輸出端重現(xiàn)，其失真小于等于D。 定理7.4 離散無記憶信源的S的信息率失真函數(shù)為R(D)，每秒鐘輸出 個信源符號，離散無記憶信道的信道容量C，每秒輸出 個信源符號，若滿足 1/sT1/CT()CSCR DTT 則信源輸出的信源序列能在此信道輸出端重現(xiàn)，其失真小于等于D。第五節(jié) 聯(lián)合有失真信源信道編碼定理 定理7.4 離散無記憶信源的S的信息率失真函數(shù)為R(D)，每秒鐘輸出 個信源符號，離散無記憶信道的信道容量C，每秒

13、輸出 個信源符號，若滿足 1/sT1/CT()CSCR DTT 則信源輸出的信源序列能在此信道輸出端重現(xiàn)，其失真小于等于D。第六節(jié) 有失真信源編碼定理的實用意義例：01( )1/21/2UP u 要對此信源進行無失真編碼，每個信源符號必須用一個二元符號來表示，信源的信息輸出率為R=H=1。若允許失真存在，并定義失真函數(shù)為漢明失真，即0( , )1ijijuvd u vuv可以設(shè)想這樣一種信源編碼：第六節(jié) 有失真信源編碼定理的實用意義121340000010000010100uuvuu562781111101111101011uuvuu無噪無損信道傳輸00001111第六節(jié) 有失真信源編碼定理的實用意義這種編碼方法，可以看成是一種特殊的試驗信道1,( )(/)0( )jjijijivC vf uP vuvf u1( )( ) ,( )Ud CP U d u f uN1 1101 1 101 1 13 84 信息率為1/3，而平均失真為1/4，根據(jù)香農(nóng)第三定理，若允許失真D=1/4時，總可以找到一種編碼，使信息輸出率達到極限R(1/4)11( )1( )0.18944RH 第