離散信道及其信道容量

《離散信道及其信道容量》由會員分享，可在線閱讀，更多相關(guān)《離散信道及其信道容量（53頁珍藏版）》請在裝配圖網(wǎng)上搜索。

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

2、（ 1）離散信道 （ 2）連續(xù)信道 （ 3）半離散半連續(xù)信道： （ 4）波形信道 以下我們只研究無反饋、固定參數(shù)的單用戶離散信道。 第一節(jié) 信道的數(shù)學(xué)模型及分類 P(y/X) X Y 根據(jù)這一模型，可對信道分類如下： 設(shè)離散信道的輸入為一個隨機變量 X，相應(yīng)的輸出的隨機 變量為 Y，如圖所示： 規(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( / ) nx my my my nx nx 2、離散信道的數(shù)學(xué)模型 第一節(jié) 信道的數(shù)學(xué)模

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

4、 , sb b b ( | ) ( | ) , ( 1 , 2 , , ; 1 , 2 , , )jiP y x P b a i r j s 1a ra 1b sb ( | )jiP b a 第一節(jié) 信道的數(shù)學(xué)模型及分類 P= y1 y2 ym x1 p(y1/x1) p(y2/x1) p(ym/x1) x2 p(y1/x2) p(y2/x2) p(ym/x2) xn p(y1/xn) p(y2/xn) p(ym/xn) 表示成矩陣形式： 第一節(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)

5、=p; P= 0 1 0 1-p p 1 p 1-p 0 1-p 0 p p 1 1-p 1 第一節(jié) 信道的數(shù)學(xué)模型及分類 例 2 二元刪除信道 X=0,1; Y=0,2,1 P= 0 2 1 0 1 p p 0 1 0 p 1-p 0 1-p 0 p p 1 1-p 1 2 P= y1 y2 ym x1 p(y1/x1) p(y2/x1) p(ym/x1) x2 p(y1/x2) p(y2/x2) p(ym/x2) xn p(y1/xn) p(y2/xn) p(ym/xn) 由此可見，一般單符號離散信道的傳遞概率可 以用矩陣表示 第一節(jié) 信道的數(shù)學(xué)模型及分類 第一節(jié) 信道的數(shù)學(xué)模型及分類 為

6、了表述簡便，可以寫成 ( / )j i ijP b a p 1 1 1 2 1 2 1 2 2 2 12 . . . . . . . s s r r r s p p p p p p P p p p 下面推導(dǎo)幾個關(guān)系式： 第一節(jié) 信道的數(shù)學(xué)模型及分類 （ 1）聯(lián)合概率 ( ) ( ) ( / ) ( ) ( / )i j i j i j i jP a b P a P b a P b P a b ( / )jiP b a其中 稱為 前向概率 ，描述信道的噪聲特性 ( / )ijP a b 稱為 后向概率 ， 有時也把 稱為 先驗 概率 ，把 稱為 后驗概率 ()iPa （ 2）輸出符號的概率 1

7、( ) ( ) ( / )rj i j i i P b p a p b a （ 3）后驗概率 ()( / ) () ij ij j P a bP a b Pb ( / )ijP a b 1 ( / ) 1r ij i P a b 表明輸出端收到任一符號，必定是輸入端某一符號 輸入所致 第二節(jié) 平均互信息 1、 信道疑義度 1 1( / ) ( / ) l o g ( / ) r j i j i ij H X b P a b p a b 這是收到 后關(guān)于 X的后驗熵，表示收到 后關(guān)于輸 入符號的信息測度 jb jb , 1( / ) ( / ) ( ) l og ( / )j XYH X Y E

8、 H X b P x y P x y 這個條件熵稱為信道疑義度，表示輸出端在收到一個 符號后，對輸入符號尚存的不確定性，這是由信道干擾 造成的，如果沒有干擾， 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)表示 收到一個符號后，對信源尚存的不確定性，所以二者之 差信道傳遞的信息量。 . ( / )( ; ) ( ) l o g ()XY P x yI X Y P x y Py 下面

