信息論離散信道及其容量

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

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

3、即輸入符號(hào)一旦定下來(lái)，信道的輸出是確定的。無(wú)噪信道：既是無(wú)損信道，又是確定信道。輸出能決定輸入，輸入也能決定輸出?，F(xiàn)實(shí)生活中很少存在這樣的信道。無(wú)用信道：輸入與輸出相互獨(dú)立，沒(méi)有任何關(guān)系。第5頁(yè)，共39頁(yè)，2022年，5月20日，1點(diǎn)21分，星期一4.2 離散無(wú)記憶信道離散信道的輸入序列為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ù)學(xué)模型：X,p(y|x),Y第6頁(yè)，共39頁(yè)，2022年，

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

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

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

7、1，不過(guò)信道不會(huì)發(fā)生錯(cuò)誤（0不可能變?yōu)?，1也不可能變?yōu)?），但是0和1都有被刪除的可能（刪除用變?yōu)閤表示）。信道矩陣：第12頁(yè)，共39頁(yè)，2022年，5月20日，1點(diǎn)21分，星期一例 二元對(duì)稱消失信道二元：輸入符號(hào)集為0,1，輸出符號(hào)集中的有效字符也為0,1。消失：輸出符號(hào)集為0,x,1，信道有可能發(fā)生錯(cuò)誤（0可能變?yōu)?，1也可能變?yōu)?），而且0和1都消失的可能（消失用變?yōu)閤表示）。信道矩陣：第13頁(yè)，共39頁(yè)，2022年，5月20日，1點(diǎn)21分，星期一離散信道中常用的幾種概率先驗(yàn)概率：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，后驗(yàn)概率：p(ai|bj)輸出符號(hào)概率：PY=p(b1) p(b2) p(bs)=PXP第14頁(yè)，共39頁(yè)，2022年，5月20日，1點(diǎn)21分，星期一4.2.3 信道疑義度定義 稱輸入空間X對(duì)輸出空間Y的條件熵 為信道疑義度。含義：收到全部輸出符號(hào)Y以后，對(duì)輸入符號(hào)X尚存在的平均不確定性。這種不確定性是由信道干擾引起的。對(duì)無(wú)擾信道：H(X|Y)=0。H(X|Y)H(X)：收到輸出符號(hào)Y以后，總能消除一些對(duì)X的不確定性，獲得一些信息。 表示接收到符號(hào)bj后，仍然保留的關(guān)于X的平均不確定性。第15頁(yè)，共39頁(yè)，2022年，5月20日

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

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

11、20日，1點(diǎn)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頁(yè)，共39頁(yè)，2022年，5月20日，1點(diǎn)21分，星期一4.3 離散無(wú)記憶擴(kuò)展信道4.2節(jié)討論了單個(gè)符號(hào)的信道傳輸情況。實(shí)際上，一般離散信道的輸入和輸出是一序列，因此有必要研究擴(kuò)展信道。N次擴(kuò)展信道與單符號(hào)信道之間的關(guān)系，類似于N次擴(kuò)展信源與單符號(hào)信源之間的關(guān)系。N次擴(kuò)展信道中，輸入變量和輸出變量均為N維的： X=X1,X2,XN，Y=Y1,Y2

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

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

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

15、道串聯(lián)一個(gè)馬爾可夫鏈，則串聯(lián)信道總的信道矩陣為則 I(X;Y)=1-H(p) I(X;Z)=1-H(2p(1-p)從圖中能夠看出 I(X;Z)I(X;Y)第27頁(yè)，共39頁(yè)，2022年，5月20日，1點(diǎn)21分，星期一例信道I和信道II的信道矩陣分別為X,Y,Z構(gòu)成一個(gè)馬爾可夫鏈，則第28頁(yè)，共39頁(yè)，2022年，5月20日，1點(diǎn)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已對(duì)所有可能的p(x)取最大值，因此容量C僅與信道特性p(y|x)有關(guān)，也就是說(shuō)，容量C是信道的固有特性，與信源無(wú)關(guān)。第29頁(yè)，共39頁(yè)，2022年，5月20日，1點(diǎn)21分，星期一信息傳輸率信道的信息傳輸率R定義為平均互信息：R=I(X;Y)其含義是：平均每個(gè)符號(hào)所能傳送的信息量。研究信道的核心問(wèn)題是求出信道容量C，以及達(dá)到信道容量C的信源分布p(x)（最佳輸入分布）。第30頁(yè)，共39頁(yè)，2022年，5月20日，1點(diǎn)21分，星期一4.5.2 特殊信道的信道容量無(wú)損信道：logr確定信道：logs無(wú)噪信道：logr =logs第31頁(yè)，共39頁(yè)，2022年，5月20

17、日，1點(diǎn)21分，星期一4.5.2.1 無(wú)損信道一個(gè)輸入對(duì)應(yīng)多個(gè)互不 相交的輸出，即信道矩 陣的每一列只有一個(gè)非 零元素。由于知道輸出之后，必然能夠確定其對(duì)應(yīng)的輸入是什么，因此信道疑義度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頁(yè)，共39頁(yè)，2022年，5月20日，1點(diǎn)21分，星期一4.5.2.2 確定信道一個(gè)輸出對(duì)應(yīng)多個(gè)互不相交 的輸入，即信道矩陣的每一行 只有一個(gè)“1”，其余元素均為0。由于知道輸出之后，必然能夠確定其對(duì)應(yīng)的輸入是什么，因此噪聲熵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頁(yè)，共39頁(yè)，2022年，5月20日，1點(diǎn)21分，星期一4.5.2.3 無(wú)噪信道輸出與輸入是一一對(duì)應(yīng)關(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頁(yè)，共39頁(yè)，2022年，5月20日，1點(diǎn)21分，星期一4.5.3 對(duì)稱信道定義 信道矩陣的每一行都是其他行的不同排列，則稱此類信道為輸入對(duì)稱信道。定義 信道矩陣的每一列都是其他列的不同排列，則稱此類信道為輸出對(duì)稱信道。定義 信道矩陣的每一行（列）都是其他行（列）的不同排列，則稱此類信道為對(duì)稱信道。第35頁(yè)，共39