第三章 信道容量

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

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

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

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

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

6、輸出二、強(qiáng)對稱二、強(qiáng)對稱(均勻均勻)離散信道的信道容量離散信道的信道容量pnpnpnpnppnpnpnpp1111.1.111.11n X nP：總體錯誤概率：總體錯誤概率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)制均勻信道容量曲線三、對稱離散信道的信道容量三、對稱離散信道的信道容量矩陣中的每行都矩陣中的每行都 是集合是集合P = p1, p2, , pn中的諸元素的不同排列，稱中的諸元素的不同排列，稱矩陣的行是可排列的。矩陣的行是可排列的。 矩陣中的每列都是集合矩陣中的每列都是集合Q = q1, q2, ,qm中的諸元素的不同排列，稱中的諸元素的不同排列，稱矩陣的列是可排列的。矩陣的列是可排列的。如果矩陣的行和列都是可排列的，如果矩陣的行和列都是可排列

8、的，稱矩陣是可排列的。稱矩陣是可排列的。如果一個信道矩陣具有可排列性，如果一個信道矩陣具有可排列性，則它所表示的信道稱為則它所表示的信道稱為對稱信道中，當(dāng)對稱信道中，當(dāng)nmnmnm，Q Q是是P P的子集；當(dāng)?shù)淖蛹?；?dāng)n=mn=m時，時，P=QP=Q。對稱信道對稱信道練習(xí)：判斷下列矩陣表示的信道是否是對練習(xí)：判斷下列矩陣表示的信道是否是對 稱信道稱信道 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)對稱信道與對稱信道強(qiáng)對稱信道與對稱信道比較比較： 強(qiáng)對稱強(qiáng)對稱 對稱對稱 n=m n與與m未必相等未必相等 矩陣對稱矩陣對稱 矩陣未必對稱矩陣未必對稱 P=Q P與與Q未必相等未必相等行之和，列之和均行之和，列之和均為為1行之和為行之和為1四、準(zhǔn)對稱信道離散信道的信道容量四、準(zhǔn)對稱信道離散信道的信道容量若信道矩陣的行是可排列的，但列不可若信道矩陣的行是可排列的，但列不可排列，如果把列分成若干個不相交的子集，排列，如果把列分成若干個不相交的子集，且由且由n n行

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

11、量的定義3.2.2 幾種特殊離散信道的容量幾種特殊離散信道的容量3.2.3 3.2.3 離散信道容量的一般計算方法離散信道容量的一般計算方法 對一般離散信道而言，求信道容量，就是在固定信對一般離散信道而言，求信道容量，就是在固定信道的條件下，對所有可能的輸入概率分布道的條件下，對所有可能的輸入概率分布p(xi)，求平，求平均互信息的極大值。采用拉各朗日乘子法來計算。均互信息的極大值。采用拉各朗日乘子法來計算。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）并驗證。求由求由求由求由)()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 單符號離散信道的數(shù)學(xué)模型單符號離散信道的數(shù)學(xué)模型3.2 單單符號離散信道的信道容量符號離散信道的信道容量3.3 多多符號離散信道的信道容量符號離散信道的信道容量3.4 網(wǎng)絡(luò)信息理論網(wǎng)絡(luò)信息理論3.5 連續(xù)信道連續(xù)信道3.6 信道編碼定理信道編碼定理3.3 多多符號離散信符號離散信道的信道容量道的信道容量3.3.2 離散無記憶擴(kuò)展信道的信離散無記憶擴(kuò)展信道的信道容量道容量3.3.3 獨立并聯(lián)信道的信道容量獨立并聯(lián)信道的

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

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

20、信道、獨立平行信道或積信道。NkCNCk如果用表示 個獨立并聯(lián)信道的容量，表示第 個單符號離散無記憶信道的信道容量，則有121.NNNkkCCCCCkNkNXCC當(dāng) 個輸入隨機(jī)變量之間統(tǒng)計獨立，且每個輸入隨機(jī)變量的概率分布為達(dá)到各自信道容量的最佳分布時，達(dá)到最大值m ax1NNkkCC3.1 單符號離散信道的數(shù)學(xué)模型單符號離散信道的數(shù)學(xué)模型3.2 單單符號離散信道的信道容量符號離散信道的信道容量3.3 多多符號離散信道的信道容量符號離散信道的信道容量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 廣播信道的信道容量廣播信道的信道容量廣播信道廣播信道具有單個輸入和多個輸出的信道。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無關(guān)無關(guān));(min21WXXIW3.1 單符號離散信道的數(shù)學(xué)模型單符號離散信道的數(shù)學(xué)模型3.2 單