9、我們討論一下互信息與其他的熵之間的關(guān)系 I(X;Y)=H(X)-H(X/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)即信到疑義度，也表示通過有噪信道造成的 損失，故也稱為 損失熵 ，因此信源的熵等于收到的信 息量加上損失的熵；而 H(Y/X)表示已知輸入的情況下， 對輸出端還殘留的不確定性，這個不

10、確定性是由噪聲 引起的，故也稱之為 噪聲熵 。 互信息與各類熵之間的關(guān)系可以用下圖表示： 第二節(jié) 平均互信息 H(X,Y) H(X/Y) H(Y/X) H(X) H(Y) I(X,Y) 可以看出，聯(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、平均互信息的非負性 I(X;Y)=0 該性質(zhì)表明，通過一

11、個信道總能傳遞一些信息，最 差的條件下，輸入輸出完全獨立，不傳遞任何信息，互 信息等于 0，但決不會失去已知的信息。 2、平均互信息的極值性 I(X;Y)=H(X) 一般來說，信到疑義度總是大于 0，所以互信息總是 小于信源的熵，只有當(dāng)信道是無損信道時，信道疑義度 等于 0，互信息等于信源的熵。 第三節(jié) 平均互信息的特性 3、平均互信息量的交互性 I(X,Y)=I(Y,X) I(Y;X)表示從 X中提取關(guān)于的 Y的信息量，實際上 I(X,Y) 和 I(Y,X)只是觀察者的立足點不同，對信道的輸入 X和輸出 Y的總體測度的兩種表達形式 4、平均互信息的凸?fàn)钚?11 1 ( / )( ; ) (

12、) ( / ) l o g ( ) ( / ) nm ji i j i n ij i j i i p y xI X Y p x p y x p x p y x 第三節(jié) 平均互信息的特性 定理 3.1 平均互信息 I(X;Y)是信源概率分布 P(X) 的 型凸函數(shù) 這就是說，對于一定的信道轉(zhuǎn)移概率分布，總可 以找到某一個先驗概率分布的信源 X，使平均交互信 息量達到相應(yīng)的最大值 Imax，這時稱這個信源為該信 道的匹配信源?？梢哉f不同的信道轉(zhuǎn)移概率對應(yīng)不同 的 Imax。 第三節(jié) 平均互信息的特性 例：對于二元對稱信道 0 1-p 0 p p 1 1-p 1 如果信源分布 X=w,1-w，則 (

13、 ; ) ( ) ( / )I X Y H Y H Y X 1( ) ( ) ( / ) l o g ( / )XYH Y P x P y x P y x 11( ) ( ) l o g l o g X H Y P x p ppp 11( ) l o g l o g ( ) ( )H Y p p H Y H p pp I(X;Y) w 1/2 1-H(P) 第三節(jié) 平均互信息的特性 ( 0)P y p p 而： ( 1 )P y p p 所以： ( ; ) ( ) ( )I X Y H p p H p 當(dāng)信道固定時，平均互信息時信源分布的 型凸函 數(shù)，最大只為 1-H(P) 第三節(jié) 平均互信息

14、的特性 定理 3.2 平均互信息 I(X;Y)信道傳遞概率分布 P(Y/X) 的 U型凸函數(shù) 這就是說，對于一個已知先驗概率為批 P(X)的離散 信源，總可以找到某一個轉(zhuǎn)移概率分布的信道，使平均 交信息量達到相應(yīng)的最小值 Imin?？梢哉f不同的信源先 驗概率對應(yīng)不同的 Imin?；蛘哒f Imin是 P(X)的函數(shù)。即 平均交互信息量的最小值是由體現(xiàn)了信源本身的特性。 例：對于二元對稱信道 0 1-p 0 p p 1 1-p 1 如果信源分布 X=w,1-w，則 由此可得 I(X;Y) p 1/2 ( ; ) ( ) ( )I X Y H p p H p 第四節(jié) 信道容量及其一般計算方法 第四節(jié)

