图片背景-四边形的认识

§4.2信道容量的计算
这里 ，我们介绍一般离散信道的信道容量计算方法，根据信道容量的定义，就是在固定
信道的条件下，对所有 可能的输入概率分布
P(x)
求平均互信息的极大值。前面已知
I

X;Y

是输入概率分布的上凸函数，所以极大值一定存在。而
I(X;Y)
是
r
个变量
{p(x
1
),p(x
2
),p(x
r
)}
的多元函数。并且满足

p(x
i
)1< br>。所以可用拉格朗日乘子法来
i1
r
计算这个条件极值。引入一个函数：
I(X;Y)



p(x
i
)[I(X;Y)


p(x)
解方程组
i
i
p(x
i
)]
i
p(x
i
)
0



p(x)1
（4.2.1）
i
i
可以先解出达到极值的概率分布和拉格朗日乘子

的值，然后在解出信道容量
C
。因
为
rs
I(X;Y)

p(x
i
)Q(y
i
x
i
)log
i1j1
Q(y
i
x
i
)

p(y
i
)
而
p(y
i
)

p(x
i
)

p(x)Q(y
i
i1
r
i
x
i< br>)
，所以
Q(y
i
x
i
)
p(y
i
)

logp(y
i
)(
p

e
(x
i
)
lnp(y
i
))logloge
。
解（4.2.1）式有
Q(y
i
x
i
)
rsQ(y
i
x
i
)
Q(y
i
x
i
)log

p(x
i
)Q(y
i
x
i
)loge

0


p(y)p(y)
j1i1j1
ii
s
（对
i1,2,,r
都成立）
又因为


p(x)Q(y
k
k1
s
j
r
k
x
k
)p(y
j
)

Q(y


j1
x
i
)

1,i

1,2,

,r

所以(4.2.1)式方程组可以转化为


Q(y
j
x
i
)log
j1
r
s
Q(y
j
x
i
)
p(y
j
)



loge(i

1,2,

,r)



p(x)1

i
i 1

假设使得平均互信息
I(X;Y)
达到极值的输入概率分布
{p
1
,p
2
,p
r
}
这样有


p(x
i
)Q(y
j
x
i
)log< br>i1j1
rs
Q(y
j
x
i
)
p(y< br>j
)


loge

从而上式左边即为信道容量，得

C

loge

现在令

I(x
i
;Y)

Q(y
j
x
i
)log
j1
s
Q(y
j
x
i
)
p( y
j
)

式中，
I(x
i
;Y)
是输出端 接收到Y后获得关于
Xx
i
的信息量，即是信源符号
Xx
i对输
出端Y平均提供的互信息。
一般来讲，
I(x
i
;Y)< br>值与
x
i
有关。根据（4.2.2）式和（4.2.3）式，

I(x
i
;Y)C

(i1,2,,r)

所以对于一般离散信道有如下定理。
定理4.2.1 一般离散信道的平均互信息
I(X;Y)
达到极大值（即等于信道容量）的充
要条件是输入概率分布
{p(x1
),,p(x
n
)}
满足

(a)

I(x
1
;Y)C
对所有的
x
i
,p(x
i
)0


(b)

I(x
i
;Y)C
对所有的
x
i
,p(x
i
)0

这时C就是所求的信道容量。
对于离散信道来说，其实信道容量还有一个解法：迭代解法。
定理4.2.2 设信道的向前转移概率矩阵为
Q(Q(y
j
x
i
))
KJ
，
P
是任给的输入字母的
一个初始概率分布， 其所有分量
P
0
(x
k
)0
。按照下式不断地对概率分布 进行迭代，更新：
0
P(x
k
)P(x
k
)

r1r

k
(P
r
)

P(x)

(P)

rr
ii
i1
r
K
其中

k
(P
r
)exp[I(Xx
k
;Y)]< br>PP



Q

y
j
x
i



J

exp


Q

y
j
x
k

log
K

r

j1

