第12講離散無記憶信道的容量_W

1、第十二講離散無記憶信道的容量Review信道容量I ( X ;Y )Y = bjX= a k(x1,x2 ,xN)(y1 , y2 , yN)pN (y | x)pN (y | x) = p( y1 , y2 , yN | x1 , x2 , xN)= p( y1 | x1 ) p( y2 | x2 ) p( yN | xN)離散無記憶C = maxI ( X ,Y )信道容量Qk p( j k )Review達到C充要條件, Q , Q 達到轉移概率為p( j k)輸入概率矢量 Q = Q01K的DMC的容量C的充要條件為I (x = k;Y ) = CI (x = k;Y ) Ck, Qk

2、k, Qk 0= 0p( j k)其中，I (x = k;Y ) = p( j k ) logiQ p( j i)jiReview信道容量計算 對于一般信道,信道容量計算相當復雜,我們只討論某些特殊類型的信道 幾種特殊類型的信道無噪無損信道有噪無損信道無噪有損信道對稱、準對稱信道準對稱信道特點定理1若DMC關于輸入為對稱的，則對任意k0, 1, , K-1J -1H(Y | X ) = p( y | k) log 1= H(Y | X = k)p( j |k)j=0K-1 J -1K-1J -1 1 1H(Y | X) = p(i) p( j | i)log p( j | i) = p(i)p

3、( j | i)log p( j | i)證明i=0 j=0i=0j=0關于輸入對稱，則P的任一行是第一行的置換，即J -1J -1 p( j |i) log= p( j | k) log 1 1kp( j |i)p( j | k)j =0j =0J -1 1H (Y | X ) = p( j | k ) log于是p( j | k )j =0準對稱信道特點定理2若DMC關于輸出為對稱的，則當輸入分布等概時，輸出分布等概。證明關于輸出對稱，即任何一列是第一列的置換設q(x)=1/K，x0, 1, , K-1，則KK -1-1 1Kj= Q kp ( j | k ) =wp ( j | k )k

4、 = 0k = 0K-1 1K=p ( 0 | k )k = 0= 1，即輸出等概分布根據概率歸一性，wjJK-1 K Jp ( j | k ) =此時k = 0準對稱信道容量特點定理3對于準對稱DMC信道（1） 達到信道容量的最佳輸入分布為等概分布（2） 信道容量為J -1p( j | k )C =p( j | k ) logK -1 1 j =0p( j | i)Ki = 0= I ( X= k ;Y )； k準對稱信道容量特點證明若信道為準對稱，則當輸入等概時，有J -1wjj =0準對稱，可將可將Y 劃分為一些子集Ysp( j k )= p( j k) logsjYswj子集Ys中相應

5、子陣的列是可置換的，所以，對此子陣中的每一個輸出j，概率 wj都相等，準對稱信道容量特點又在同一個子陣中，各行又都是第1行的置換，所以 p( j k ) log p( j k ) = p( j k ) log p( j k) = constwjwjjYsjYsI (x = k;Y ) = const = I (x = k ;Y )k k sjYs滿足了K-T條件，從而證明輸入等概情況下達到信道 容量。準對稱信道容量計算公式準對稱DMC信道對稱DMC信道J -1C = log J + p( j k) log p( j k)j =0C = I (x = k;Y ) = J -1 p( j k) l

6、og= J -1 p( j k ) logK -1j =0wjj =01 p( j i)K i=0例KSC信道容量例 KSC信道其中0p 0特別注意對上面得到的解進行驗證。= 2b j -Cw計算wjjwj = Qk p( j k )求解方程組計算Qk驗證k 0 即所得到的解是正確的若 Qk否則滿足條件的最大值在邊界上，于是令某個Qk 為0，再次進行試解?？赡婢仃囆诺廊萘苛蟹匠探M p( j k )b j = p( j k ) log p( j k )k = 0,1, K-1j計算信道容量jC = log(2b j )j驗證b -Cw= 2jjwj = Qk p( j k )k可逆矩陣信道容量Q

7、k 0特別注意對上面得到的解進行驗證。= 2b j -Cw計算wjjwj = Qk p( j k )求解方程組計算Qk驗證k 0 即所得到的解是正確的若 Qk否則滿足條件的最大值在邊界上，于是令某個Qk 為0，再次進行試解。J K 多解有時要令多個特別Qk為0，進行試解例 題DMC信道的轉移概率矩陣為1/41/21/ 41000011/ 40 0P =00 1/41/2 求其信道容量C。非奇異矩陣1/401/21/ 41000011/ 40P =例 題00 1/41/2 p( j k )b j = p( j k ) log p( j k )列方程組根據jj1 b+ 1 b+ 1 b= 1 lo

8、g 1 + 1 log 1 + 1 log 112444224444b2 = 0b= 03+ 1 b+ 1 b= 1 log 1 + 1 log 1 + 1 log 11 b413442444422b2 = b3 = 0b1 = b4 =-2得C = log(2b j) = log 5 -1從而j1/21/ 41000011/ 41/ 4001/ 20P =例 題0 1/4= 2b j -C= 2-C 2b j1，求得驗證根據 wj= 2b1-Cw1 = 2= w4 =b -= 2C= ww2 10235wj = Qk p( j k )，得到方程組再根據k= 1141 Q + 1 Q=1Q=

9、QQ= Q=可得223143014304+ Q101 Q= 2 0，因此結果正確C = log 5-1最佳分布為經驗證Qk125= 25= 1 1041Q+Q3441 Q + 1 Q44= 11142Q= Q=Q= Q23143030N次擴展信道容量pN (y | x)NXNY( y1 , y2 , yN)(x1,x2,xN)yn Yn = 0,1,2, J -1xn Xn = 0,1,2, K -1p( yn | xn )NI ( XN ;Y) I (X;Y) NCN【定理】nnn =1信道 N次擴展信道容量X N ) = H (YY Y證明H (YNXXX)12N12N= H (Y1X1

10、X2 XN ) + H (Y2X1 X 2 XNY1)+H (YNNX1 X 2 XNY1Y2 YN-1)= H (YnXn )無記憶信道n=1H (Y N ) = H (YY Y)12N= H (Y1 ) + H (Y2 Y1 ) +H (YNY1Y2 YN -1)N H (Yn )注：當輸入字母序列中各字母統(tǒng)計獨立時，輸出各字母y也相互獨立，此時等號成立。n=1N次擴展信道容量X N ) = H (YY Y證明H (YNXXX)12N12N= H (Y1X1 X2 XN ) + H (Y2X1 X 2 XNY1)+H (YNNX1 X 2 XNY1Y2 YN-1)= H (YnXn )無記憶信道n=1H (Y N ) = H (YY Y)12N= H (Y1 ) + H (Y2 Y1 ) +H (YNNY1Y2 YN -1) H (Yn )n=1N次擴展信道容量X n )NI ( X N ;Y N ) = H (Y N ) - H (YNNnnn =1= I ( Xn ;Yn )n=1注：當輸入字母序列中各字母統(tǒng)計獨立時，等號成立。由信道容量的定義知，對于任意n，有I ( X