15、 信道容量及其一般計算方法 我們先定義 信息傳輸率 ： R=I(X,Y)=H(X)-H(X/Y)=H(Y)-H(Y/X) bit/符號 由定理 3.1可知，對于每一個確定信道，都有一個信源 分布，使得信息傳輸率達到最大值，我們把這個最大值稱 為該信道的 信道容量 。 C I X Y H X H X YP X P X m a x ( , ) m a x ( ) ( / )( ) ( ) 信道容量與與信源無關(guān)，它是信道的特征參數(shù)，反 應(yīng)的是信道的最大的信息傳輸能力。 對于二元對稱信道，由圖可以看出信道容量等于 1-H(P) 第四節(jié) 信道容量及其一般計算方法 1、離散無噪信道的信道容量 （ 1）具有

16、一一對應(yīng)關(guān)系的無噪聲信道 x1 y1 x2 y2 x3 y3 此時由于信道的損失熵和疑義度都等于 0，所以 I(X;Y)=H(X)=H(Y) C=logr=logs 第四節(jié) 信道容量及其一般計算方法 (2)有噪無損信道 x1 x2 y1 y2 y3 y4 y5 此時信道疑義度不為 0，而信道噪聲熵為 0，從而 C=maxI(X;Y)=maxH(X)-H(X/Y)=maxH(X)=logr 1 / 2 1 / 2 0 0 0 0 0 0 3 / 5 3 / 1 0 1 / 1 0 0 0 0 0 0 0 1 P 可見，信道矩陣中每一列有且只有一個非零元素時，這 個信道一定是有噪無損信道 第四節(jié)

17、信道容量及其一般計算方法 (3)無噪有損信道 x1 x2 x3 x4 x5 y1 y2 此時信道疑義度為 0，而信道噪聲熵不為 0，從而 C=maxI(X;Y)=maxH(Y)-H(Y/X)=maxH(Y)=logs 第四節(jié) 信道容量及其一般計算方法 如果一個離散信道的信道轉(zhuǎn)移矩陣中的每一行都是由 同一組元素的不同組合構(gòu)成的，并且每一列也是由這一組 元素組成的，則稱為 對稱信道 如： 1 1 1 1 3 3 6 6 1 1 1 1 6 6 3 3 P 和 111 2 3 6 111 6 2 3 111 3 6 2 P 2、對稱離散信道的信道容量 第四節(jié) 信道容量及其一般計算方法 如果離散信道的

18、轉(zhuǎn)移矩陣如下 . 11 1 1 1 . . 11 pp p rr p p p p P r r r pp p rr 則稱此信道為 強對稱信道 或 均勻信道 ，它是對稱離 散信道的一種特例。該信道的各列之和也為 1 第四節(jié) 信道容量及其一般計算方法 下面我們來計算對稱離散信道的信道容量 I(X;Y)=H(Y)-H(Y/X) 而 1( / ) ( ) ( / ) l o g ( ) ( / ) ( / )X Y XH Y X P x P y x P x H Y X xP y x H(Y/X=x)是對矩陣的行求和，而由于對稱信道定義，我們 知道，此值是一個與 x無關(guān)的一個常數(shù)，即 12( / ) (

19、, . )sH Y X x H p p p 因此 12m a x ( ) ( , . . . ) sC H Y H p p p 可以看出，當(dāng)輸出等概分布時，即 H(Y)=logs時信道容 量達到。 第四節(jié) 信道容量及其一般計算方法 那么，在什么樣的信源輸出情況下，信道輸出能等概 分布呢？可以證明，輸入等概分布時，輸出也等概分布 1 1 1 1 ( ) ( ) ( / ) ( / ) . 1 ( ) ( ) ( / ) ( / ) XX s s s XX P y P x P y x P y x r P y P x P y x P y x r 可以看出，信道的輸出也是等概分布的 12l o g (

20、 , . )sC s H p p p 第四節(jié) 信道容量及其一般計算方法 例： 1 1 1 1 3 3 6 6 1 1 1 1 6 6 3 3 P 1 1 1 1 1 1 1 1l og 4 ( , , , ) 2 l og 3 l og 3 l og 6 l og 6 0. 81 7 3 3 6 6 3 3 6 6CH 對于二元對稱信道 l o g 2 ( ) 1 ( )C H p H p 這個式子很重要。 第四節(jié) 信道容量及其一般計算方法 例：對于強對稱信道，其信道容量為： l og ( , , , . ., )1 1 1p p pC r H p r r r l og l og l og l