PQ

y
j
x
i





i1


r
由此所得的
IP,Q< br>序列收敛于信道容量C。

我们还可以将上述过程写成算法以便编制程序实现（如图4.2.1）

I
L
log{

P(x)

k
k1< br>K
k
(P)}


I
U
log{max

k
(P)}

k

开始



I
L
log{

P(x
k
)

k
(P)}

k1
K
P
0
P

I
U
log{max

k
(P)}

k

k
(P)



I
L
(P)


I
U
(P)






I
U
I
L








CI
L







图4.2.1 信道容量的迭代算法
对于一些特殊的离散信道，我们有方便的方法计算其信道容量。

(P)
P (x)P(x)

1
P(x)

(P)

定义4.2.1 设X和Y分别表示输入信源与输出信源，则我们称
HXY
为损失熵 ，

H

YX

为信道噪声熵。
如果信道的损失熵
HXY0
，则次信道容量为


C

maxI

X;Y

max

H(x)H

XY

maxH(X)1ogr
（bit符号 ）这里输入
P(x)P(x)P(x)
信源X的信源符号个数为
r
。
如果信道的噪声熵
HYX0
，则此信道容量为

C
 
maxI

X;Y

maxH(Y)logs
（b it符号）
P(x)P(x)
这里输出信源符Y的符号个数为s.
定义4.2.2 一个信道Q称为对称离散信道，如果它满足下面的性质：
（1）信道Q矩阵中每一行是另一行的置换；
（2）每一列式另一列的置换。
例如，信道矩阵

1

Q

3
1



6
1
3
1
6
1
6
1
3

1
1




2
6

1
1

和
Q


6

3


1

3
1
3
1
2
1
6
1

6

1



3
1

2

满足对称性，所以对应信道是对称离散信道。
定义4.2.3 对称离散信道的信道容量为

2

,

,P
s


（bit符号）

ClogsH

P
1
,P

2

,,P
s

}
和输 出符号集的个数s有关。 上式只与対称信道矩阵中行矢量
{P
1
,P
证明
I(X;Y)H(Y)HYX

而
HYX


P(x)

P

yx

log
1

p

yx

xy



P(x)H

YXx


x
由于信道的对称性，所以
HYXx
与
x
无关，为一常熟，即
 

2

,

,P
s





Cmax

H(Y) H

P
1
,P
P(x)

2

, ,P
s

)

logsH(P
1
,P
接着举一个例子加以说明。
例4.2.1 某对称离散信倒的信道矩阵为

1


3

P

1


6
1
3
1
61
6
1
3
1


6


1


3


用公式计算信道容量

Clog4H(,,,)


2

log
1111
3366

1

3
1111111

logloglog


3336666


0.0817
（bit符号）
定义4.2.3 若信道矩阵Q的列可以划分成若 干互不相交的子集矩阵
B
K
，即
B
i
B
j


,(ij)
且
B
1
B
2
 B
n
Y
。由
B
K
为列组成的矩阵
Q
k< br>是对称矩阵，
则称信道矩阵Q所对应的信道为准对称信道。
例如，信道矩阵

1


3

P
1


1


6
1
3
13
1
6
1
6
1


6

0.70.10.2



P

2

0.20.10.7


< br>
1


3

都是准对称信道，在信道矩阵
P
1
中，Y可以划分为三个子集，由子集的列组成的矩阵
为

1


3



1


6
1


6


，
1


3


1



3


，

1



3


1


6




1



3

它们满足对称性，所以
P
1
对应的信道是准对称信道。同理
P
2
可划分为




0.70.2


，


0.20.7


0.1



0. 1




这两个矩阵也满足对称性。
下面，我们给出准对称离散信道的信道容量计算公式

2

,,P
s

)

