信息論離散信道及其容量

信息論離散信道及其容量第一頁，共三十九頁，2022年，8月28日通信系統(tǒng)模型信息論的研究基礎(chǔ)是通信系統(tǒng)模型。第二頁，共三十九頁，2022年，8月28日4.1信道的數(shù)學(xué)模型及其分類信道是信息傳輸?shù)耐ǖ?。由于干擾的存在，信道的輸出Y與信道的輸入X不完全相同，用條件概率p(y|x)描述。而輸入和輸出又有各自的統(tǒng)計特性，分別用和表示。第3章介紹有記憶信源的時候用到了條件概率，現(xiàn)在又用到了條件概率，兩種情況下條件概率所表達(dá)的含義相同嗎？

不同信源：表示前后輸出的符號之間的關(guān)聯(lián)關(guān)系信道：表示傳輸時發(fā)生錯誤的情況，或者說干擾的情況第三頁，共三十九頁，2022年，8月28日信道的分類根據(jù)輸入輸出事件的時間特性離散信道：GSM連續(xù)信道：有線電視、廣播根據(jù)輸入輸出個數(shù)兩端信道（單路信道）：電話多元接入信道：信道的復(fù)用廣播信道：廣播根據(jù)統(tǒng)計特性恒參信道：信道的統(tǒng)計特性不隨時間發(fā)生變化。隨參信道：信道的統(tǒng)計特性隨時間發(fā)生變化。根據(jù)記憶特性無記憶信道：信道的輸出僅與當(dāng)前的輸入有關(guān)，與以前的輸入無關(guān)。有記憶信道：信道的輸出不僅與當(dāng)前的輸入有關(guān)，與以前的輸入也有關(guān)系。第四頁，共三十九頁，2022年，8月28日一些特殊信道無損信道：輸出可以決定輸入，即知道了信道的輸出符號，能確切判斷出它對應(yīng)的輸入符號是什么。確定信道：輸出完全由輸入決定，即輸入符號一旦定下來，信道的輸出是確定的。無噪信道：既是無損信道，又是確定信道。輸出能決定輸入，輸入也能決定輸出?，F(xiàn)實(shí)生活中很少存在這樣的信道。無用信道：輸入與輸出相互獨(dú)立，沒有任何關(guān)系。第五頁，共三十九頁，2022年，8月28日4.2離散無記憶信道離散信道的輸入序列為X={X1,X2,…,XN}，其取值為x={x1,x2,…,xN}，其中xn∈A={a1,a2,…,ar}。信道的輸出序列為Y={Y1,Y2,…,YN}，其取值為y={y1,y2,…,yN}，其中yn∈B={b1,b2,…,bs}。離散信道特性：p(y|x)=p(y1y2…yN|x1x2…xN)信道的數(shù)學(xué)模型：{X,p(y|x),Y}第六頁，共三十九頁，2022年，8月28日離散無記憶信道定義

若離散信道對任意N長的輸入、輸出序列有p(y|x)=p(y1y2…yN|x1x2…xN)=，則稱它為離散無記憶信道，簡稱DMC。其數(shù)學(xué)模型為：{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)的或者恒參的。第七頁，共三十九頁，2022年，8月28日無記憶離散平穩(wěn)信道中序列的轉(zhuǎn)移概率和單個符號的轉(zhuǎn)移概率的關(guān)系后面如無特殊聲明，所討論的離散無記憶信道都是平穩(wěn)的。因?yàn)闊o記憶，所以序列的轉(zhuǎn)移概率可以表示為單個符號的轉(zhuǎn)移概率的乘積。因?yàn)槠椒€(wěn)，所以序列的轉(zhuǎn)移概率和符號的轉(zhuǎn)移概率都不隨時間發(fā)生變化。因此對于無記憶離散平穩(wěn)信道，只需研究單個符號的傳輸，即研究一維概率分布即可。第八頁，共三十九頁，2022年，8月28日三種常見的離散信道無擾（無噪）信道輸出符號與輸入符號之間有確定的一一對應(yīng)關(guān)系：yn=f(xn)，常見的情況是yn=xn，這表明傳輸沒有發(fā)生錯誤（信道上沒有干擾），發(fā)送的是什么，接收到的就是什么。無擾信道還可以表示為：有干擾無記憶信道有干擾有記憶信道實(shí)際信道往往是既有干擾又有記憶第九頁，共三十九頁，2022年，8月28日4.2.2單符號離散信道N=1，信道傳遞概率：p(y|x)=P(Y=bj|X=ai)=p(bj|ai)=pij，滿足pij≥0，所有的信道傳遞概率可以組成一個矩陣：信道矩陣P：第十頁，共三十九頁，2022年，8月28日例

