第11講——離散無(wú)記憶信道的容量

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

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

3、11111111其中其中0p1。稱稱p為錯(cuò)誤概率。為錯(cuò)誤概率。特別當(dāng)特別當(dāng)K=2時(shí)，記時(shí)，記為為BSCppppP11例例 KSC信道容量信道容量l 對(duì)稱信道對(duì)稱信道l 最佳輸入分布為等概分布最佳輸入分布為等概分布l 當(dāng)輸入等概時(shí)，輸出分布當(dāng)輸入等概時(shí)，輸出分布 也為等概也為等概l 信道容量信道容量)() 1log(log) 1(log) 1() 1()1log()1 (logpHKpKKpKpKppKC)(12pHCK 時(shí)：當(dāng)例例 KSC信道容量信道容量pKpKpKpKpKpKppP1111111110)(log)(logJjkjpkjpJC例例 二元?jiǎng)h除信道容量二元?jiǎng)h除信道容量例：二元?jiǎng)h除信

4、道例：二元?jiǎng)h除信道輸入事件集為輸入事件集為0,1；輸出事；輸出事件集為件集為0,2,1；轉(zhuǎn)移概率矩陣；轉(zhuǎn)移概率矩陣為為qpqppqqpP1112010當(dāng)當(dāng)q=0時(shí)，簡(jiǎn)化為時(shí)，簡(jiǎn)化為BSC。當(dāng)當(dāng)p=0時(shí)，簡(jiǎn)化為純刪除信道。時(shí)，簡(jiǎn)化為純刪除信道。達(dá)到信道容量時(shí)的最佳輸入分達(dá)到信道容量時(shí)的最佳輸入分布為等概分布。布為等概分布。信道容量是轉(zhuǎn)移概率矩陣任何信道容量是轉(zhuǎn)移概率矩陣任何一行所對(duì)應(yīng)的半平均互信息量。一行所對(duì)應(yīng)的半平均互信息量。它為準(zhǔn)對(duì)稱信道，它為準(zhǔn)對(duì)稱信道， 達(dá)到達(dá)到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 例例 二元?jiǎng)h除信道容量二元?jiǎng)h除信道容量DMC的輸入為的輸入為X，X的所有事件為的所有事件為0, 1, , K-1；DMC的噪聲為的噪聲為Z，Z的所有事件為的所有事件為0, 1, , K-1；DMC的輸出為的輸出為Y，Y的所有事件為的所有事件為0, 1, , K-1；X與與Z相互獨(dú)立；相互獨(dú)立；Y=X+Z(modK)。例例 模模K加性噪聲信道加性噪聲信道+X

6、xZz)(xQ)(zpYzxy)(yw輸入輸出干擾求信道容量求信道容量C若記若記P(Z=z)=sz，則轉(zhuǎn)移概率矩，則轉(zhuǎn)移概率矩陣為陣為0321301221011210ssssssssssssssssKKKKKK例例 模模K加性信道容量加性信道容量顯然，模顯然，模K加性噪聲信道是對(duì)稱加性噪聲信道是對(duì)稱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個(gè)未知數(shù)個(gè)未知數(shù) 的線性方程組。由假設(shè)的線性方程組。由假設(shè)P是是非奇異矩陣，故必有唯一解。非奇異矩陣，故必有唯一解。j令令 j是其解，由上假設(shè)是其解，由上假設(shè)jjCCjw222又又1jjw，

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

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

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

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

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

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

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

15、();(證明：假設(shè)信源無(wú)記憶，有因此，有NnnnNNYXIYXI1);();(Niixpp1)()(xCpHZHYHYXIiixpiixpii)(1)()(max);(max)()(NnnnxpNNxxxpYXIYXInN1)(),.,();(max);(max21NnnnNNYXIYXI1);();(NCYXINNxxxpN);(max),.,(21組合信道組合信道若信道若信道1和信道和信道2同時(shí)同時(shí)傳送信息，則組合信道的輸入集傳送信息，則組合信道的輸入集由所有的有序?qū)τ伤械挠行驅(qū)?組成，其中組成，其中) ,(kk1Xk2Xk 輸出集由所有的有序?qū)敵黾伤械挠行驅(qū)?組成，其中組成，其中

16、) ,(jj1Yj2 Yj) ()() (kjpkjpkkjjp轉(zhuǎn)移概率轉(zhuǎn)移概率 ，稱這樣組成的信道，稱這樣組成的信道為信道為信道1和信道和信道2的的獨(dú)立并行信道獨(dú)立并行信道或或積信道積信道。信道。信道1和信和信道道2稱作積信道的分信道。稱作積信道的分信道。信道1 kaX 1 jbY 1)( kjp積信道積信道定理定理 獨(dú)立并行信道的容量獨(dú)立并行信道的容量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時(shí)等號(hào)成立。時(shí)等號(hào)成立。 條件下，相當(dāng)于要求條件下，相當(dāng)于要求) ()() (kjpkjpkkjjp) (kkQQkkQ即要求兩個(gè)分信道的輸入彼此獨(dú)立。這樣對(duì)于積信道的即

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

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

20、qqqP10012此時(shí)和信道的轉(zhuǎn)移概率矩陣為此時(shí)和信道的轉(zhuǎn)移概率矩陣為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回代回代 入關(guān)系式入關(guān)系式2211loglogpCpC)(2211PHCpCpC則則21222CCC

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

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