離散信道及其信道容量

1、第三章 離散信道及其信道容量,第一節(jié) 信道的數(shù)學(xué)模型及分類,第二節(jié) 平均互信息,第三節(jié) 平均互信息的特性,第四節(jié) 信道容量及其一般計(jì)算方法,第五節(jié) 離散無(wú)記憶擴(kuò)展信道及其信道容量,第六節(jié) 信源與信道的匹配,第一節(jié) 信道的數(shù)學(xué)模型及分類,1、信道的分類：,根據(jù)信道用戶的多少，可分為：,（1）單用戶信道：只有一個(gè)輸入端和一個(gè)輸出端,（2）多用戶信道：至少有一端有兩個(gè)以上的用戶，雙向通信,根據(jù)輸入端和輸出端的關(guān)聯(lián)：,（1）無(wú)反饋信道,（

2、2）有反饋信道,第一節(jié) 信道的數(shù)學(xué)模型及分類,,根據(jù)信道參數(shù)與時(shí)間的關(guān)系：,（1）固定參數(shù)信道,（2）時(shí)變參數(shù)信道,根據(jù)輸入輸出信號(hào)的特點(diǎn) （1）離散信道 （2）連續(xù)信道 （3）半離散半連續(xù)信道： （4）波形信道,以下我們只研究無(wú)反饋、固定參數(shù)的單用戶離散信道。,第一節(jié) 信道的數(shù)學(xué)模型及分類,P(y/X),X,Y,,,根據(jù)這一模型，可對(duì)信道分類如下：,設(shè)離散信道的輸入為一個(gè)隨機(jī)變量X，相應(yīng)的輸出的隨機(jī)變量為Y，如

3、圖所示：規(guī)定一個(gè)離散信道應(yīng)有三個(gè)參數(shù)：輸入符號(hào)集：X={x1，x2，…， }輸出符號(hào)集：Y={y1，y2，…， }信道轉(zhuǎn)移概率：P(Y/X)={p(y1/x1),p(y2/x1),…p( /x1),……p(y1/ )…p( / )},2、離散信道的數(shù)學(xué)模型,,第一節(jié) 信道的數(shù)學(xué)模型及分類,（1）無(wú)干擾信道：輸入信號(hào)與輸出信號(hào) 有一一對(duì)應(yīng)關(guān)系,（2）有干擾無(wú)記憶信道：輸入與輸出無(wú)一一對(duì)應(yīng)關(guān)系，

4、 輸出只與當(dāng)前輸入有關(guān)；（3）有干擾有記憶信道：這是最一般的信道。,第一節(jié) 信道的數(shù)學(xué)模型及分類,3、單符號(hào)離散信道的數(shù)學(xué)模型 單符號(hào)離散信道的輸入變量為X，取值于輸出變量為Y，取值于 。并有條件概率條件概率被稱為信道的傳遞概率或轉(zhuǎn)移概率。 一般簡(jiǎn)單的單符號(hào)離散信道的數(shù)學(xué)模型可以用概率空間[X,p(y|x),Y]來(lái)描述。 X

5、 Y,,,,,,,,第一節(jié) 信道的數(shù)學(xué)模型及分類,,表示成矩陣形式：,第一節(jié) 信道的數(shù)學(xué)模型及分類,,,,,[例1] 二元對(duì)稱信道（BSC） X={0,1}; Y={0,1}; p(0/0)=p(1/1)=1-p; p(0/1)=p(1/0)=p;,0 1-p 0,p p,1

6、 1-p 1,第一節(jié) 信道的數(shù)學(xué)模型及分類,,,,,[例2] 二元?jiǎng)h除信道X={0,1}; Y={0,2,1},0 1-p 0,p,p,1 1-p 1,2,由此可見，一般單符號(hào)離散信道的傳遞概率可以用矩陣表示,第一節(jié) 信道的數(shù)學(xué)模型及分類,第一節(jié) 信道的數(shù)學(xué)模型及分類,為了表述簡(jiǎn)便，可以寫成,下面推導(dǎo)幾個(gè)關(guān)系式：,第一節(jié) 信道

7、的數(shù)學(xué)模型及分類,（1）聯(lián)合概率,其中,稱為前向概率，描述信道的噪聲特性,稱為后向概率，,有時(shí)也把 稱為先驗(yàn),概率，把 稱為后驗(yàn)概率,（2）輸出符號(hào)的概率,（3）后驗(yàn)概率,表明輸出端收到任一符號(hào)，必定是輸入端某一符號(hào)輸入所致,第二節(jié) 平均互信息,1、信道疑義度,這是收到 后關(guān)于X的后驗(yàn)熵，表示收到 后關(guān)于輸入符號(hào)的信息測(cè)度,這個(gè)條件熵稱為信道疑義度，表示輸出端在收到一個(gè)符號(hào)后，對(duì)輸入符號(hào)尚存的不確