ClogrH(P
1
,P

N
k1
n
k
logM
k


2

,,P
s
)
为准对称信道矩阵中的行矢量。设矩阵可其中，
r
是输入符号集的个 数，
(P
1
,P
划分为
n
个互不相交的子集。
N< br>k
是第
k
个子矩阵
Q
k
中行元素之和，
M< br>k
是第
k
个子矩
阵
Q
k
中列元素之和，即

N
k

yY
k
P

yx


i

M
k


P

yx

,y

Y,(k

1,2,

,n)

ik
x
并且可以证明达到准对称离散信道容量的输入分布式等概分布，我们将推导作为习题留
给读者 。
例4.2.2 设信道传递矩阵为
0 0
p

1pqq
1-p-q


P


pq1pq



q
可表示成如图4.2.2所示，计算其信道容量
p
根据上面计算公式可得

N
1
1q,N
2
q


p 2
M
1
1q,M
2
2q


q
则有


Clog2H(1pq,q,p)

1-p-q
1 1

(1q)log1(q)qlog2q


plogp(1pq)log1(pq)(1q)log
下面我们举一些其他 信道容量的例子
例4.2.3 设离散信道如图4.2.3所示，输入符号集为
{a
1
,a
2
,a
3
,a
4
,a
5
}
，输出符号
集为
{b
1
,b
2
}
，信道 矩阵为
2
图4.2.2
1q
X

Y

a
1

a
2

b
1

a
3

a
4

b
2

a
5

图4.2.3


1< br>

1


P

1

2


0



0
0


0


1


2


1


1


a
5
由于输入符号
a
3
传递到
b
1
和
b
2< br>是等概率的，所以
a
3
可以省去。而且
a
1
,a2
与
a
4
，
都分别传递到
b
1
和b
2
，因此可只取
a
1
和
a
5
，所以 设输入概率分布
P(a
1
)P(a
5
)
1
，< br>2
P(a
2
)P(a
3
)P(a
4
) 0
，可以计算得
P(b
1
)P(b
2
)

I(xa
1
;Y)I(xa
2
;Y)log2


I(xa
4
;Y)I(xa
5
;Y)log2


I(xa
3
;Y)0

可见，此假设分布满足定理4.2.1，因此，信道容量

Clog21
（bit符号）
1
，由定理4.2.1得
2
1
,p(a
2
)P(a
3
)P(a
4
)0

2
1
若设输入分布为
P(a
1
)P( a
2
)P(a
4
)P(a
5
),P(a
3< br>)0
。同理可得
4
1
P(b
1
)P(b
2
)
，根据定理4.2.1有
2
最佳分布是
P(a
1
)P(a
5
)

I(x
i
;Y)log2

(x
i
a< br>1
,a
2
,a
4
,a
5
)


I(x
i
;Y)log2

(x
i
x
3
)

从而，输入分布
P(a
1
)P(a
2
)P(a
4
)P(a
5
)
1
,P(a
3
)0
也是最佳分布，可
4
见 ，信道最佳输入分布不是唯一的。
对于一般的离散信道，我们很难利用特殊计算方法，因此只能采用解 方程组式
（4.2.2）的方法。
我们将（4.2.2）式的前r个方程组改写成


Q

yx

log

yx
< br>

Q

yx

logP(y)C

iiiiiii
j1j1
ss

(i1,2,,r)

移项后得


Q

yx


ClogP(y)
< br>

Q

yx

logQ

yx< br>

jijjiji
j1j1
ss

(i1,2,,r)

令

j
ClogP(y
j
)
，代入上式得


Q

yx




Q

yx

log

yx


jijjiji
j1j1
ss

(i1,2,,r)

化为矩阵形式为

H

Yx
1




1




H

Yx
2




2


Q













H

Yx


r


s

这是含有
s
个未知数

j
,r
个方程的非齐 次线性方程组。
如果设
rs
，信道矩阵
Q
为非奇异矩阵，则此方 程组有解，并且可以求出

j
的数
值，然后根据

P

y

1
求得信道容量
j
j1
s

Clog

2
j

j
（bit符号） 由这个
C
值可解得对应的输出概论分布
P(y
j
)
。

P(y
j
)2
r

j
C

(j1,2,,s)

再根据
P(y
j
)
< br>分布
{P(x
i
)}
。

P(x)Q
< br>yx

,j

1,2,

s,
即可解出达到 信道容量的最佳输入
iji
i1
下面给出一例。
例4.2.4 设离散 无记忆信道输入
X
的符号集为
{a
1
,a
2
,a< br>3
,a
4
}
，输出
Y
的符号集为
{b
1
,b
2
,b
3
,b
4
}
，如图4.2 .4所示。其信道矩阵为


1
< br>
2

0

Q

0


1



4
1
4
1
0
0
0
0
1
1
4
1


4

0



0



1


2

b
1


X

Y


a
1
12
14 14

a
2
1
b
2



a
3
1
b
3

14 14

a
4
12
b
4


我们才用上面所讲的方法来计算信道容量：

111111111

1


2


4
logloglo g

244224444


2
0



3
0


111111111

1


3


4
logl oglog

444444422
解方程组得

2
< br>
3
0;

1


4
2;< br>
信道容量
Clog
2
(2222)log
2
51
（bit符号）
又求得输出分布

P(b
1
)P(b
4
)2

P(b
3
)P(b
2
)
因此可以求得最佳输入分布为

P(a
1
)P(a
4
)
(2log
2
51)
2002

1

10
4

10
4

30

P(a
2
)P(a
3
)
11

30
例4.2.5 设有两个独立并联信道如图4.2.5，计算它的信道容量。

X
1

信道

Y
1

1

Qy
1
x
1




X
2

信道

2

Y
2


Qy
2
x
2



解 根据定理4.1.1有

I (X
1
X
2
;Y
1
Y
2
)


I(X;Y)

ii
i1
2
即联合平均互信息 不大于各自信道的平均互信息之和，因此得到独立并联信道的信道容量为

C
1,2
maxI(X
1
X
2
;Y
1< br>Y
2
)
p(x
1
x
2
)

C

i
i1
2

C
i
max I(X
i
,Y
i
)
，是个独立信道的信道容量。
p(x
i
)
只有当输入符号
x
i
互相独 立，且输入符号
x
i
的概率分布达到各子信道容量的概率分布
时，独立并联信 道的信道容量才等于各信道容量之和，即

C
1,2


C
i1
2
i

这个方法推广到N个独立并联信道容量的计算，即有

C
1,2,

,N

p(x
1
x
2

x
N
)
maxI(X
1
X
2

X
N
;Y
1
Y
2

Y
N
)

C
i

i1
N
对于信道Ⅰ和Ⅱ，我们将它串联起来组成新的信道（如图4.2.6）

X 信道 Y Z
信道Ⅰ 信道Ⅱ

图4.2.6
则此信道容量为
C
串
(,)maxI(X;Z)

p(x)
例4.2.6 设有两个离散二元对称信道（BSC信道），其串联信道如图4.2 .7，并设第一
个信道输入符号集的概率空间为

0,

X






P(x)




1
,

2
1

1



2



X
二

元

对

信
Y
二

元

对

称

信
Z
称

道 Ⅰ
道 Ⅱ

图4.2.7
而两个信道的信道矩阵分别为

Q
1
Q
2



p

所以串联信道总的信 道矩阵为

1pp



1p


2p(1p)



22< br>
(1p)p


(1p)
2
p
2

QQ
1
Q
2



2p(1p)

根据平均互信息定义

I(X;Y)1H(p)
（bit符号）

I(X;Z)1H[2p(1p)]
（bit符号）
其中，
I (X;Y)I(X;Z)
（根据信息不增原理）。因此，当串联信道数目越多时，损失的信
息 越多，可证：
limI(X;X
n
)0
。
n
对于本例中两个串联的二元离散对称信道，其信道容量为

C
串
(,)maxI(X;Z)1H(2p(1p))
（bit符号）
p(x)