可逆矩阵信道容量
假定所有输入字母的概率 Qk ，则
w j Qk p( j k )
k
j 0,1, , J 1
由
I ( x k ; Y ) p ( j k ) log
p( j k ) wj
C
k 0,1, , K 1
C
可得 即
j
j
p( j k ) log p( j k ) p( j k ) log w
j
验证
j
wj 2
k
j C
w j Qk p( j k )
可逆矩阵信道容量
特别注意 Qk 0 对上面得到的解进行验证。 计算wj 计算Qk 求解方程组 w j Qk p( j k )
wj 2
j C
验证
若 Qk 0 即所得到的解是正确的
否则满足条件的最大值在边界上，于是 令某个 Qk 为0， 再次进行试解。 特别 J K 多解 有时要令多个 Qk 为0，进行试解
根据 p ( j k ) j p ( j k ) log p ( j k )列方程组
1 1 1 1 1 1 1 1 1 2 1 4 2 4 4 2 log 2 4 log 4 4 log 4 2 0 3 0 1 1 1 1 log 1 1 log 1 1 log 1 1 3 4 4 2 4 4 4 4 2 2 4
准对称信道特点
定理1 若DMC关于输入为对称的，则对任意k∈{0, 1, …, K-1}
1 H (Y | X ) p( y | k ) log H (Y | X k ) p( j | k ) j 0
K 1 J 1 1 1 证明 H (Y | X ) p(i) p( j | i) log p(i) p( j | i) log p( j | i ) i 0 p( j | i ) i 0 j 0 j 0 K 1 J 1
可以看成是有J个未知数 j 的线性方程组。由假设P是 非奇异矩阵，故必有唯一解。 令 j 是其解，由上假设 又 w j 1，可得
j
wj 2
j C
2 2
j
C
j
C log( 2 )
j
可逆矩阵信道容量
特别注意 Qk 0 对上面得到的解进行验证。 计算wj 计算Qk 求解方程组 w j Qk p( j k )
k k '
I ( x k ; Y ) const I ( x k ';Y )
s jYs
满足了K-T条件，从而证明输入等概情况下达到信道 容量。
准对称信道容量计算公式
准对称DMC信道
C I ( x k ; Y ) p( j k ) log
j 0 J 1
p( j k ) wj
BSC(q=0) C=1-H(p) 纯删除信道(p=0) C=1-q
例 模K加性噪声信道
DMC的输入为X，X的所有事件为{0, 1, …, K-1}； DMC的噪声为Z，Z的所有事件为{0, 1, …, K-1}； DMC的输出为Y，Y的所有事件为{0, 1, …, K-1}； X与Z相互独立；Y=X+Z(modK)。 求信道容量C
p( j | k ) C p ( j | k ) log K 1 1 j 0 p( j | i) i 0 K I ( X k ; Y )；k
J 1
准对称信道容量特点
证明
若信道为准对称，则当输入等概时，有
p( j k ) I ( x k ; Y ) p( j k ) log wj j 0
输入 x X
Q( x)
+
输出 y x z Y
w( y )zZ p(Fra bibliotekz )干扰
例 模K加性信道容量
p(y|x)=P(Y=y|X=x) =P(X+Z(modK)=y|X=x) =P(x+Z(modK)=y|X=x) =P(Z=y-x(modK)|X=x) =P(Z=y-x(modK))。 若记P(Z=z)=sz，则转移概率矩 阵为
K 1 k 0
s1 s2 s0 s K 1 s0 s1 sK 2 sK 1 s0 s2 s3 s1

sK 1 sK 2 s K 3 s0
显然，模K加性噪声信道是对称DMC，则信道容量为
C log K sk log sk log K H ( Z )
p( j k ) log
j 0
J 1
p( j k ) 1 K
p( j i)
i 0
K 1
对称DMC信道
C log J p( j k ) log p( j k )
j 0 J 1
例 KSC信道容量
例 KSC信道
1 p p P K 1 p K 1 p K 1 p K 1 p K 1 p K 1 1 p
J 1
准对称，可将可将Y 划分为一些子集Ys

s jYs
p( j k ) p ( j k ) log wj
子集Ys中相应子阵的列是可置换的，所以，对 此子阵中的每一个输出j，概率 w j 都相等，
准对称信道容量特点
又在同一个子阵中，各行又都是第1行的置换，所以
p( j k ) p( j k ') p ( j k ) log p( j k ') log const wj wj jYs jYs
p K 1

p K 1 p p C log K (1 p) log( 1 p) ( K 1) log ( K 1) ( K 1) log K p log( K 1) H ( p)
p K 1 p K 1 1 p
k
例题
DMC信道的转移概率矩阵为
1 / 2 1 / 4 0 1 / 4 0 1 0 0 P 0 0 1 0 1 / 4 0 1 / 4 1 / 2
求其信道容量C。
非奇异矩阵
例题
j j
1 / 2 1 / 4 0 1 / 4 0 1 0 0 P 0 0 1 0 1 / 4 0 1 / 4 1 / 2
当K 2时：C 1 H ( p)
例 二元删除信道容量
例：二元删除信道 输入事件集为{0,1}；输出事 件集为{0,2,1}；转移概率矩阵 为
0 2 1 p P 0 1 p q q p q 1 p q 1
当q=0时，简化为BSC。 当p=0时，简化为纯删除信道。 达到信道容量时的最佳输入分 布为等概分布。 信道容量是转移概率矩阵任何 一行所对应的半平均互信息量。
wj 2
j C
验证
若 Qk 0 即所得到的解是正确的
否则满足条件的最大值在边界上，于是 令某个 Qk 为0， 再次进行试解。
k
可逆矩阵信道容量
列方程组
p( j k ) p( j k ) log p( j k )
j j j
k 0,1, , K 1
计算信道容量
C log( 2 )
p( y1 | x1 ) p( y2 | x2 ) p( y N | xN )
信道容量
C max{I ( X , Y )}
Qk
Review
达到C充要条件
输入概率矢量 Q Q0 , Q1, , QK 达到转移概率为 p( j k ) 的DMC的容量C的充要条件为
I ( x k;Y ) C
I ( x k;Y ) C
k , Qk 0 k , Qk 0
其中，
I ( x k ; Y ) p( j k ) log
j
p( j k )
Q p( j i )
i i
Review
信道容量计算
• 对于一般信道,信道容量计算相当复杂,我们 只讨论某些特殊类型的信道 • 几种特殊类型的信道 －无噪无损信道 －有噪无损信道 －无噪有损信道 －对称、准对称信道
p( j | k )
k 0
K 1
p (0 | k )
k 0
K 1
1 ，即输出等概分布 wj 根据概率归一性， J K 1 此时 p ( j | k ) K J k 0
准对称信道容量特点
定理3 对于准对称DMC信道 最佳输入分布为等概分布 （1）达到信道容量的最佳输入分布为等概分布； （2）信道容量为
1 p( j | k )
准对称信道特点
定理2 若DMC关于输出为对称的，则当输入分布等概时， 输出分布等概。 证明 关于输出对称，即任何一列是第一列的置换 设q(x)=1/K，x∈{0, 1, …, K-1}，则
1 w j Qk p ( j | k ) K k 0 1 K
K 1
j
j
p( j k ) log p( j k ) p( j k )[C log w ]
j j j
j
可逆矩阵信道容量
令 jj C C log log w wjj，得
p( j k ) p( j k ) log p( j k )
j j j
k 0,1, , K 1
j
j C
2C 2
，求得
2 5
1 w4 10
k
w2 2 2 C w3
再根据 w j Qk p( j k )，得到方程组
1 1 1 Q Q 2 1 4 4 10 1 2 Q1 Q2 4 5 1 2 Q3 Q4 4 5 1 1 1 Q Q 1 4 2 10 4