第三章 信道容量

1、第第1章：概述章：概述第第2章：信源熵章：信源熵第第3 3章：信道容量章：信道容量第第4章：信息率失真函數(shù)章：信息率失真函數(shù)第第5章：信源編碼章：信源編碼第第6章：信道編碼章：信道編碼第第7 7章：密碼體制的安全性測(cè)度章：密碼體制的安全性測(cè)度3.1 單符號(hào)離散信道的數(shù)學(xué)模型單符號(hào)離散信道的數(shù)學(xué)模型3.2 單單符號(hào)離散信道的信道容量符號(hào)離散信道的信道容量3.3 多多符號(hào)離散信道的信道容量符號(hào)離散信道的信道容量3.4 網(wǎng)絡(luò)信息理論網(wǎng)絡(luò)信息理論3.5 連續(xù)信道連續(xù)信道3.6 信道編碼定理信道編碼定理3.1 單符號(hào)離散信道的數(shù)學(xué)模型單符號(hào)離散信道的數(shù)學(xué)模型P(Y/X)xY信道的數(shù)學(xué)模型：信道的數(shù)學(xué)模型

2、： X P(Y/X) Y信道的分類信道的分類無(wú)干擾無(wú)干擾信道信道有干擾有干擾信道信道信道的分類信道的分類有記憶有記憶信道信道無(wú)記憶無(wú)記憶信道信道信道的分類信道的分類單符號(hào)單符號(hào) 信道信道多符號(hào)多符號(hào)信道信道信道的分類信道的分類單用戶單用戶信道信道多用戶多用戶信道信道信道的分類信道的分類連續(xù)連續(xù)信道信道半離散半離散信道信道離散離散信道信道3.1 單符號(hào)離散信道的數(shù)學(xué)模型單符號(hào)離散信道的數(shù)學(xué)模型3.2 單單符號(hào)離散信道的信道容量符號(hào)離散信道的信道容量3.3 多多符號(hào)離散信道的信道容量符號(hào)離散信道的信道容量3.4 網(wǎng)絡(luò)信息理論網(wǎng)絡(luò)信息理論3.5 連續(xù)信道連續(xù)信道3.6 信道編碼定理信道編碼定理3.2