21、 og . l og1 1 1 1 1 1p p p p p pr p p r r r r r r l og l og l og 1pr p p p r l og l og( 1 ) ( )r r H p 第四節(jié) 信道容量及其一般計算方法 3、準(zhǔn)對稱信道的信道容量： 若信道的列可以劃分成若干個互不相交的子集，每一個 子集都是對稱信道，則稱該信道為準(zhǔn)對稱信道，如： 1 1 / 3 1 / 3 1 / 6 1 / 6 1 / 6 1 / 3 1 / 6 1 / 3P 可劃分為： 1 / 3 1 / 6 1 / 6 1 / 3 1/3 1/3 1/6 1/6 第四節(jié) 信道容量及其一般計算方法 有如：

22、 2 0 . 7 0 . 1 0 . 2 0 . 2 0 . 1 0 . 7P 可分成： 0.7 0.2 0.2 0.7 0.1 0.1 第四節(jié) 信道容量及其一般計算方法 可以證明達到信道容量的輸入分布是等概分布，也可計 算準(zhǔn)對稱信道的信道容量為： 12 1 l og ( , , . ., ) l og n s k k k C r H p p p N M 其中 r是輸入符號集的個數(shù)， 為矩陣中的行元素 12, , ., sp p p kN 是第 k各矩陣中的行元素只和， 是第 k個矩陣的列元素 之和 kM 第四節(jié) 信道容量及其一般計算方法 例： 1 1 p q q pP p q p q 可分成

23、： 1 1 p q p p p q q l o g 2 ( 1 , , ) ( 1 ) l o g ( 1 ) l o g 2C H p q p q q q q q 第四節(jié) 信道容量及其一般計算方法 4、一般離散信道的信道容量 我們可以對輸入分布求極值，得到 1 1 ( / ) ( / ) l o g l o g () ( ) 1 s ji ji j j r i i P b a P b a e Pb Pa 而： l o gCe 定理 3.3 一般離散信道達到信道容量的充要條件是輸入概 率分布滿足 ( ) ( ; ) 0 ( ) ( ; ) 0 i i a I x Y C x b I x Y C

24、 x i i 對 所 有 其 p 對 所 有 其 p 1 ( / )( ; ) ( / ) l og () s ji ji j j p b aI x Y p b a pb 該定理說明，當(dāng)平均互信息達到信道容量時，信源每 一個符號都對輸出端輸出相同的互信息。 第四節(jié) 信道容量及其一般計算方法 第四節(jié) 信道容量及其一般計算方法 可以利用該定理對一些特殊信道求得它的信道容量 例：輸入符號集為 :0,1,2 10 11 22 01 P 假設(shè) P(0)=P(2)=1/2， P(1)=0，則： 1 ( 0 ) 2 1 ( 1) 2 Py Py 2 1 ( / 0 )(0 , ) ( / 0 ) l o g

25、 l o g 2 ()y PyI Y P y Py 2 1 ( / 2 )( 2 , ) ( / 2 ) l o g l o g 2 ()y PyI Y P y Py 2 1 ( / 1 )( 1 , ) ( / 1 ) l o g 0 (1)y PyI Y P y P 第四節(jié) 信道容量及其一般計算方法 所以： l og 2 1C 第四節(jié) 信道容量及其一般計算方法 對于一般信道的求解方法，就是求解方程組 11 ( / ) l o g ( / ) ( / ) l o g ( )ssj i j i j i j jj P b a P b a P b a P b C 移項得： 11 ( / ) l o

26、 g ( ) ( / ) l o g ( / )ssj i j j i j i jj P b a C P b P b a P b a 令 l o g ( )jjC P b 則 11 ( / ) ( / ) l o g ( / )ssj i j j i j i jj P b a P b a P b a 若 r=s，此方程有解，可以解出 s各未知數(shù) ，再根據(jù) j ( ) 2 j CjPb 得 1 21js C j 從而 1 lo g 2 js j C 第四節(jié) 信道容量及其一般計算方法 例： 1 1 1 0 2 4 4 0 1 0 0 0 0 1 0 1 1 1 0 4 4 2 P 可列方程組： 1

