32第3章33多符號離散信道

1、hust furong wang- information and coding theory1第第3章信道容量章信道容量o 3.1信道的數(shù)學(xué)模型和分類信道的數(shù)學(xué)模型和分類o 3.2單符號離散信道的信道容量單符號離散信道的信道容量o 3.3多符號離散信道多符號離散信道n 3.3.1 多符號離散信道的數(shù)學(xué)模型多符號離散信道的數(shù)學(xué)模型n 3.3.2 離散無記憶信道和獨立并聯(lián)信道的信道離散無記憶信道和獨立并聯(lián)信道的信道容量容量o 3.4多用戶信道多用戶信道o 3.5連續(xù)信道連續(xù)信道o 3.6信道編碼定理信道編碼定理hust furong wang- information and coding th

2、eory2離散無記憶離散無記憶n次擴展信道次擴展信道的數(shù)學(xué)模型基本上與的模型相同。o 不同的是其輸入和輸出不是單個隨機變量x和y，而是隨機序列o 其概率空間為 121 2(,)(,).nnx xxyyyxy和 , (),pxy/x yhust furong wang- information and coding theory3簡單的離散無記憶信道簡單的離散無記憶信道o 簡單的離散無記憶信道的輸入和輸出都是單個隨機變量，其數(shù)學(xué)模型如下圖：o 信道的輸入隨機變量取值于符號集xo 信道的輸出隨機變量取值于符號集yo 信道的傳遞概率為 1,2,1,2,.,;.,nmxx xxyy yy信道 (/)j

3、ip yxxy(/)ijjipp yxhust furong wang- information and coding theory4簡單的離散無記憶信道簡單的離散無記憶信道o 信道矩陣為：o 且滿足n 這意味著矩陣中每一行之和為1。(/)(/)(/), .ijjijijipp yxp yyxxx p yxy其中其概率空間為 ,1111mnnmppppp11;1,2,jmijpinhust furong wang- information and coding theory512121( i1,2, j()(./.)/,2,)1nnnnnjninjijjiijkikikjp yp b ap y

4、 yyx xxxxy/輸入隨機矢量 的可能取值有n 個，分別是a，,n輸出隨機矢量 的可能取值有m 個，分別是b ，,m根據(jù)信道的無記憶特性，有離散無記憶信道的離散無記憶信道的n次擴展信道次擴展信道o 此離散無記憶信道的n次擴展信道的數(shù)學(xué)模型如下圖：n次擴展信道nxny(/)jip bahust furong wang- information and coding theory6n次擴展信道的信道矩陣次擴展信道的信道矩陣1212111212122212(/) i1,2,;1,2, (,) 1,2,(1,2, ) b(,) 1,2,nnnnnnnnnnnnmmnnn mijjiiiiikjjj

5、jppppppnpppp banjmaxxxininyyyjmp次擴展信道的信道矩陣為其中:p；，；1(1,2,)1 i1,2,1nnkmijjjmpnn，且滿足 這仍意味著 次擴展信道矩陣中各行之和為。hust furong wang- information and coding theory7n次擴展信道的信道矩陣次擴展信道的信道矩陣12121(/)(/)/)1,2,;1,2,nnkknkijjijjjiiijinnp ypp bap y yyx xxxnjm由于信道是無記憶的，故有其中：ihust furong wang- information and coding theory8例

6、例 二元對稱信道的二次擴展信道二元對稱信道的二次擴展信道o 分析的二次擴展信道。ppppxy001122222424nnxy二元無記憶對稱信道的輸入和輸出隨機變量 和 都取值于同一符號集 0,1 ，因此，二次擴展信道的輸入符號集為x = 00,01,10,11 ，共有n個輸入符號。輸出符號集為y = 00,01,10,11 ，共有m個輸出符號。hust furong wang- information and coding theory921111122113311441 (/),1,2,3,4 p(/)(00/00)(0/0) (0/0) p(/)(01/00)(0/0) (1/0) p(/

7、)(10/00)(1/0) (0/0) p(/)(11/00)(1jip bajp bappppp bapppppp bapppppp bapp根據(jù)信道的無記憶特性，可以求出二次擴展信道的傳遞概率，i為2/0) (1/0) p(/) i1,2,3,4; j1,2,3,4ijjippp ba同樣，還可求出其它例例 二次擴展信道的傳遞概率二次擴展信道的傳遞概率hust furong wang- information and coding theory10例例 二次擴展信道的信道矩陣二次擴展信道的信道矩陣o 從而求得二元對稱信道的二次擴展信道的信道矩陣為：22222222ppppppppppppp