3、 單單符號(hào)離散信符號(hào)離散信道的信道容量道的信道容量信道容量的定義信道容量的定義3.2.2 幾種特殊離散信道的容量幾種特殊離散信道的容量3.2 .3 離散信道容量的一般計(jì)算方法離散信道容量的一般計(jì)算方法3.2.1 信道容量的定義信道容量的定義naaaX,21p(yi/xi)xYi=1,2,n信道轉(zhuǎn)移概率矩陣：（見(jiàn)下頁(yè)）信道轉(zhuǎn)移概率矩陣：（見(jiàn)下頁(yè)）mbbbY,21 nmnnmmabababababababababppppppppp,212222111211信道容量信道容量)()(max )()(max );(max)()()(XYHYHYXHXHYXICiiixpxpxp);(max1)(YXIt

4、Ciapt3.2 單單符號(hào)離散信符號(hào)離散信道的信道容量道的信道容量3.2.1 信道容量的定義信道容量的定義3.2 .3 離散信道容量的一般計(jì)算方法離散信道容量的一般計(jì)算方法3.2.2 幾種特殊離散信道的容量幾種特殊離散信道的容量一、離散無(wú)噪信道一、離散無(wú)噪信道1、一一對(duì)應(yīng)的無(wú)噪信道、一一對(duì)應(yīng)的無(wú)噪信道an bna1 b1a2 b21.000.0.0100.100naaaX,21nbbbY,21a1 b1a2 b2an-1 bn-1an bn00.10000.010.10.00001.000X、Y一一對(duì)應(yīng)一一對(duì)應(yīng) CmaxI(X;Y)log np(ai)a1 b1 b2 b32、具有擴(kuò)展功能的無(wú)

5、噪信道、具有擴(kuò)展功能的無(wú)噪信道a2 b4 b5 b6a3 b7 b8 31211156422278330000000000000000bbbaaabbbaaabbaapppppppp此時(shí)，此時(shí)，H(X/Y)=0，H(Y/X) 0，且且 H(X) H(Y)。此時(shí)，此時(shí)，C = max H(X) = log n p(ai)一個(gè)輸入對(duì)應(yīng)多個(gè)輸出一個(gè)輸入對(duì)應(yīng)多個(gè)輸出3、具有歸并性的無(wú)噪信道、具有歸并性的無(wú)噪信道x1 y1x2 x3 y2x4100010010001001x5 y3C = max H(Y) = log mp(ai)H(X/Y) 0，H(Y/X) = 0多個(gè)輸入變成一個(gè)輸出多個(gè)輸入變成一個(gè)

6、輸出二、強(qiáng)對(duì)稱二、強(qiáng)對(duì)稱(均勻均勻)離散信道的信道容量離散信道的信道容量pnpnpnpnppnpnpnpp1111.1.111.11n X nP：總體錯(cuò)誤概率：總體錯(cuò)誤概率naaaX,21mbbbY,21niniininjijijininjijijiHnppppnppppapnnpnpppabpabpapabpabpapXYH1log)1log()1(1log)1log()1)() 1)(1log1()1log()1 ()/(log)/()()/(log)/()()/(napi1)(相應(yīng)的相應(yīng)的ninapapapHnHYHXYHYHYXICiiiilog )(max )/()(max );(m

7、ax)()()(二進(jìn)制均勻信道容量二進(jìn)制均勻信道容量 C1H(p),其中 H(p)=-(1-p)log(1-p)+plogp)二進(jìn)制均勻信道容量曲線二進(jìn)制均勻信道容量曲線三、對(duì)稱離散信道的信道容量三、對(duì)稱離散信道的信道容量矩陣中的每行都矩陣中的每行都 是集合是集合P = p1, p2, , pn中的諸元素的不同排列，稱中的諸元素的不同排列，稱矩陣的行是可排列的。矩陣的行是可排列的。 矩陣中的每列都是集合矩陣中的每列都是集合Q = q1, q2, ,qm中的諸元素的不同排列，稱中的諸元素的不同排列，稱矩陣的列是可排列的。矩陣的列是可排列的。如果矩陣的行和列都是可排列的，如果矩陣的行和列都是可排列

8、的，稱矩陣是可排列的。稱矩陣是可排列的。如果一個(gè)信道矩陣具有可排列性，如果一個(gè)信道矩陣具有可排列性，則它所表示的信道稱為則它所表示的信道稱為對(duì)稱信道中，當(dāng)對(duì)稱信道中，當(dāng)nmnmnm，Q Q是是P P的子集；當(dāng)?shù)淖蛹?；?dāng)n=mn=m時(shí)，時(shí)，P=QP=Q。對(duì)稱信道對(duì)稱信道練習(xí)：判斷下列矩陣表示的信道是否是對(duì)練習(xí)：判斷下列矩陣表示的信道是否是對(duì) 稱信道稱信道 61316131616131313p 40.7 0.2 0.10.1 0.2 0.7p 31316161616131311p3121612161316131212pnapi1)(相應(yīng)的相應(yīng)的minimjijijinimjijijiHabpabp

9、apabpabpapXYH )/(log)/()( )/(log)/()()/(1111mimiapHmHYHCilog)(max)(強(qiáng)對(duì)稱信道與對(duì)稱信道強(qiáng)對(duì)稱信道與對(duì)稱信道比較比較： 強(qiáng)對(duì)稱強(qiáng)對(duì)稱 對(duì)稱對(duì)稱 n=m n與與m未必相等未必相等 矩陣對(duì)稱矩陣對(duì)稱 矩陣未必對(duì)稱矩陣未必對(duì)稱 P=Q P與與Q未必相等未必相等行之和，列之和均行之和，列之和均為為1行之和為行之和為1四、準(zhǔn)對(duì)稱信道離散信道的信道容量四、準(zhǔn)對(duì)稱信道離散信道的信道容量若信道矩陣的行是可排列的，但列不可若信道矩陣的行是可排列的，但列不可排列，如果把列分成若干個(gè)不相交的子集，排列，如果把列分成若干個(gè)不相交的子集，且由且由n n行

10、和各子集的諸列構(gòu)成的各個(gè)子矩陣行和各子集的諸列構(gòu)成的各個(gè)子矩陣都是可排列的，則稱相應(yīng)的信道為準(zhǔn)對(duì)稱都是可排列的，則稱相應(yīng)的信道為準(zhǔn)對(duì)稱信道。例如下面的矩陣：信道。例如下面的矩陣：8181214181814121miHXYH)/()(max)(miapHYHCi假設(shè)此時(shí)將矩陣的列分為假設(shè)此時(shí)將矩陣的列分為S S個(gè)子集，每個(gè)子集，每個(gè)子集的元素個(gè)數(shù)分別是個(gè)子集的元素個(gè)數(shù)分別是m m1 1，m m2 2，m ms s。ssmjjsjsmjjjmjjjbPbPbPbPbPbPYH)(log)(.)(log)()(log)()(11113.2 單單符號(hào)離散符號(hào)離散信道信道3.2.1 信道容量的定義信道容

11、量的定義3.2.2 幾種特殊離散信道的容量幾種特殊離散信道的容量3.2.3 3.2.3 離散信道容量的一般計(jì)算方法離散信道容量的一般計(jì)算方法 對(duì)一般離散信道而言，求信道容量，就是在固定信對(duì)一般離散信道而言，求信道容量，就是在固定信道的條件下，對(duì)所有可能的輸入概率分布道的條件下，對(duì)所有可能的輸入概率分布p(xi)，求平，求平均互信息的極大值。采用拉各朗日乘子法來(lái)計(jì)算。均互信息的極大值。采用拉各朗日乘子法來(lái)計(jì)算。niiaPYXI1)();(設(shè):,0)(則有令iaP()() (/)njijiip bp ap ba()(/)()jjiidp bp badp aexxloglnlognimjniiiji

12、jimjjjiapabpabpapbpbpap11111)()/(log)/()()(log)()( / )log ( )( / )log( )( / )log ( / )0mjijjijimjijijp b ap bp b aep ap b ap b a11(/)log (/)(/)log ( )log0mmjijijijjjp b ap b ap b ap be11(/)log(/)(/)log()logmjijijmjijjp bap bap bap be (1)兩邊乘兩邊乘p(ai)，并求和，則有：，并求和，則有：2112112() ()log()() ()log()lognmijij