二元對稱信道簡稱為BSC二元：輸入和輸出符號集均為{0,1}對稱：1變成0和0變成1的概率相等。p(0|0)=p(1|1)=1-p，p(0|1)=p(1|0)=pBSC的信道矩陣：第十一頁，共三十九頁，2022年，8月28日例

二元刪除信道二元：輸入符號集為{0,1}，輸出符號集中的有效字符也為{0,1}。刪除：輸出符號集為{0,x,1}，不過信道不會發(fā)生錯誤（0不可能變?yōu)?，1也不可能變?yōu)?），但是0和1都有被刪除的可能（刪除用變?yōu)閤表示）。信道矩陣：第十二頁，共三十九頁，2022年，8月28日例

二元對稱消失信道二元：輸入符號集為{0,1}，輸出符號集中的有效字符也為{0,1}。消失：輸出符號集為{0,x,1}，信道有可能發(fā)生錯誤（0可能變?yōu)?，1也可能變?yōu)?），而且0和1都消失的可能（消失用變?yōu)閤表示）。信道矩陣：第十三頁，共三十九頁，2022年，8月28日離散信道中常用的幾種概率先驗(yàn)概率：p(ai)，PX=[p(a1)p(a2)…p(ar)]聯(lián)合概率：p(aibj)=p(ai)p(bj|ai)=p(bj)p(bj|ai)信道傳遞概率：p(bj|ai)=pij，后驗(yàn)概率：p(ai|bj)輸出符號概率：PY=[p(b1)p(b2)…p(bs)]=PXP第十四頁，共三十九頁，2022年，8月28日4.2.3信道疑義度定義

稱輸入空間X對輸出空間Y的條件熵為信道疑義度。含義：收到全部輸出符號Y以后，對輸入符號X尚存在的平均不確定性。這種不確定性是由信道干擾引起的。對無擾信道：H(X|Y)=0。H(X|Y)≤H(X)：收到輸出符號Y以后，總能消除一些對X的不確定性，獲得一些信息。

表示接收到符號bj后，仍然保留的關(guān)于X的平均不確定性。第十五頁，共三十九頁，2022年，8月28日例4.2.4二元刪除信道則由此可得第十六頁，共三十九頁，2022年，8月28日4.2.4平均互信息定義

原始信源熵與信道疑義度之差稱為平均互信息。I(X;Y)=H(X)-H(X|Y)含義：接收到信道的輸出符號集Y之后，平均每個符號獲得的關(guān)于信道輸入符號集X的信息量。平均互信息具有非負(fù)性。第十七頁，共三十九頁，2022年，8月28日兩個定理定理

對于固定的信道，平均互信息I(X;Y)是信源概率分布p(x)的上凸函數(shù)。固定信道：信道傳遞概率p(y|x)不變定理

對于固定的信源分布，平均互信息I(X;Y)是信道傳遞概率p(y|x)的下凸函數(shù)。固定信源：信源概率分布p(x)不變第十八頁，共三十九頁，2022年，8月28日平均互信息的例子例

信源：信道：則互信息量：第十九頁，共三十九頁，2022年，8月28日例對信道的輸入符號集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第二十頁，共三十九頁，2022年，8月28日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)第二十一頁，共三十九頁，2022年，8月28日4.3離散無記憶擴(kuò)展信道4.2節(jié)討論了單個符號的信道傳輸情況。實(shí)際上，一般離散信道的輸入和輸出是一序列，因此有必要研究擴(kuò)展信道。N次擴(kuò)展信道與單符號信道之間的關(guān)系，類似于N次擴(kuò)展信源與單符號信源之間的關(guān)系。N次擴(kuò)展信道中，輸入變量和輸出變量均為N維的：X={X1,X2,…,XN}，Y={Y1,Y2,…,YN}，輸入序列共有rN個，輸出序列共有sN個，輸入和輸出序列分別記為αk和βh。N次擴(kuò)展信道的數(shù)學(xué)模型為第二十二頁，共三十九頁，2022年，8月28日例

