信息論離散信道及其容量

信息論離散信道及其容量第1頁，課件共39頁，創(chuàng)作于2023年2月通信系統(tǒng)模型信息論的研究基礎(chǔ)是通信系統(tǒng)模型。第2頁，課件共39頁，創(chuàng)作于2023年2月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ò)誤的情況，或者說干擾的情況第3頁，課件共39頁，創(chuàng)作于2023年2月信道的分類根據(jù)輸入輸出事件的時(shí)間特性離散信道：GSM連續(xù)信道：有線電視、廣播根據(jù)輸入輸出個(gè)數(shù)兩端信道（單路信道）：電話多元接入信道：信道的復(fù)用廣播信道：廣播根據(jù)統(tǒng)計(jì)特性恒參信道：信道的統(tǒng)計(jì)特性不隨時(shí)間發(fā)生變化。隨參信道：信道的統(tǒng)計(jì)特性隨時(shí)間發(fā)生變化。根據(jù)記憶特性無記憶信道：信道的輸出僅與當(dāng)前的輸入有關(guān)，與以前的輸入無關(guān)。有記憶信道：信道的輸出不僅與當(dāng)前的輸入有關(guān)，與以前的輸入也有關(guān)系。第4頁，課件共39頁，創(chuàng)作于2023年2月一些特殊信道無損信道：輸出可以決定輸入，即知道了信道的輸出符號(hào)，能確切判斷出它對(duì)應(yīng)的輸入符號(hào)是什么。確定信道：輸出完全由輸入決定，即輸入符號(hào)一旦定下來，信道的輸出是確定的。無噪信道：既是無損信道，又是確定信道。輸出能決定輸入，輸入也能決定輸出?，F(xiàn)實(shí)生活中很少存在這樣的信道。無用信道：輸入與輸出相互獨(dú)立，沒有任何關(guān)系。第5頁，課件共39頁，創(chuàng)作于2023年2月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}第6頁，課件共39頁，創(chuàng)作于2023年2月離散無記憶信道定義4.2.1

若離散信道對(duì)任意N長的輸入、輸出序列有p(y|x)=p(y1y2…yN|x1x2…xN)=，則稱它為離散無記憶信道，簡稱DMC。其數(shù)學(xué)模型為：{X,p(y|x),Y}={X,p(yn|xn),Y}無記憶的含義：信道的輸出只與此時(shí)信道的輸入有關(guān)，與以前的輸入無關(guān)。定義4.2.2

對(duì)任意n和m，若離散無記憶信道還滿足P(yn=j|xn=i)=P(ym=j|xm=i)

則稱此信道為平穩(wěn)的或者恒參的。第7頁，課件共39頁，創(chuàng)作于2023年2月無記憶離散平穩(wěn)信道中序列的轉(zhuǎn)移概率和單個(gè)符號(hào)的轉(zhuǎn)移概率的關(guān)系后面如無特殊聲明，所討論的離散無記憶信道都是平穩(wěn)的。因?yàn)闊o記憶，所以序列的轉(zhuǎn)移概率可以表示為單個(gè)符號(hào)的轉(zhuǎn)移概率的乘積。因?yàn)槠椒€(wěn)，所以序列的轉(zhuǎn)移概率和符號(hào)的轉(zhuǎn)移概率都不隨時(shí)間發(fā)生變化。因此對(duì)于無記憶離散平穩(wěn)信道，只需研究單個(gè)符號(hào)的傳輸，即研究一維概率分布即可。第8頁，課件共39頁，創(chuàng)作于2023年2月三種常見的離散信道無擾（無噪）信道輸出符號(hào)與輸入符號(hào)之間有確定的一一對(duì)應(yīng)關(guān)系：yn=f(xn)，常見的情況是yn=xn，這表明傳輸沒有發(fā)生錯(cuò)誤（信道上沒有干擾），發(fā)送的是什么，接收到的就是什么。無擾信道還可以表示為：有干擾無記憶信道有干擾有記憶信道實(shí)際信道往往是既有干擾又有記憶第9頁，課件共39頁，創(chuàng)作于2023年2月4.2.2單符號(hào)離散信道N=1，信道傳遞概率：p(y|x)=P(Y=bj|X=ai)=p(bj|ai)=pij，滿足pij≥0，所有的信道傳遞概率可以組成一個(gè)矩陣：信道矩陣P：第10頁，課件共39頁，創(chuàng)作于2023年2月例4.2.1

二元對(duì)稱信道簡稱為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頁，課件共39頁，創(chuàng)作于2023年2月例4.2.2

二元?jiǎng)h除信道二元：輸入符號(hào)集為{0,1}，輸出符號(hào)集中的有效字符也為{0,1}。刪除：輸出符號(hào)集為{0,x,1}，不過信道不會(huì)發(fā)生錯(cuò)誤（0不可能變?yōu)?，1也不可能變?yōu)?），但是0和1都有被刪除的可能（刪除用變?yōu)閤表示）。信道矩陣：第12頁，課件共39頁，創(chuàng)作于2023年2月例4.2.3

二元對(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頁，課件共39頁，創(chuàng)作于2023年2月離散信道中常用的幾種概率先驗(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)輸出符號(hào)概率：PY=[p(b1)p(b2)…p(bs)]=PXP第14頁，課件共39頁，創(chuàng)作于2023年2月4.2.3信道疑義度定義4.2.3

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

表示接收到符號(hào)bj后，仍然保留的關(guān)于X的平均不確定性。第15頁，課件共39頁，創(chuàng)作于2023年2月例4.2.4二元?jiǎng)h除信道則由此可得第16頁，課件共39頁，創(chuàng)作于2023年2月4.2.4平均互信息定義4.2.4

