信息論離散信道及其容量

1、信息論離散信道及其容量第1頁，共39頁，2022年，5月20日，1點21分，星期一通信系統(tǒng)模型信息論的研究基礎(chǔ)是通信系統(tǒng)模型。第2頁，共39頁，2022年，5月20日，1點21分，星期一4.1 信道的數(shù)學模型及其分類信道是信息傳輸?shù)耐ǖ?。由于干擾的存在，信道的輸出Y與信道的輸入X不完全相同，用條件概率p(y|x)描述。而輸入和輸出又有各自的統(tǒng)計特性，分別用 和表示。第3章介紹有記憶信源的時候用到了條件概率，現(xiàn)在又用到了條件概率，兩種情況下條件概率所表達的含義相同嗎？ 不同信源：表示前后輸出的符號之間的關(guān)聯(lián)關(guān)系信道：表示傳輸時發(fā)生錯誤的情況，或者說干擾的情況第3頁，共39頁，2022年，5月20

2、日，1點21分，星期一信道的分類根據(jù)輸入輸出事件的時間特性離散信道：GSM連續(xù)信道：有線電視、廣播根據(jù)輸入輸出個數(shù)兩端信道（單路信道）：電話多元接入信道：信道的復用廣播信道：廣播根據(jù)統(tǒng)計特性恒參信道：信道的統(tǒng)計特性不隨時間發(fā)生變化。隨參信道：信道的統(tǒng)計特性隨時間發(fā)生變化。根據(jù)記憶特性無記憶信道：信道的輸出僅與當前的輸入有關(guān)，與以前的輸入無關(guān)。有記憶信道：信道的輸出不僅與當前的輸入有關(guān)，與以前的輸入也有關(guān)系。第4頁，共39頁，2022年，5月20日，1點21分，星期一一些特殊信道無損信道：輸出可以決定輸入，即知道了信道的輸出符號，能確切判斷出它對應的輸入符號是什么。確定信道：輸出完全由輸入決定，

3、即輸入符號一旦定下來，信道的輸出是確定的。無噪信道：既是無損信道，又是確定信道。輸出能決定輸入，輸入也能決定輸出?，F(xiàn)實生活中很少存在這樣的信道。無用信道：輸入與輸出相互獨立，沒有任何關(guān)系。第5頁，共39頁，2022年，5月20日，1點21分，星期一4.2 離散無記憶信道離散信道的輸入序列為X=X1,X2,XN，其取值為x=x1,x2,xN，其中xnA=a1,a2,ar。信道的輸出序列為Y=Y1,Y2,YN，其取值為y=y1,y2,yN，其中ynB=b1,b2,bs。離散信道特性：p(y|x)=p(y1y2yN | x1x2xN)信道的數(shù)學模型：X,p(y|x),Y第6頁，共39頁，2022年，

4、5月20日，1點21分，星期一離散無記憶信道定義 若離散信道對任意N長的輸入、輸出序列有p(y|x)=p(y1y2yN | x1x2xN)= ， 則稱它為離散無記憶信道，簡稱DMC。其數(shù)學模型為：X,p(y|x),Y=X,p(yn|xn),Y無記憶的含義：信道的輸出只與此時信道的輸入有關(guān)，與以前的輸入無關(guān)。定義 對任意n和m，若離散無記憶信道還滿足P(yn=j|xn=i) = P(ym=j|xm=i) 則稱此信道為平穩(wěn)的或者恒參的。第7頁，共39頁，2022年，5月20日，1點21分，星期一無記憶離散平穩(wěn)信道中序列的轉(zhuǎn)移概率和單個符號的轉(zhuǎn)移概率的關(guān)系后面如無特殊聲明，所討論的離散無記憶信道都是