二元無記憶對稱信道的二次擴(kuò)展信道。二元對稱信道二次擴(kuò)展信道的輸入和輸出：N=2,r=2,s=2，則rN=4,sN=4，輸入、輸出符號集{00,01,10,11}擴(kuò)展信道的傳遞概率：信道矩陣為：擴(kuò)展信道的平均互信息：I(X;Y)=I(XN;YN)第二十三頁，共三十九頁，2022年，8月28日4.3.2定理定理

若信道的輸入和輸出分別是N長序列X和Y，且信道是無記憶的，則：I(X;Y)≤∑I(Xi;Yi)定理

若信道的輸入和輸出分別是N長序列X和Y，且信源是無記憶的，則：I(X;Y)≥∑I(Xi;Yi)當(dāng)信源和信道都是無記憶的，此時I(X;Y)=∑I(Xi;Yi)當(dāng)信道輸入序列的每一個符號來自同一個符號集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}第二十四頁，共三十九頁，2022年，8月28日4.4信道的組合組合方式并行：積信道串行：級聯(lián)信道例如：Internet例如：GSM重點(diǎn)介紹級聯(lián)信道（串聯(lián)信道）第二十五頁，共三十九頁，2022年，8月28日假設(shè)串聯(lián)的兩個信道為信道I和信道II，信道I的傳遞概率為p(y|x)，信道II的傳遞概率為p(z|xy)。定理

若隨機(jī)變量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第二十六頁，共三十九頁，2022年，8月28日例4.4.1兩個二元對稱信道串聯(lián)一個馬爾可夫鏈，則串聯(lián)信道總的信道矩陣為則I(X;Y)=1-H(p)I(X;Z)=1-H(2p(1-p))從圖中能夠看出

I(X;Z)≤I(X;Y)第二十七頁，共三十九頁，2022年，8月28日例信道I和信道II的信道矩陣分別為X,Y,Z構(gòu)成一個馬爾可夫鏈，則第二十八頁，共三十九頁，2022年，8月28日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)和信源特性p(x)共同決定的，但是容量C已對所有可能的p(x)取最大值，因此容量C僅與信道特性p(y|x)有關(guān)，也就是說，容量C是信道的固有特性，與信源無關(guān)。第二十九頁，共三十九頁，2022年，8月28日信息傳輸率信道的信息傳輸率R定義為平均互信息：R=I(X;Y)其含義是：平均每個符號所能傳送的信息量。研究信道的核心問題是求出信道容量C，以及達(dá)到信道容量C的信源分布p(x)（最佳輸入分布）。第三十頁，共三十九頁，2022年，8月28日4.5.2特殊信道的信道容量無損信道：logr確定信道：logs無噪信道：logr=logs第三十一頁，共三十九頁，2022年，8月28日4.5.2.1無損信道一個輸入對應(yīng)多個互不相交的輸出，即信道矩陣的每一列只有一個非零元素。由于知道輸出之后，必然能夠確定其對應(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第三十二頁，共三十九頁，2022年，8月28日4.5.2.2確定信道一個輸出對應(yīng)多個互不相交的輸入，即信道矩陣的每一行只有一個“1”，其余元素均為0。由于知道輸出之后，必然能夠確定其對應(yīng)的輸入是什么，因此噪聲熵H(Y|X)=0。則I(X;Y)=H(Y)-H(Y|X)=H(Y)因此信道容量C=maxp(x){I(X;Y)}=maxp(x){H(Y)}=logs第三十三頁，共三十九頁，2022年，8月28日4.5.2.3無噪信道輸出與輸入是一一對應(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第三十四頁，共三十九頁，2022年，8月28日4.5.3對稱信道定義

信道矩陣的每一行都是其他行的不同排列，則稱此類信道為輸入對稱信道。定義

信道矩陣的每一列都是其他列的不同排列，則稱此類信道為輸出對稱信道。定義

信道矩陣的