原始信源熵與信道疑義度之差稱為平均互信息。I(X;Y)=H(X)-H(X|Y)含義：接收到信道的輸出符號(hào)集Y之后，平均每個(gè)符號(hào)獲得的關(guān)于信道輸入符號(hào)集X的信息量。平均互信息具有非負(fù)性。第17頁，課件共39頁，創(chuàng)作于2023年2月兩個(gè)定理定理4.2.1

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

對(duì)于固定的信源分布，平均互信息I(X;Y)是信道傳遞概率p(y|x)的下凸函數(shù)。固定信源：信源概率分布p(x)不變第18頁，課件共39頁，創(chuàng)作于2023年2月平均互信息的例子例4.2.5

信源：信道：則互信息量：第19頁，課件共39頁，創(chuàng)作于2023年2月例4.2.7對(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頁，課件共39頁，創(chuàng)作于2023年2月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頁，創(chuàng)作于2023年2月4.3離散無記憶擴(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,…,YN}，輸入序列共有rN個(gè)，輸出序列共有sN個(gè)，輸入和輸出序列分別記為αk和βh。N次擴(kuò)展信道的數(shù)學(xué)模型為第22頁，課件共39頁，創(chuàng)作于2023年2月例4.3.1

二元無記憶對(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頁，課件共39頁，創(chuàng)作于2023年2月4.3.2定理定理4.3.1

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

若信道的輸入和輸出分別是N長序列X和Y，且信源是無記憶的，則：I(X;Y)≥∑I(Xi;Yi)當(dāng)信源和信道都是無記憶的，此時(shí)I(X;Y)=∑I(Xi;Yi)當(dāng)信道輸入序列的每一個(gè)符號(hào)來自同一個(gè)符號(hào)集A，信道輸出序列的每一個(gè)符號(hào)來自同一個(gè)符號(hào)集B，則∑I(Xi;Yi)=NI(X;Y)，即I(X;Y)=NI(X;Y)來自同一符號(hào)集：{00,01,10,11}，每一序列的兩個(gè)符號(hào)均來自{0,1}

來自不同符號(hào)集：{a1,a2,b1,b2}，每一序列的第一個(gè)符號(hào)來自{a,b}，第二個(gè)符號(hào)來自{1,2}第24頁，課件共39頁，創(chuàng)作于2023年2月4.4信道的組合組合方式并行：積信道串行：級(jí)聯(lián)信道例如：Internet例如：GSM重點(diǎn)介紹級(jí)聯(lián)信道（串聯(lián)信道）第25頁，課件共39頁，創(chuàng)作于2023年2月假設(shè)串聯(lián)的兩個(gè)信道為信道I和信道II，信道I的傳遞概率為p(y|x)，信道II的傳遞概率為p(z|xy)。定理4.4.2

若隨機(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)定理4.4.2叫做數(shù)據(jù)處理定理，它的含義是通過串聯(lián)信道的傳輸，只會(huì)丟失信息，不會(huì)增加信息，至多保持原來的消息量。這是信息不增性原理。信道Ip(y|x)信道IIp(z|xy)XYZ第26頁，課件共39頁，創(chuàng)作于2023年2月例4.4.1兩個(gè)二元對(duì)稱信道串聯(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頁，課件共39頁，創(chuàng)作于2023年2月例4.4.2信道I和信道II的信道矩陣分別為X,Y,Z構(gòu)成一個(gè)馬爾可夫鏈，則第28頁，課件共39頁，創(chuàng)作于2023年2月4.5信道容量定義4.5.1

信道容量定義為平均互信息的最大值：C=maxp(x){I(X;Y)}由定理4.2.1知，I(X;Y)是p(x)的上凸函數(shù)，稱使I(X;Y)取最大值的p(x)為最佳輸入分布。由I(X;Y)的定義式可知，I(X;Y)是由信道特性p(y|x)和信源特性p(x)共同決定的，但是容量C已對(duì)所有可能的p(x)取最大值，因此容量C僅與信道特性p(y|x)有關(guān)，也就是說，容量C是信道的固有特性，與信源無關(guān)。第29頁，課件共39頁，創(chuàng)作于2023年2月信息傳輸率信道的信息傳輸率R定義為平均互信息：R=I(X;Y)其含義是：平均每個(gè)符號(hào)所能傳送的信息量。研究信道的核心問題是求出信道容量C，以及達(dá)到信道容量C的信源分布p(x)（最佳輸入分布）。第30頁，課件共39頁，創(chuàng)作于2023年2月4.5.2特殊信道的信道容量無損信道：logr確定信道：logs無噪信道：logr=logs第31頁，課件共39頁，創(chuàng)作于2023年2月4.5.2.1無損信道一個(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頁，課件共39頁，創(chuàng)作于2023年2月4.5.2.2確定信道一個(gè)輸出對(duì)應(yīng)多個(gè)互不相交的輸入，即信道矩陣的每一行只有一個(gè)“1”，其余元素均為0。由于知道輸出之后，必然能夠確定其對(duì)應(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第33頁，課件共39頁，創(chuàng)作于2023年2月4.5.2.3無噪信道輸出與輸入是一一對(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頁，課件共39頁，創(chuàng)作于2023年2月4.5.3對(duì)稱信道定義4.5.2

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

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