離散信道及其信道容量

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

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

3、圖所示：規(guī)定一個離散信道應(yīng)有三個參數(shù)：輸入符號集：X={x1，x2，…， }輸出符號集：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）無干擾信道：輸入信號與輸出信號 有一一對應(yīng)關(guān)系,（2）有干擾無記憶信道：輸入與輸出無一一對應(yīng)關(guān)系，

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

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

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

8、定性，這是由信道干擾造成的，如果沒有干擾，H(X/Y)=0,一般情括下H(X/Y)小于H(X)，說明經(jīng)過信道傳輸，總能消除一些信源的不確定性，從而獲得一些信息。,第二節(jié) 平均互信息,I(X;Y)=H(X)-H(X/Y),2、平均互信息,因為H(X),表示傳輸前信源的不確定性，而H(X/Y)表示收到一個符號后，對信源尚存的不確定性，所以二者之差信道傳遞的信息量。,下面我們討論一下互信息與其他的熵之間的關(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)表示已知輸入的情況下，對輸出端還殘留的不確定性，這個不確定性是由噪聲引起的，故也稱之為噪聲熵。,互信息與各類熵之間的關(guān)系可以用下圖表示：,第二節(jié) 平均互信息,,,,H(X,Y),H(X/Y) H(Y/X),H(X) H(Y) I(X,Y),可

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

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

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

14、信道的匹配信源?？梢哉f不同的信道轉(zhuǎn)移概率對應(yīng)不同的Imax。,第三節(jié) 平均互信息的特性,例：對于二元對稱信道,,,,,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ù)，最大只為1-H(P),第三節(jié) 平均互信息的

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

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

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

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

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

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

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

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

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

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

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

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

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