8、定性，這是由信道干擾造成的，如果沒有干擾，H(X/Y)=0,一般情括下H(X/Y)小于H(X)，說(shuō)明經(jīng)過信道傳輸，總能消除一些信源的不確定性，從而獲得一些信息。,第二節(jié) 平均互信息,I(X;Y)=H(X)-H(X/Y),2、平均互信息,因?yàn)镠(X),表示傳輸前信源的不確定性，而H(X/Y)表示收到一個(gè)符號(hào)后，對(duì)信源尚存的不確定性，所以二者之差信道傳遞的信息量。,下面我們討論一下互信息與其他的熵之間的關(guān)系,I(X;Y)=H(X)-H(X/

9、Y) =H(X)+H(Y)-H(XY) =H(Y)-H(Y/X) (3.34),第二節(jié) 平均互信息,也可以得到：H(XY)=H(X)+H(Y/X)=H(Y)+H(X/Y),由3.34也可以看出，互信息I(X;Y)也表示輸出端H(Y)的不確定性和已知X的條件下關(guān)于Y的不確定性之差，也等于發(fā)送前后關(guān)于Y的不確定性之差。,H(X/Y)即信到疑義度，也表示通過有噪信道造成的損失，故也稱為損

10、失熵，因此信源的熵等于收到的信息量加上損失的熵；而H(Y/X)表示已知輸入的情況下，對(duì)輸出端還殘留的不確定性，這個(gè)不確定性是由噪聲引起的，故也稱之為噪聲熵。,互信息與各類熵之間的關(guān)系可以用下圖表示：,第二節(jié) 平均互信息,,,,H(X,Y),H(X/Y) H(Y/X),H(X) H(Y) I(X,Y),可

11、以看出，聯(lián)合熵等于兩園之和減去第三部分，也等于一個(gè)園加上另外一部分,下面討論兩種極端情況：,圖1,第二節(jié) 平均互信息,（1）無(wú)噪一一對(duì)應(yīng)信道,此時(shí)可以計(jì)算得：H(X/Y)=H(Y/X)=0在圖一中表示就是兩圓重合。,(2)輸入輸出完全統(tǒng)計(jì)獨(dú)立 此時(shí)I(X;Y)=0 H(X/Y)=H(X) H(Y/X)=H(Y),第三節(jié) 平均互信息的特性,1、平均互信息的非負(fù)性,I(X;Y)>

12、=0,該性質(zhì)表明，通過一個(gè)信道總能傳遞一些信息，最差的條件下，輸入輸出完全獨(dú)立，不傳遞任何信息，互信息等于0，但決不會(huì)失去已知的信息。2、平均互信息的極值性 I(X;Y)<=H(X) 一般來(lái)說(shuō)，信到疑義度總是大于0，所以互信息總是小于信源的熵，只有當(dāng)信道是無(wú)損信道時(shí)，信道疑義度等于0，互信息等于信源的熵。,第三節(jié) 平均互信息的特性,3、平均互信息量的交互性 I(X,Y)=

13、I(Y,X) I(Y;X)表示從X中提取關(guān)于的Y的信息量，實(shí)際上I(X,Y)和I(Y,X)只是觀察者的立足點(diǎn)不同，對(duì)信道的輸入X和輸出Y的總體測(cè)度的兩種表達(dá)形式,4、平均互信息的凸?fàn)钚?,第三節(jié) 平均互信息的特性,定理3.1 平均互信息I(X;Y)是信源概率分布P(X)的 型凸函數(shù),這就是說(shuō)，對(duì)于一定的信道轉(zhuǎn)移概率分布，總可以找到某一個(gè)先驗(yàn)概率分布的信源X，使平均交互信息量達(dá)到相應(yīng)的最大值Imax，這時(shí)稱這個(gè)信源為該

14、信道的匹配信源?？梢哉f(shuō)不同的信道轉(zhuǎn)移概率對(duì)應(yīng)不同的Imax。,第三節(jié) 平均互信息的特性,例：對(duì)于二元對(duì)稱信道,,,,,0 1-p 0,p,p,1 1-p 1,如果信源分布X={w,1-w}，則,,,I(X;Y),w,,1/2,,1-H(P),第三節(jié) 平均互信息的特性,而：,所以：,當(dāng)信道固定時(shí)，平均互信息時(shí)信源分布的 型凸函數(shù)，最大只為1-H(P),第三節(jié) 平均互信息的