8、pppppppppppphust furong wang- information and coding theory11(/)ijjipp ba100a 201a 310a 411a 100b201b310b411bnxny例例 二元對稱信道的二次擴展信道二元對稱信道的二次擴展信道o 二元對稱信道的二次擴展信道如下圖所示：hust furong wang- information and coding theory12n次擴展信道的平均互信息次擴展信道的平均互信息,( ;)()(/)(;)()(/)(/)()log( )(/)()log ()1,2,.,; j1,2,.,nnnnnnnnnn

9、nnijijxyijiijxyjnnnih xh xyi xyh yh yxp abp abp ap bap abp bnmx y根據(jù)平均互信息的定義，可以求出 次擴展信道的平均互信息；其中：ihust furong wang- information and coding theory13定理一定理一o 若信道的輸入和輸出分別是n長序列x和y，且，亦即信道傳遞概率為111(;);,1,2, p()/)/)/) i1,2,;1,2,kkninjiniiiiiiiiiiinnjiip yp bp yii x yxyxyiixyi x yinxaxnjmy xx yx y/或者 則存在 式中,和

10、是隨機序列 和 中第 位隨機變量,它意味著平均互信息小于或等于單個隨機變量和 的互信息之和。hust furong wang- information and coding theory14定理定理 二二o 若信道的輸入和輸出分別是n長序列x和y，且，亦即1211( ;)(;) ()() ()() i1,2, p( )nniiininiiiiiiip aii x yxyip xp xp xp xnxx yxy或者 則存在 式中，、 是隨機序列 和 中對應(yīng)的第 位隨機變量。hust furong wang- information and coding theory15n個獨立信道并聯(lián)個獨立信道

11、并聯(lián)o 根據(jù)定理一和定理二可知，當(dāng)信源和信道都是無記憶的。此時， 這相當(dāng)于n個獨立信道并聯(lián)的情況。1(;) ( ;)niiii x yix y11(;)(;)( ;)( ;)niniiiiii x yi x yiix yx y當(dāng)信道無記憶時，有當(dāng)信源無記憶時，有hust furong wang- information and coding theory16n個獨立信道并聯(lián)個獨立信道并聯(lián)o 數(shù)學(xué)模型12.nxx xx12.nyy yy11(/)p yx22(/)p yx(/)nnp yx1x2xnxny1y2yhust furong wang- information and coding t

12、heory17n次擴展信道次擴展信道12121212=(),1,2, ,( ,),1,2,= ,ninnimx xxx inxx xxy yyy inyy yyxy如果信道的輸入隨機序列中的分量取值于同一信源符號集x并具有同一種概率分布。信道輸出隨機序列其各個分量也取值于同一符號集y并具有同一種概率分布。1122n1(;)(;) (;)(; ) (; ); ) 則 于是得 ，式中 是隨機序列的長度。nniiii x yi xyi xyi x yi x yx ynn ihust furong wang- information and coding theory18n次擴展信道次擴展信道o 這樣

13、，對于離散無記憶信道的 n 次擴展信道，當(dāng)信源也是無記憶時，則有 i(x;y) = n i(x;y)o 此式表明，當(dāng)信源是無記憶時，對于無記憶的n次擴展信道，其平均互信息i(x;y)等于原來信道的平均互信息i(x;y)的 n 倍。hust furong wang- information and coding theory19離散無記憶離散無記憶n次擴展信道次擴展信道 1( )( )11( ) ; max( ;)max(;)max(;)niiinnniiip xp xiiiiip xii x yncii x ycci x yix yx y對于一般離散無記憶信道，由定理，有所以其 次擴展信道的信

14、道容量為其中， 表示在某時刻 通過離散無記憶 信道傳輸?shù)淖畲笮畔⒘俊?2(,),1,2,ninxxxcc inicncx由于輸入隨機序列是在同一信道中傳輸，所以有。亦即任何時刻 通過離散無記憶信道傳輸?shù)淖畲笮畔⒘慷枷嗤?，于是?hust furong wang- information and coding theory20n次擴展信道的信道容量次擴展信道的信道容量o cn = nc 表明，對于離散無記憶 n 次擴展信道，其信道容量等于單變量信道的信道容量的n 倍。o 只有當(dāng)輸入信源是無記憶的，同時序列中每一分量xi , i = 1,2, . ,n 的分布各自達到最佳分布時，n 次擴展信道的信