27、 2 4 2 3 1 3 4 1 1 1 1 1 1 1 1 1 l og l og l og 2 4 4 2 2 4 4 4 4 0 0 1 1 1 1 1 1 1 1 1 l og l og l og 4 4 2 4 4 4 4 2 2 第四節(jié) 信道容量及其一般計算方法 解之得： 23 14 0 2 2 0 0 2 5l og( 2 2 2 2 ) l og l og 5 1 2C 2 l og 5 114 1( ) ( ) 2 10P b P b 14 23 4 ( ) ( ) 30 11 ( ) ( ) 30 P a P a P a P a 0 l og 5 123 4( ) ( )

28、2 10P b P b 第五節(jié) 離散無記憶擴展信道及其信道容量 離散無記憶信道為： 1 1 1 2 1 2 1 2 2 2 12 . . . . . . . s s r r r s p p p p p p P p p p 則它的 N次擴展信道為： 第五節(jié) 離散無記憶擴展信道及其信道容量 1 1 1 2 1 2 1 2 2 2 12 N N N N N s s r r r s ( / )k n h kP k 為 N次擴展信源中的一個符號 h 為 N次擴展接收符號集中的一個符號 第五節(jié) 離散無記憶擴展信道及其信道容量 我們首先從一個例子開始 例：二元無記憶對稱信道得二次擴展信道 二元記憶對稱信道為

29、 pp P pp 22 22 22 22 p pp pp p pp p p pp pp p p pp p pp pp p 可以將信道的擴展和信源的擴展聯(lián)系起來看，當(dāng)信 源擴展以后，信道也就稱為了擴展信道。 第五節(jié) 離散無記憶擴展信道及其信道容量 則它的二次擴展信道為： 第五節(jié) 離散無記憶擴展信道及其信道容量 根據(jù)互信息的定義 ( ; ) ( ) ( / ) ( ) ( / )N N N N N N N NI X Y H X H X Y H Y H Y X 定理 3.5 如果信道是無記憶的，即 1 ( / ) ( / ) N ii i P y P y xx 1 ( ; ) ( ; ) N NN

30、ii i I X Y I X Y 則： 定理 3.6 如果信源是無記憶的 1 ( ; ) ( ; ) N NN ii i I X Y I X Y 第五節(jié) 離散無記憶擴展信道及其信道容量 因此，如果信源、信道都是無記憶的 ( ; ) ( ; )NNI X Y N I X Y NC NC 這就是離散無記憶擴展信道得信道容量，該信道容 量在信源是無記憶信源且每一個輸入變量 Xi達到最佳分 布時達到。 第六節(jié) 信源與信道的匹配 信道的信道容量是固定的，如果某一信源通過該信道 傳輸是，信息傳輸率達到了信道容量，我們認為 信源與信 道達到匹配 ，否則，我們認為有剩余。 定義： 信道剩余度 C-I(X;Y)

31、 信道的 相對剩余度 ( ; )1 I X Y C 對于無損信道，相對剩余度 ()1 lo g HX r 第六節(jié) 信源與信道的匹配 如何才能做到匹配呢？ 一般通信系統(tǒng)中，把信源發(fā)出的符號變成能在信道中 傳輸?shù)姆?，在傳輸時，要能夠盡量用較少的符號表示相 同的信息，這樣就可以提高信息的傳輸率，從而提高信道 的利用率。這就是香農(nóng)無失真信源編碼理論，也就是無失 真數(shù)據(jù)壓縮理論。 無失真信源編碼就是將信源輸出的消息變換成適合信 道傳輸?shù)男滦旁吹南韨鬏?，而使新信源的符號接近?概率分布，新信源的熵接近最大熵。這樣，信源傳輸?shù)男?息量達到最大，信道剩余度接近于零，信源與信道達到匹 配。這些是我們將在下一章討論這些問題。