15、特性,定理3.2 平均互信息I(X;Y)信道傳遞概率分布P(Y/X)的 U型凸函數(shù),這就是說(shuō)，對(duì)于一個(gè)已知先驗(yàn)概率為批P(X)的離散信源，總可以找到某一個(gè)轉(zhuǎn)移概率分布的信道，使平均交信息量達(dá)到相應(yīng)的最小值Imin?？梢哉f(shuō)不同的信源先驗(yàn)概率對(duì)應(yīng)不同的Imin?；蛘哒f(shuō)Imin是P(X)的函數(shù)。即平均交互信息量的最小值是由體現(xiàn)了信源本身的特性。,例：對(duì)于二元對(duì)稱信道,,,,,0 1-p 0,p,p,1

16、 1-p 1,如果信源分布X={w,1-w}，則 由此可得,,,I(X;Y),p,1/2,,第四節(jié) 信道容量及其一般計(jì)算方法,第四節(jié) 信道容量及其一般計(jì)算方法,我們先定義信息傳輸率： R=I(X,Y)=[H(X)-H(X/Y)]=[H(Y)-H(Y/X)] bit/符號(hào),由定理3.1可知，對(duì)于每一個(gè)確定信道，都有一個(gè)信源分布，使得信息傳輸

17、率達(dá)到最大值，我們把這個(gè)最大值稱為該信道的信道容量。,,信道容量與與信源無(wú)關(guān)，它是信道的特征參數(shù)，反應(yīng)的是信道的最大的信息傳輸能力。 對(duì)于二元對(duì)稱信道，由圖可以看出信道容量等于 1-H(P),第四節(jié) 信道容量及其一般計(jì)算方法,1、離散無(wú)噪信道的信道容量,,（1）具有一一對(duì)應(yīng)關(guān)系的無(wú)噪聲信道,x1 y1x2

18、 y2x3 y3,,,,此時(shí)由于信道的損失熵和疑義度都等于0，所以 I(X;Y)=H(X)=H(Y) C=logr=logs,第四節(jié) 信道容量及其一般計(jì)算方法,(2)有噪無(wú)損信道,,,,,,,x1,x2,y1,y2,y3,y4,y5,此時(shí)信道疑義度不為0，而信道噪聲熵為0，從而 C=max{I(X;Y)}=

19、max{H(X)-H(X/Y)}=max{H(X)}=logr,可見，信道矩陣中每一列有且只有一個(gè)非零元素時(shí)，這個(gè)信道一定是有噪無(wú)損信道,第四節(jié) 信道容量及其一般計(jì)算方法,(3)無(wú)噪有損信道,,,,,,,x1,x2,x3,x4,x5,y1,y2,此時(shí)信道疑義度為0，而信道噪聲熵不為0，從而 C=max{I(X;Y)}=max{H(Y)-H(Y/X)}=max{H(Y)}=logs,第四節(jié) 信道容量及其一般計(jì)算方法,如果一個(gè)離散信道的

20、信道轉(zhuǎn)移矩陣中的每一行都是由同一組元素的不同組合構(gòu)成的，并且每一列也是由這一組元素組成的，則稱為對(duì)稱信道 如：,和,2、對(duì)稱離散信道的信道容量,第四節(jié) 信道容量及其一般計(jì)算方法,如果離散信道的轉(zhuǎn)移矩陣如下,則稱此信道為強(qiáng)對(duì)稱信道或均勻信道，它是對(duì)稱離散信道的一種特例。該信道的各列之和也為1,第四節(jié) 信道容量及其一般計(jì)算方法,下面我們來(lái)計(jì)算對(duì)稱離散信道的信道容量,I(X;Y)=H(Y)-H(Y/X) 而,H(Y/X=x)是對(duì)矩陣的行求

21、和，而由于對(duì)稱信道定義，我們知道，此值是一個(gè)與x無(wú)關(guān)的一個(gè)常數(shù)，即,因此,可以看出，當(dāng)輸出等概分布時(shí)，即H(Y)=logs時(shí)信道容量達(dá)到。,第四節(jié) 信道容量及其一般計(jì)算方法,那么，在什么樣的信源輸出情況下，信道輸出能等概分布呢？可以證明，輸入等概分布時(shí)，輸出也等概分布,可以看出，信道的輸出也是等概分布的,第四節(jié) 信道容量及其一般計(jì)算方法,例：,對(duì)于二元對(duì)稱信道,這個(gè)式子很重要。,第四節(jié) 信道容量及其一般計(jì)算方法,例：對(duì)于強(qiáng)對(duì)稱信道，其信