5、平穩(wěn)的。因為無記憶，所以序列的轉(zhuǎn)移概率可以表示為單個符號的轉(zhuǎn)移概率的乘積。因為平穩(wěn)，所以序列的轉(zhuǎn)移概率和符號的轉(zhuǎn)移概率都不隨時間發(fā)生變化。因此對于無記憶離散平穩(wěn)信道，只需研究單個符號的傳輸，即研究一維概率分布即可。第8頁，共39頁，2022年，5月20日，1點21分，星期一三種常見的離散信道無擾（無噪）信道輸出符號與輸入符號之間有確定的一一對應關(guān)系：yn=f(xn)，常見的情況是yn=xn，這表明傳輸沒有發(fā)生錯誤（信道上沒有干擾），發(fā)送的是什么，接收到的就是什么。無擾信道還可以表示為：有干擾無記憶信道有干擾有記憶信道 實際信道往往是既有干擾又有記憶第9頁，共39頁，2022年，5月20日，1點

6、21分，星期一4.2.2 單符號離散信道N=1，信道傳遞概率： p(y|x)=P(Y=bj|X=ai)= p(bj|ai)=pij，滿足pij0，所有的信道傳遞概率可以組成一個矩陣：信道矩陣P：第10頁，共39頁，2022年，5月20日，1點21分，星期一例 二元對稱信道簡稱為BSC二元：輸入和輸出符號集均為0,1對稱：1變成0和0變成1的概率相等。p(0|0)=p(1|1)=1-p，p(0|1)=p(1|0)=pBSC的信道矩陣：第11頁，共39頁，2022年，5月20日，1點21分，星期一例 二元刪除信道二元：輸入符號集為0,1，輸出符號集中的有效字符也為0,1。刪除：輸出符號集為0,x,

7、1，不過信道不會發(fā)生錯誤（0不可能變?yōu)?，1也不可能變?yōu)?），但是0和1都有被刪除的可能（刪除用變?yōu)閤表示）。信道矩陣：第12頁，共39頁，2022年，5月20日，1點21分，星期一例 二元對稱消失信道二元：輸入符號集為0,1，輸出符號集中的有效字符也為0,1。消失：輸出符號集為0,x,1，信道有可能發(fā)生錯誤（0可能變?yōu)?，1也可能變?yōu)?），而且0和1都消失的可能（消失用變?yōu)閤表示）。信道矩陣：第13頁，共39頁，2022年，5月20日，1點21分，星期一離散信道中常用的幾種概率先驗概率：p(ai)，PX=p(a1) p(a2) p(ar)聯(lián)合概率：p(aibj)=p(ai)p(bj|ai)=

8、p(bj)p(bj|ai)信道傳遞概率：p(bj|ai)=pij，后驗概率：p(ai|bj)輸出符號概率：PY=p(b1) p(b2) p(bs)=PXP第14頁，共39頁，2022年，5月20日，1點21分，星期一4.2.3 信道疑義度定義 稱輸入空間X對輸出空間Y的條件熵 為信道疑義度。含義：收到全部輸出符號Y以后，對輸入符號X尚存在的平均不確定性。這種不確定性是由信道干擾引起的。對無擾信道：H(X|Y)=0。H(X|Y)H(X)：收到輸出符號Y以后，總能消除一些對X的不確定性，獲得一些信息。 表示接收到符號bj后，仍然保留的關(guān)于X的平均不確定性。第15頁，共39頁，2022年，5月20日

9、，1點21分，星期一例4.2.4 二元刪除信道則由此可得第16頁，共39頁，2022年，5月20日，1點21分，星期一4.2.4 平均互信息定義 原始信源熵與信道疑義度之差稱為平均互信息。I(X;Y)=H(X)-H(X|Y)含義：接收到信道的輸出符號集Y之后，平均每個符號獲得的關(guān)于信道輸入符號集X的信息量。平均互信息具有非負性。第17頁，共39頁，2022年，5月20日，1點21分，星期一兩個定理定理 對于固定的信道，平均互信息I(X;Y)是信源概率分布p(x)的上凸函數(shù)。固定信道：信道傳遞概率p(y|x)不變定理 對于固定的信源分布，平均互信息I(X;Y)是信道傳遞概率p(y|x)的下凸函數(shù)

