第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，再次进行试解。可逆矩阵信道容量列方程组 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 )注：当输入字母序列中各字母统计独立时，输出各字母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注：当输入字母序列中各字母统计独立时，等号成立。由信道容量的定义知，对于任意n，有I ( X