13、iijnmijijijp a p bap bap a p bap be2(; )logI X Ye2logCe(2)將（將（2 2）代入（）代入（1 1），則有：），則有：(/)log(/)(/)log()(/)log()mjijijmjijjmjijjp bap bap bap bCp bap bC（3）log()jjp bC令（4）(/)log (/)(/)mjijijmjjijp bap bap ba則（則（3）變?yōu)椋海┳優(yōu)椋?22(4)log()()2122logjjjmjjjjmmCjjjmCjp bCp bC由求出（5） （6）（7）1(5)()2()() (/)()jCjnjij

14、iiip bp bp ap bap a由求出由求出（8）（9）并驗(yàn)證。求由求由求由求由)()9(.4);()8(.3;)7(.2;)4(.1ijjaPbPC：信道矩陣如下，求：信道矩陣如下，求C C。101121221(1)log(1) log(1)loglog(1)1log(1) 0log01log121210111121 (1)log2log2mjjC 111()2()2211(1)jCjCCp bp b 232111()1()(1)1(1)p bp b )()()()()( 2121111abpapabpapbp42121222( )( ) ( / )( ) ( /)p bp a p b

15、 ap a p b a11222()()()()(1) ()p bp ap ap bp a11111121()1(1)()1(1)p ap a 100)(),(21apap3.1 單符號(hào)離散信道的數(shù)學(xué)模型單符號(hào)離散信道的數(shù)學(xué)模型3.2 單單符號(hào)離散信道的信道容量符號(hào)離散信道的信道容量3.3 多多符號(hào)離散信道的信道容量符號(hào)離散信道的信道容量3.4 網(wǎng)絡(luò)信息理論網(wǎng)絡(luò)信息理論3.5 連續(xù)信道連續(xù)信道3.6 信道編碼定理信道編碼定理3.3 多多符號(hào)離散信符號(hào)離散信道的信道容量道的信道容量3.3.2 離散無(wú)記憶擴(kuò)展信道的信離散無(wú)記憶擴(kuò)展信道的信道容量道容量3.3.3 獨(dú)立并聯(lián)信道的信道容量獨(dú)立并聯(lián)信道的

16、信道容量多符號(hào)離散信道多符號(hào)離散信道 多符號(hào)信源通過(guò)離散信道傳輸形多符號(hào)信源通過(guò)離散信道傳輸形成多符號(hào)離散信道。成多符號(hào)離散信道。3.3.1 多符號(hào)離散信道的數(shù)學(xué)模型多符號(hào)離散信道的數(shù)學(xué)模型1212.NNXX XXYYYYYXYPX)(121 2KnKnXaaaYbbb12Niiiia aanii iN,.,2 , 1.21Nni,.,2,112Njjjjb bbNmj,.,2,1mjjjN,.,2 , 1.21YYXPX)(112111222212()().()()().().()() .()NNNNNNmmnmnnppppppppp 3.3 多多符號(hào)離散信符號(hào)離散信道的信道容量道的信道容量

17、3.3.2 離散無(wú)記憶擴(kuò)展信道的信離散無(wú)記憶擴(kuò)展信道的信道容量道容量3.3.3 獨(dú)立并聯(lián)信道的信道容量獨(dú)立并聯(lián)信道的信道容量3.3.2 離散無(wú)記憶擴(kuò)展信道的信道容量離散無(wú)記憶擴(kuò)展信道的信道容量無(wú)記憶：無(wú)記憶：YK僅與僅與XK有關(guān)有關(guān)121211221(/)(./.)(/)(/).(/)(/)NNNNNiiiP YXP Y YYX XXP YXP YXP YXP YX)/()();(XYHYHYXI1X)(11XYP)(NNXYPNXXY1YNY11121212121211112( /).(.) (.)log(.)NNNNNNNnnmmiiijjjiiiiijjjjjiiiH Y Xp a aa

18、p b bba aap b bba aa 1211111111112() ()()log()()NNNNNNNnnmmiiijijiiijjjijip a aap b ap bap b ap ba 11111112222222222() ()log()() ()log().() ()log()NNNNNNNnmijijiijnmijijiijnmijijiijp ap bap bap ap bap bap ap bap ba 11221(/)(/).(/)(/)KKNKKKH YXH YXH YXH YXNKKKYXIYXI1);();(a)NKKKNKKNKKNNKKKNNKKKXYHYHY