15、道容量才能達到 nc 。o 一般情況下，消息序列在離散無記憶 n 次擴展信道中傳輸時，其平均互信息量為： i(x;y) nco 對于獨立并聯(lián)信道，有 當(dāng)個輸入隨機變量之間統(tǒng)計獨立，且每個輸入隨機變量的概率分布為達到各自信道容量的最佳分布時，等式成立。121.nnnkkccccchust furong wang- information and coding theory21小結(jié)小結(jié)o 首先介紹了離散無記憶信道中各種熵、信道疑義度及平均互信息量之間的相互關(guān)系。并通過例題說明和驗證了這些關(guān)系；o 討論了離散無記憶擴展信道。分析了二元對稱信道的二次擴展信道的統(tǒng)計特性；o 對于一般離散信道，關(guān)于傳輸n

16、長隨機序列所獲得的平均互信息，給出了兩個重要的定理。hust furong wang- information and coding theory22信道的組合信道的組合o 實際中我們常常會遇到兩個或多個信道組合在一起使用的情況。例如：待發(fā)送的消息比較多時，可能要用兩個或多個信道并行地傳送，香農(nóng)稱這種信道為積信道；有時消息會依次地通過幾個信道串行地傳送，有時消息會依次地通過幾個信道串行地傳送，稱此為級聯(lián)信道；稱此為級聯(lián)信道；有時將兩個以上信道聯(lián)合起來，這類信道香農(nóng)稱為和信道。o 在研究較復(fù)雜的信道時，往往也可以將它們分解成幾個簡單的、已經(jīng)解決的信道的組合。hust furong wang- i

17、nformation and coding theory23級聯(lián)信道（串聯(lián)信道）的模型級聯(lián)信道（串聯(lián)信道）的模型o 信道i和信道ii都是離散無記憶信道12121212i,nmmlxx xyy yyy yzz zz信道輸入隨機變量為 ，它取值于輸入符號集,x；輸出隨機變量為 ，它取值于符號集,y；信道ii輸入隨機變量為 ，它取值于符號集,y；輸出隨機變量為 ，它取值于輸出符號集。x信道i信道iiyz(/ )p y x( /)p zxy(/ )1p yx( /)1p z xyhust furong wang- information and coding theory24級聯(lián)信道的傳遞概率級聯(lián)信道

18、的傳遞概率i/1,2,1,2,./1,2,1,2,1,2, .jikijp y xp yxinjmp z xyp zx yinjmklxy信道 的傳遞概率為:，；信道的傳遞概率為:，；顯然，信道ii的傳遞概率一般與前面的符號 和 均有關(guān)。x信道i信道iiyz(/ )p y x( /)p zxy(/ )1p yx( /)1p z xyhust furong wang- information and coding theory25定理定理o 級聯(lián)信道中的平均互信息滿足以下關(guān)系 (;)( ;) ; (;)(;) ( /)( / ) ; ( /)( / );i xy zi y zi xy zi x

19、zxyzp z xyp z yp z xyp z xi xy zxyzzxyi y zzyi x zzx等號成立的充要條件，對所有的 、 、 ，有表示聯(lián)合隨機變量與變量 之間的平均互信息，也就是接收到 后獲得關(guān)于聯(lián)合變量的信息量，是接收到 后獲得關(guān)于變量 的信息量;是接收到 后獲得關(guān)于變量 的信息量。( /)( / )p z xyp z yzyx該定理中，等號成立的條件是，它表示:輸出隨機變量 僅依賴于隨機變量 ， 與前面的 無關(guān)。hust furong wang- information and coding theory26數(shù)據(jù)處理定理數(shù)據(jù)處理定理zyxxyz如果輸出隨機變量 僅依賴于隨機

20、變量 ，而與前面的 無關(guān),則意味著隨機變量 、 、 構(gòu)成一個一階馬爾可夫鏈。這就是說，級聯(lián)信道的輸入和輸出變量之間構(gòu)成一個馬爾可夫鏈，并且存在下面的定理: ; ;若隨機變量 、 、 構(gòu)成一個馬爾可夫鏈，則有該定理表明：通過串聯(lián)信道的傳輸只會丟失信息，不會增加信息，至多保持原來的信息量。xyzi x zi x yi x zi y zhust furong wang- information and coding theory27數(shù)據(jù)處理定理數(shù)據(jù)處理定理 / , ,如果信道滿足（對一切）即串聯(lián)信道的總的信道矩陣等于第一級信道矩陣時，通過串聯(lián)信道傳輸后不會增加信息的損失。p x yp x zx y

