1、 信道容量信道容量),(maxYXICkQ信道容量信道容量);(YXI)|()|()|(2211NNxypxypxyp),|,()|(22N1N1Nxxxyyyppxy離散無記憶離散無記憶Review達到達到C充要條件充要條件輸入概率矢量輸入概率矢量KQQQQ,10達到轉移概率為達到轉移概率為)( kjp的的DMC的容量的容量C的充要條件為的充要條件為CYkxI);(0,kQkCYkxI);(0,kQk其中，其中，iiji jpQkjpkjpYkxI)()(log)();(Review定理定理3 對于準對稱對于準對稱DMC信道信道（1）達到信道容量的最佳輸入分布為等概分布；）達到信道容量的最佳

2、輸入分布為等概分布；（2）信道容量為）信道容量為kYkXIijpKkjpkjpCJjKi；);()|(1)|(log)|(1010準對稱信道的容量準對稱信道的容量最佳輸入分布為等概分布最佳輸入分布為等概分布kYkXIijpKkjpkjpCJjKi；);()|(1)|(log)|(1010Review準對稱準對稱DMC信道信道準對稱信道容量計算公式準對稱信道容量計算公式101010)(1)(log)()(log)();(JjKiJjji jpKkjpkjpwkjpkjpYkxIC對稱對稱DMC信道信道10)(log)(logJjkjpkjpJC 例例 KSC信道信道pKpKpKpKpKpKppP

3、11111111其中其中0p1。稱稱p為錯誤概率。為錯誤概率。特別當特別當K=2時，記時，記為為BSCppppP11例例 KSC信道容量信道容量l 對稱信道對稱信道l 最佳輸入分布為等概分布最佳輸入分布為等概分布l 當輸入等概時，輸出分布當輸入等概時，輸出分布 也為等概也為等概l 信道容量信道容量)() 1log(log) 1(log) 1() 1()1log()1 (logpHKpKKpKpKppKC)(12pHCK 時：當例例 KSC信道容量信道容量pKpKpKpKpKpKppP1111111110)(log)(logJjkjpkjpJC例例 二元刪除信道容量二元刪除信道容量例：二元刪除信

4、道例：二元刪除信道輸入事件集為輸入事件集為0,1；輸出事；輸出事件集為件集為0,2,1；轉移概率矩陣；轉移概率矩陣為為qpqppqqpP1112010當當q=0時，簡化為時，簡化為BSC。當當p=0時，簡化為純刪除信道。時，簡化為純刪除信道。達到信道容量時的最佳輸入分達到信道容量時的最佳輸入分布為等概分布。布為等概分布。信道容量是轉移概率矩陣任何信道容量是轉移概率矩陣任何一行所對應的半平均互信息量。一行所對應的半平均互信息量。它為準對稱信道，它為準對稱信道， 達到達到C的分布為等概分布，即的分布為等概分布，即2/110 QQ10)1 (2121)1 (21wqpqpwqqqw21212YXIY

5、XI; 1; 0)1 (21loglog)1 (21)1 (log)1 (qppqqqqqpqp21log)1 (log)1log()1 (qqppqpqp解：解：BSC(q=0) C=1-H(p)純刪除信道純刪除信道(p=0) C=1-q 例例 二元刪除信道容量二元刪除信道容量DMC的輸入為的輸入為X，X的所有事件為的所有事件為0, 1, , K-1；DMC的噪聲為的噪聲為Z，Z的所有事件為的所有事件為0, 1, , K-1；DMC的輸出為的輸出為Y，Y的所有事件為的所有事件為0, 1, , K-1；X與與Z相互獨立；相互獨立；Y=X+Z(modK)。例例 模模K加性噪聲信道加性噪聲信道+X

6、xZz)(xQ)(zpYzxy)(yw輸入輸出干擾求信道容量求信道容量C若記若記P(Z=z)=sz，則轉移概率矩，則轉移概率矩陣為陣為0321301221011210ssssssssssssssssKKKKKK例例 模模K加性信道容量加性信道容量顯然，模顯然，模K加性噪聲信道是對稱加性噪聲信道是對稱DMC，則信道容量為，則信道容量為)(logloglog10ZHKssKCkKkkp(y|x)=P(Y=y|X=x) =P(X+Z(modK)=y|X=x) =P(x+Z(modK)=y|X=x) =P(Z=y-x(modK)|X=x) =P(Z=y-x(modK)。假定所有輸入字母的概率假定所有輸

7、入字母的概率kQ，則，則kkjkjpQw)( 1, 1 , 0Jj由由CwkjpkjpYkxIjj)(log)();( 1, 1 , 0Kk可得可得Cwkjpkjpkjpjjjlog)()(log)(即即log )()(log)(jjjwCkjpkjpkjp 可逆矩陣信道容量可逆矩陣信道容量j令令jjwClog，得，得 jjjkjpkjpkjp)(log)()(1, 1 , 0Kk可以看成是有可以看成是有J個未知數個未知數 的線性方程組。由假設的線性方程組。由假設P是是非奇異矩陣，故必有唯一解。非奇異矩陣，故必有唯一解。j令令 j是其解，由上假設是其解，由上假設jjCCjw222又又1jjw，

8、可得，可得)2log(jjC可逆矩陣信道容量可逆矩陣信道容量jjwClog0kQ對上面得到的解進行驗證。對上面得到的解進行驗證。 特別注意特別注意可逆矩陣信道容量可逆矩陣信道容量計算計算wjCjjw2計算計算Qk求解方程組求解方程組驗證驗證0kQ 若若 即所得到的解是正確的即所得到的解是正確的否則滿足條件的最大值在邊界上，于是否則滿足條件的最大值在邊界上，于是kQ令某個令某個為為0， 再次進行試解。再次進行試解。kkjkjpQw)(可逆矩陣信道容量可逆矩陣信道容量jjjkjpkjpkjp)(log)()(1, 1 , 0Kk)2log(jjCCjjw2kkjkjpQw)(列方程組列方程組計算信

9、道容量計算信道容量驗證驗證0kQ對上面得到的解進行驗證。對上面得到的解進行驗證。 特別注意特別注意可逆矩陣信道容量可逆矩陣信道容量計算計算wjCjjw2計算計算Qk求解方程組求解方程組驗證驗證0kQ 若若 即所得到的解是正確的即所得到的解是正確的否則滿足條件的最大值在邊界上，于是否則滿足條件的最大值在邊界上，于是kQ令某個令某個為為0， 再次進行試解。再次進行試解。KJ 多解多解有時要令多個有時要令多個kQ為為0，進行試解，進行試解特別特別kkjkjpQw)(例例 題題DMC信道的轉移概率矩陣為信道的轉移概率矩陣為 2/14/104/1010000104/104/12/1P求其信道容量求其信道

10、容量C。非奇異矩陣非奇異矩陣 例例 題題2/14/104/1010000104/104/12/1P根據根據jjjkjpkjpkjp)(log)()(列方程組列方程組21log2141log4141log412141410041log4141log4121log2141412143132421得得241 032 從而從而 )2log(jjC15log例例 題題驗證驗證jjCCjw222，求得，求得1012411wwC 522322wwC再根據再根據kkjkjpQw)(，得到方程組，得到方程組101214152415241101412141432141QQQQQQQQ 可得可得 30441 QQ3

11、01132 QQ經驗證經驗證0kQ，因此結果正確，因此結果正確15log C最佳分布為最佳分布為30441 QQ301132 QQ根據根據2/14/104/1010000104/104/12/1PN次擴展信道容量次擴展信道容量NCYXIYXINnnnNN1);();(有：有：【定理定理】：DMC)()(2121NNNNXXXYYYHXYH)(log)(111111NNyyxxNNxxyypyyxxpNN NnnnXYH1)(無記憶信道無記憶信道)()(21NNYYYHYH)()(121YYHYH)(121NNYYYYH NnnYH1)(證明證明注：等號成立條件注：等號成立條件 )()()(lo

12、g)(221111NNNNxypxypxypyyxxp)(log)(1111xypyyxxpNN)()(2121NNNNXXXYYYHXYH)(log)(111111NNyyxxNNxxyypyyxxpNN NnnnXYH1)(無記憶信道無記憶信道)()(21NNYYYHYH)()(121YYHYH)(121NNYYYYH NnnYH1)(證明證明注：等號成立條件注：等號成立條件 )()()(log)(221111NNNNxypxypxypyyxxp)(log)(1111xypyyxxpNNNnnnnNNNNNXYHYHXYHYHYXI1)()()()();(NnnnYXI1);(注：當輸入字

13、母序列中各字母統計獨立時，等號成立。注：當輸入字母序列中各字母統計獨立時，等號成立。 CYXInn);(NCCYXINnNN1);(由信道容量的定義知，對于任意由信道容量的定義知，對于任意n，有，有注：若對每個注：若對每個n，輸入分布，輸入分布 可使可使 極大極大，則有，則有 ，從而等式成立。，從而等式成立。)(nxQ);(nnYXICYXInn);(DMC，有問題：對有記憶信道上式是否成立？NCYXIYXINnnnNN1);();(例：例： 模模2加性噪聲信道加性噪聲信道考慮滿足的考慮滿足的 二元對稱信道，其中二元對稱信道，其中 表示模表示模2加法運算，并且加法運算，并且假設假設 具有分布具

14、有分布 但但不一定相互獨立。假設不一定相互獨立。假設Zn與輸入與輸入Xn相互獨立，相互獨立，C=1-H(p).則有：則有：iiiZXYNCYYYXXXINNxxxpN).;.(max2121),.,(211 , 0,iiYXiZ,1)0Pr(,) 1Pr(pZpZiiniZZZ,.,21該結論的證明，用到互信息的當 （信道無記憶）時，有當 （信源無記憶）時，有當信源和信道都是無記憶時，有之間的關系：與);();(iiNNYXIYXINnnnNNYXIYXI1);();(NnnnNNYXIYXI1);();(niiixypp1)/()/(xyniixpp1)()(xNnnnNNYXIYXI1);

15、();(證明：假設信源無記憶，有因此，有NnnnNNYXIYXI1);();(Niixpp1)()(xCpHZHYHYXIiixpiixpii)(1)()(max);(max)()(NnnnxpNNxxxpYXIYXInN1)(),.,();(max);(max21NnnnNNYXIYXI1);();(NCYXINNxxxpN);(max),.,(21組合信道組合信道若信道若信道1和信道和信道2同時同時傳送信息，則組合信道的輸入集傳送信息，則組合信道的輸入集由所有的有序對由所有的有序對 組成，其中組成，其中) ,(kk1Xk2Xk 輸出集由所有的有序對輸出集由所有的有序對 組成，其中組成，其中

16、) ,(jj1Yj2 Yj) ()() (kjpkjpkkjjp轉移概率轉移概率 ，稱這樣組成的信道，稱這樣組成的信道為信道為信道1和信道和信道2的的獨立并行信道獨立并行信道或或積信道積信道。信道。信道1和信和信道道2稱作積信道的分信道。稱作積信道的分信道。信道1 kaX 1 jbY 1)( kjp積信道積信道定理定理 獨立并行信道的容量獨立并行信道的容量C為各分信道容量之和為各分信道容量之和21CCC證明：證明：);();(2121YYXXIYXI) () (log) (kkjjjjwkkjjpjjkkp) () ()(log) (kkjjjjwkjpkjpjjkkpkjjwkjpkjpYX

17、I)(log)();(11)(log) (kkjjjwkjpjjkkp22) (log) ();(kjjwkjpjkpYXI) (log) (kkjjjwkjpjjkkp );();();(22112121YXIYXIYYXXI) (log) (kkjjjjjjwwwjjkkp) (log) (jjjjjjwwwjjw0 1) ()()(logjjjjjjwwwjjwe由此得由此得12CCC特別注意特別注意) (jjwwjjw時等號成立。時等號成立。 條件下，相當于要求條件下，相當于要求) ()() (kjpkjpkkjjp) (kkQQkkQ即要求兩個分信道的輸入彼此獨立。這樣對于積信道的即

18、要求兩個分信道的輸入彼此獨立。這樣對于積信道的最佳利用是將兩個信道獨立地使用，并使每個分信道的最佳利用是將兩個信道獨立地使用，并使每個分信道的輸入分布為最佳，就能保證到達信道容量。輸入分布為最佳，就能保證到達信道容量。 推論（推論（N個獨立信道構成的并行信道）個獨立信道構成的并行信道）設每個分信道的輸入空間、輸出空間和轉移概率分設每個分信道的輸入空間、輸出空間和轉移概率分 布相應為布相應為Xn，Yn和和Pn，則合成的積信道的輸入、輸，則合成的積信道的輸入、輸出空間及轉移概率分布和容量分別為出空間及轉移概率分布和容量分別為NnnXX1NnnYY1NnnPP1和和NnnCC1【例例】DMC的的N次

19、擴展信道次擴展信道積信道積信道若任一單位時間可隨機地選用信道若任一單位時間可隨機地選用信道1或信道或信道2中的一個（中的一個（兩者不能同時選用兩者不能同時選用）。選用信道）。選用信道1的概率為的概率為p1，選用信道，選用信道2的概率為的概率為p2,且且p1+p2=1。組合信道的輸入空間為。組合信道的輸入空間為稱此組合信道為和信道，或稱作并信道。稱此組合信道為和信道，或稱作并信道。21XXX輸出空間為輸出空間為 ，轉移概率分布為，轉移概率分布為21YYY2121Y j ,Y,Xk,Xk: ) (),(jkjpkjp和信道和信道信道1 kaX 1 jbY 1)( kjp【例例】ppppP111 q

20、qqqP10012此時和信道的轉移概率矩陣為此時和信道的轉移概率矩陣為qqqqppppPPP100001000001000121)()(21)|(00)|(MJNKMNJKuvpxyp和信道的互信息為和信道的互信息為, 22,11) (log) ()(log)();(jkjkjkjkwpkjpkjpQpwpkjpkjpQpYXI, 2,1) (log) ()(log)(jkjkjkjkwkjpkjpQpwkjpkjpQp2211loglogpppp)();();(222111PHpYXIpYXI其中其中2211loglog)(ppppHP定理定理 信道信道1和信道和信道2的和信道的容量的和信道

21、的容量C滿足滿足21222CCC證明：證明：)();(max);(maxmax);(max222111,PHpYXIpYXIYXICQQPQQP)(max2211PHCpCpP)1(12pp)1log()1 (log)1 (max11112111ppppCPCpP令令epepCCdpYXdIlog)1log(loglog);(11211 0loglog2121ppCC所以所以 2211loglogpCpC解之解之 121cp222cp又又 ,則則 121 pp21222cc或或22log21cc回代回代 入關系式入關系式2211loglogpCpC)(2211PHCpCpC則則21222CCC

22、可得可得 )(loglog2211PHppppC21pp121cp222cpccp121ccp222推論（推論（N個獨立信道的和信道）個獨立信道的和信道）若各分信道的輸入、輸出空間、轉移概率和容量分別為若各分信道的輸入、輸出空間、轉移概率和容量分別為Xn，Yn和和Pn和和Cn，則和信道的信道容量為，則和信道的信道容量為NnCnC12log每個信道被利用的概率為每個信道被利用的概率為CCnnp 2和信道和信道【例例】求解信道求解信道 的容量的容量C 1000101ppppP解解和信道和信道ppppP111 12P)(11phC02C12log)(12pHC12/22)(1)(111pHpHCCp

23、121pp最佳分布最佳分布11021pQQ22pQ 若將信道若將信道1的輸出作為信道的輸出作為信道2的輸入，信道的輸入，信道1的輸入的輸入集就是組合信道的輸入集，信道集就是組合信道的輸入集，信道2的輸出集就是組的輸出集就是組合信道的輸出集。稱這樣組成的信道為級聯信道，合信道的輸出集。稱這樣組成的信道為級聯信道，又稱串行信道。又稱串行信道。信道1 kaX 1 jbY 1)( kjp 級聯信道級聯信道轉移概率轉移概率jjkjpkjpkjp)()()(將信道將信道1與信道與信道2級聯，組成級聯信道，求其信道容級聯，組成級聯信道，求其信道容量和最佳輸入分布。量和最佳輸入分布。100.250.750.80.201信道信道1信道信道2100.250.750.80.200.8BSC信道信道，C=1-H(0.2)，最佳分布為等概分布。，最佳分布為等概分布。級聯信道級聯信