19、XIYHYYYHXYHYYYHXYHYHYXI111211211 )/()();()().()/().()/()();(也是無(wú)記憶的要求等號(hào)成立相互獨(dú)立，NCCYXNIYXIXaYYYKKN 2 121);();( .XX )( . 3.3 多多符號(hào)離散信符號(hào)離散信道的信道容量道的信道容量3.3.2 離散無(wú)記憶擴(kuò)展信道的信離散無(wú)記憶擴(kuò)展信道的信道容量道容量3.3.3 獨(dú)立并聯(lián)信道的信道容量獨(dú)立并聯(lián)信道的信道容量3.3.3 獨(dú)立并聯(lián)信道的信道容量 將離散無(wú)記憶信道的N次擴(kuò)展信道加以推廣，也就是令信道的輸入個(gè)輸出隨機(jī)變量序列中的各隨機(jī)變量分別取值去不同的符號(hào)集合，就構(gòu)成了獨(dú)立并聯(lián)信道，也稱獨(dú)立并列

20、信道、獨(dú)立平行信道或積信道。NkCNCk如果用表示 個(gè)獨(dú)立并聯(lián)信道的容量，表示第 個(gè)單符號(hào)離散無(wú)記憶信道的信道容量，則有121.NNNkkCCCCCkNkNXCC當(dāng) 個(gè)輸入隨機(jī)變量之間統(tǒng)計(jì)獨(dú)立，且每個(gè)輸入隨機(jī)變量的概率分布為達(dá)到各自信道容量的最佳分布時(shí)，達(dá)到最大值m ax1NNkkCC3.1 單符號(hào)離散信道的數(shù)學(xué)模型單符號(hào)離散信道的數(shù)學(xué)模型3.2 單單符號(hào)離散信道的信道容量符號(hào)離散信道的信道容量3.3 多多符號(hào)離散信道的信道容量符號(hào)離散信道的信道容量3.4 網(wǎng)絡(luò)信息理論網(wǎng)絡(luò)信息理論3.5 連續(xù)信道連續(xù)信道3.6 信道編碼定理信道編碼定理3.4 3.4 網(wǎng)絡(luò)信息理論網(wǎng)絡(luò)信息理論3.4.2 廣播信

21、道的信道容量廣播信道的信道容量3.4 .3 相關(guān)信源的邊信息和公信相關(guān)信源的邊信息和公信息息3.4.1 多址接入信道的信道容量多址接入信道的信道容量多入單出信道多入單出信道信源信源1 1信源信源2 21 u2 u編碼器編碼器1 1編碼器編碼器2 21u2u信道信道譯碼譯碼12CY1a2a二址接入信道模型1 111121.nXaaa1 221222.nXaaa121222 nYb bb11uu11RC112(;/)RI X Y X12112()()max(;/)P XP XCI X YX22RC12221()()max(;/)P XP XCI X YX121212()()max(; )P XP

22、XCI X X Y1212RRC121212max(,)C CCCCR2 C20 C1 C12C1+C2R13.4 3.4 網(wǎng)絡(luò)信息理論網(wǎng)絡(luò)信息理論3.4.2 廣播信道的信道容量廣播信道的信道容量3.4 .3 相關(guān)信源的邊信息和公信相關(guān)信源的邊信息和公信息息3.4.2 3.4.2 廣播信道的信道容量廣播信道的信道容量廣播信道廣播信道具有單個(gè)輸入和多個(gè)輸出的信道。1U信源信源1 1編碼器編碼器信道信道信源信源2 2譯碼器譯碼器2 2譯碼器譯碼器1 12U1U2UX1Y2Y圖3.4.4 單輸入雙輸出廣播信道模型退化廣播信道（串聯(lián)）編碼器編碼器信道信道1 11U2UX1Y2Y信道信道2 21()P

23、Y X21()P Y Y圖3.4.5 退化的廣播信道模型)/()()/(12121bbpxbpxbbp2121(/)(/)p bb xp bb)/()/(1212YYHXYYH21YYX、構(gòu)成馬爾可夫鏈);();(121YXIYYXI)(xp)(xp不變)()(21upup、，保持);(1YXI最大)/;(211uYXIR )/;(122uYXIR );(121YXIRR3.4 3.4 網(wǎng)絡(luò)信息理論網(wǎng)絡(luò)信息理論3.4.2 廣播信道的信道容量廣播信道的信道容量3.4 .3 相關(guān)信源的邊信息和公信相關(guān)信源的邊信息和公信息息模型13.4.3 3.4.3 相關(guān)信源的邊信息與公信息相關(guān)信源的邊信息與公信

24、息1X信信源源2X編碼器編碼器1 1編碼器編碼器2 2信道信道1 1信道信道2 2譯碼器譯碼器1 1譯碼器譯碼器2 22X1X相關(guān)信源多用戶信道)/(211XXHC )/(122XXHC )(2121XXHCCC2)(21XXH)(21XXH)/(21XXH)(1XH)(2XH)/(12XXHC1E1C1D1x1x21x)/(21XXH邊信息邊信息模型模型2RE1E2C1C2D1D2x1x21x2xE0C0w012(;)RI X X WW:公信息公信息11(/)RH XW22(/)RH XW要求要求R0盡可能小，并且在盡可能小，并且在W條件下，條件下，X1X2無(wú)關(guān)無(wú)關(guān));(min21WXXIW3.1 單符號(hào)離散信道的數(shù)學(xué)模型單符號(hào)離散信道的數(shù)學(xué)模型3.2 單