10、。固定信源：信源概率分布p(x)不變第18頁，共39頁，2022年，5月20日，1點21分，星期一平均互信息的例子例 信源： 信道：則互信息量：第19頁，共39頁，2022年，5月20日，1點21分，星期一例對信道的輸入符號集X：設(shè)面1、2、3、4朝上為事件X=0；設(shè)面5、6朝上為事件 X=1。則信源概率空間為：對信道的輸出符號集Y：設(shè)出現(xiàn)0次正面為 事件Y=0；設(shè)出現(xiàn)1次正面為事件Y=1；設(shè)出 現(xiàn)2次正面為事件Y=2。則信道矩陣為： 聯(lián)合分布為： 條件熵為：輸出符號集Y的分布：則所以：I(X;Y)=H(Y)-H(Y|X)=1.325-1.166=0.159第20頁，共39頁，2022年，5月

11、20日，1點21分，星期一4.2.5 熵、信道疑義度及平均互信息的相互關(guān)系H(X,Y)=H(X|Y)+H(Y)=H(Y|X)+H(X)I(X;Y)=H(X)-H(X|Y)I(X;Y)=I(Y;X)I(X;Y)=I(Y;X)0I(X;X)=H(X)第21頁，共39頁，2022年，5月20日，1點21分，星期一4.3 離散無記憶擴展信道4.2節(jié)討論了單個符號的信道傳輸情況。實際上，一般離散信道的輸入和輸出是一序列，因此有必要研究擴展信道。N次擴展信道與單符號信道之間的關(guān)系，類似于N次擴展信源與單符號信源之間的關(guān)系。N次擴展信道中，輸入變量和輸出變量均為N維的： X=X1,X2,XN，Y=Y1,Y2

12、,YN，輸入序列共有rN個，輸出序列共有sN個，輸入和輸出序列分別記為k和h。N次擴展信道的數(shù)學模型為第22頁，共39頁，2022年，5月20日，1點21分，星期一例 二元無記憶對稱信道的二次擴展信道。二元對稱信道二次擴展信道的輸入和輸出：N=2,r=2,s=2，則rN=4,sN=4，輸入、輸出符號集00,01,10,11擴展信道的傳遞概率：信道矩陣為：擴展信道的平均互信息：I(X;Y)=I(XN;YN)第23頁，共39頁，2022年，5月20日，1點21分，星期一4.3.2 定理定理 若信道的輸入和輸出分別是N長序列X和Y，且信道是無記憶的，則：I(X;Y)I(Xi;Yi)定理 若信道的輸入

13、和輸出分別是N長序列X和Y，且信源是無記憶的，則：I(X;Y)I(Xi;Yi)當信源和信道都是無記憶的，此時I(X;Y)=I(Xi;Yi)當信道輸入序列的每一個符號來自同一個符號集A，信道輸出序列的每一個符號來自同一個符號集B，則I(Xi;Yi)=NI(X;Y)，即I(X;Y)=NI(X;Y)來自同一符號集：00,01,10,11，每一序列的兩個符號均來自0,1 來自不同符號集：a1,a2,b1,b2，每一序列的第一個符號來自a,b，第二個符號來自1,2第24頁，共39頁，2022年，5月20日，1點21分，星期一4.4 信道的組合組合方式 并行：積信道 串行：級聯(lián)信道 例如：Internet

14、 例如：GSM重點介紹級聯(lián)信道（串聯(lián)信道）第25頁，共39頁，2022年，5月20日，1點21分，星期一假設(shè)串聯(lián)的兩個信道為信道I和信道II，信道I的傳遞概率為p(y|x)，信道II的傳遞概率為p(z|xy)。定理 若隨機變量X,Y,Z構(gòu)成一個馬爾可夫鏈（p(z|xy)=p(z|y)），則有I(X;Z)I(X;Y) I(X;Z)I(Y;Z)定理叫做數(shù)據(jù)處理定理，它的含義是通過串聯(lián)信道的傳輸，只會丟失信息，不會增加信息，至多保持原來的消息量。這是信息不增性原理。信道Ip(y|x)信道IIp(z|xy)XYZ第26頁，共39頁，2022年，5月20日，1點21分，星期一例4.4.1 兩個二元對稱信