21、z信道i信道iixyz( / )p y x( /)p z xy( / )1p y x ( /)1p z xy 如果信道是無損一一對應(yīng)信道時，這個條件顯然滿足。如果信道是數(shù)據(jù)處理系統(tǒng)，則表明通過數(shù)據(jù)處理后，一般只會增加信息的損失，最多保持原來獲得的信息，不可能比原來獲得的信息有所增加。hust furong wang- information and coding theory28數(shù)據(jù)處理定理（續(xù)）數(shù)據(jù)處理定理（續(xù)）|xyzyxp x yp x z若要使數(shù)據(jù)處理后獲得的關(guān)于 的平均互信息保持不變，必須滿足。故稱為數(shù)據(jù)處理定理。如果信道 是數(shù)據(jù)處理系統(tǒng)，則對接收到的數(shù)據(jù) 進行處理后，無論變量 是

22、的確定對應(yīng)關(guān)系還是概率關(guān)系，均不會減少關(guān)于 的不確定性。信道i信道iixyz( / )p y x( /)p z xy( / )1p y x ( /)1p z xy hust furong wang- information and coding theory29定理的物理意義定理的物理意義o 數(shù)據(jù)處理定理說明，在任何信息傳輸系統(tǒng)中，最后獲得的信息至多是信源所提供的信息。o 如果一旦在某一過程中丟失一些信息，以后的系統(tǒng)不管如何處理，如不觸及到丟失信息過程的輸入端，就不能再恢復(fù)已丟失的信息。o 這就是信息不增性原理，它與熱熵不減原理正好對應(yīng)。它深刻地反映了信息的物理意義。hust furong w

23、ang- information and coding theory30例例 二元對稱信道的串聯(lián)二元對稱信道的串聯(lián)o 設(shè)有二個離散二元對稱信道，其串聯(lián)信道如下圖所示。o 設(shè)第一個二元對稱信道的輸入符號的概率空間，以及兩個二元對稱信道的信道矩陣為12011;1/2 1/21xppppppp1p1p1p1ppppp000111二元對稱信道xyz二元對稱信道hust furong wang- information and coding theory31例（續(xù)）平均互信息例（續(xù)）平均互信息12222211 11(1)2 (1)2 (1)(1)(; )1( ); (;)12 (1)如果設(shè) 、 、 為馬

24、爾可夫鏈，則串聯(lián)信道的總的信道矩陣為于是，根據(jù)平均互信息的定義，可以算出 xyzppppppppppppppppi x yh pi x zhpppp phust furong wang- information and coding theory32n個二元對稱信道串聯(lián)個二元對稱信道串聯(lián)o 如果在兩個二元對稱信道串聯(lián)之后再增加一個級聯(lián)環(huán)節(jié)，可得o 依次類推，n個二元對稱信道經(jīng)串聯(lián)后，其平均互信息量如下圖所示。22(;)13(1)i x whppp(; )i x 1n 2n 3n 1.01.01.0000.20.20.20.40.40.40.60.60.60.80.80.8hust furong

25、 wang- information and coding theory33n個二元對稱信道串聯(lián)個二元對稱信道串聯(lián)1 ; ;2; ;. 當(dāng)時，串聯(lián)信道退化為一個二元對稱信道，其平均互信息量等于曲線；當(dāng)時，曲線等于曲線。對于個二元對稱信道的串聯(lián)，從圖中可以看出： 這意味著二元對稱信道經(jīng)串聯(lián)后只會增加信息的損失。當(dāng)串聯(lián)級數(shù)增加時，損失的信息越大。ni xi x yni xi x zni x yi x zi x wnhust furong wang- information and coding theory34例例o 一串聯(lián)信道如下圖所示，求總的信道矩陣。設(shè)x、y、z滿足馬氏鏈的性質(zhì)。1a2a1/

26、31/31/31/21/22/32/31b2b3b1/31/31c2c3cxyz信道i信道iihust furong wang- information and coding theory35例例 （續(xù)）總的信道矩陣（續(xù)）總的信道矩陣 |1001/3 1/3 1/302/31/31/201/201/32/3|1,2 1,2,3. 1/3 1/3 1/3 1/201/2可以得到兩個信道的信道矩陣分別為：，根據(jù)馬氏鏈的性質(zhì)，總的信道矩陣中的元素滿足，其中；，所以有y xz ykijikjjz yxy xz yz yxppp cap ba p cbijkpppp1001/3 1/3 1/302/31/31/2 1/6 1/301/32/3hust furong