22、道容量為：,第四節(jié) 信道容量及其一般計(jì)算方法,3、準(zhǔn)對(duì)稱信道的信道容量： 若信道的列可以劃分成若干個(gè)互不相交的子集，每一個(gè)子集都是對(duì)稱信道，則稱該信道為準(zhǔn)對(duì)稱信道，如：,可劃分為：,第四節(jié) 信道容量及其一般計(jì)算方法,有如：,可分成：,第四節(jié) 信道容量及其一般計(jì)算方法,可以證明達(dá)到信道容量的輸入分布是等概分布，也可計(jì)算準(zhǔn)對(duì)稱信道的信道容量為：,其中r是輸入符號(hào)集的個(gè)數(shù)， 為矩陣中的行元素,是第k各矩

23、陣中的行元素只和， 是第k個(gè)矩陣的列元素之和,第四節(jié) 信道容量及其一般計(jì)算方法,例：,可分成：,第四節(jié) 信道容量及其一般計(jì)算方法,4、一般離散信道的信道容量,我們可以對(duì)輸入分布求極值，得到,而：,定理3.3 一般離散信道達(dá)到信道容量的充要條件是輸入概率分布滿足,該定理說(shuō)明，當(dāng)平均互信息達(dá)到信道容量時(shí)，信源每一個(gè)符號(hào)都對(duì)輸出端輸出相同的互信息。,第四節(jié) 信道容量及其一般計(jì)算方法,第四節(jié) 信道容量及其一般計(jì)算方法,可以利用該定理對(duì)一

24、些特殊信道求得它的信道容量,例：輸入符號(hào)集為:{0,1,2},假設(shè)P(0)=P(2)=1/2，P(1)=0，則：,第四節(jié) 信道容量及其一般計(jì)算方法,所以：,第四節(jié) 信道容量及其一般計(jì)算方法,對(duì)于一般信道的求解方法，就是求解方程組,移項(xiàng)得：,令,則,若r=s，此方程有解，可以解出s各未知數(shù) ，再根據(jù),得,從而,第四節(jié) 信道容量及其一般計(jì)算方法,例：,可列方程組：,第四節(jié) 信道容量及其一般計(jì)算方法,解之得：,第五節(jié) 離散無(wú)記憶擴(kuò)展信道

25、及其信道容量,離散無(wú)記憶信道為：,則它的N次擴(kuò)展信道為：,第五節(jié) 離散無(wú)記憶擴(kuò)展信道及其信道容量,為N次擴(kuò)展信源中的一個(gè)符號(hào),為N次擴(kuò)展接收符號(hào)集中的一個(gè)符號(hào),第五節(jié) 離散無(wú)記憶擴(kuò)展信道及其信道容量,我們首先從一個(gè)例子開始例：二元無(wú)記憶對(duì)稱信道得二次擴(kuò)展信道 二元記憶對(duì)稱信道為,可以將信道的擴(kuò)展和信源的擴(kuò)展聯(lián)系起來(lái)看，當(dāng)信源擴(kuò)展以后，信道也就稱為了擴(kuò)展信道。,第五節(jié) 離散無(wú)記憶擴(kuò)展信道及其信道容量,則它的二次擴(kuò)展信道為：,第五節(jié)

26、離散無(wú)記憶擴(kuò)展信道及其信道容量,根據(jù)互信息的定義,定理3.5 如果信道是無(wú)記憶的，即,則：,定理3.6 如果信源是無(wú)記憶的,第五節(jié) 離散無(wú)記憶擴(kuò)展信道及其信道容量,因此，如果信源、信道都是無(wú)記憶的,這就是離散無(wú)記憶擴(kuò)展信道得信道容量，該信道容量在信源是無(wú)記憶信源且每一個(gè)輸入變量Xi達(dá)到最佳分布時(shí)達(dá)到。,第六節(jié) 信源與信道的匹配,信道的信道容量是固定的，如果某一信源通過該信道傳輸是，信息傳輸率達(dá)到了信道容量，我們認(rèn)為信源與信道達(dá)到匹配

27、，否則，我們認(rèn)為有剩余。 定義：信道剩余度＝C-I(X;Y) 信道的相對(duì)剩余度＝,對(duì)于無(wú)損信道，相對(duì)剩余度＝,第六節(jié) 信源與信道的匹配,如何才能做到匹配呢？ 一般通信系統(tǒng)中，把信源發(fā)出的符號(hào)變成能在信道中傳輸?shù)姆?hào)，在傳輸時(shí)，要能夠盡量用較少的符號(hào)表示相同的信息，這樣就可以提高信息的傳輸率，從而提高信道的利用率。這就是香農(nóng)無(wú)失真信源編碼理論，也就是無(wú)失真數(shù)據(jù)壓縮理論。 無(wú)失真信源編碼就是將信源輸出的