15、道串聯(lián)一個馬爾可夫鏈，則串聯(lián)信道總的信道矩陣為則 I(X;Y)=1-H(p) I(X;Z)=1-H(2p(1-p)從圖中能夠看出 I(X;Z)I(X;Y)第27頁，共39頁，2022年，5月20日，1點21分，星期一例信道I和信道II的信道矩陣分別為X,Y,Z構(gòu)成一個馬爾可夫鏈，則第28頁，共39頁，2022年，5月20日，1點21分，星期一4.5 信道容量定義 信道容量定義為平均互信息的最大值：C=maxp(x)I(X;Y)由定理知，I(X;Y)是p(x)的上凸函數(shù)，稱使I(X;Y)取最大值的p(x)為最佳輸入分布。由I(X;Y)的定義式可知， I(X;Y)是由信道特性p(y|x)和信源特性

16、p(x)共同決定的，但是容量C已對所有可能的p(x)取最大值，因此容量C僅與信道特性p(y|x)有關(guān)，也就是說，容量C是信道的固有特性，與信源無關(guān)。第29頁，共39頁，2022年，5月20日，1點21分，星期一信息傳輸率信道的信息傳輸率R定義為平均互信息：R=I(X;Y)其含義是：平均每個符號所能傳送的信息量。研究信道的核心問題是求出信道容量C，以及達到信道容量C的信源分布p(x)（最佳輸入分布）。第30頁，共39頁，2022年，5月20日，1點21分，星期一4.5.2 特殊信道的信道容量無損信道：logr確定信道：logs無噪信道：logr =logs第31頁，共39頁，2022年，5月20

17、日，1點21分，星期一4.5.2.1 無損信道一個輸入對應多個互不 相交的輸出，即信道矩 陣的每一列只有一個非 零元素。由于知道輸出之后，必然能夠確定其對應的輸入是什么，因此信道疑義度H(X|Y)=0。則I(X;Y)=H(X)-H(X|Y)=H(X)因此信道容量C=maxp(x)I(X;Y)=maxp(x)H(X)=logr第32頁，共39頁，2022年，5月20日，1點21分，星期一4.5.2.2 確定信道一個輸出對應多個互不相交 的輸入，即信道矩陣的每一行 只有一個“1”，其余元素均為0。由于知道輸出之后，必然能夠確定其對應的輸入是什么，因此噪聲熵H(Y|X)=0。則I(X;Y)=H(Y)

18、-H(Y|X)=H(Y)因此信道容量C=maxp(x)I(X;Y)=maxp(x)H(Y)=logs第33頁，共39頁，2022年，5月20日，1點21分，星期一4.5.2.3 無噪信道輸出與輸入是一一對應關(guān)系， 即信道矩陣為單位矩陣。因此信道疑義度H(X|Y)=0，噪聲熵H(Y|X)=0。則I(X;Y) )=H(X)-H(X|Y)=H(X) =H(Y)-H(Y|X)=H(Y)因此信道容量C=maxp(x)I(X;Y) )=maxp(x)H(X)=logr=maxp(x)H(Y)=logs第34頁，共39頁，2022年，5月20日，1點21分，星期一4.5.3 對稱信道定義 信道矩陣的每一行都是其他行的不同排列，則稱此類信道為輸入對稱信道。定義 信道矩陣的每一列都是其他列的不同排列，則稱此類信道為輸出對稱信道。定義 信道矩陣的每一行（列）都是其他行（列）的不同排列，則稱此類信道為對稱信道。第35頁，共39