信道容量的计算

§4.2信道容量的计算

这里，我们介绍一般离散信道的信道容量计算方法，根据信道容量的定义，就是在固定信道的条件下，对所有可能的输入概率分布P(x)求平均互信息的极大值。前面已知I?X;Y?是输入概率分布的上凸函数，所以极大值一定存在。而I(X;Y)是r个变量

r{p(x1),p(x2),?p(xr)}的多元函数。并且满足?p(xi)?1。所以可用拉格朗日乘子法来

i?1计算这个条件极值。引入一个函数：??I(X;Y)???p(xi)解方程组

i?[I(X;Y)?????p(xi)?ip(xi)]?p(xi)?0

?ip(xi)?1 （4.2.1）

可以先解出达到极值的概率分布和拉格朗日乘子?的值，然后在解出信道容量C。因为

rsI(X;Y)???i?1j?1p(xi)Q(yixi)logQ(yixi)p(yi)

r而p(yi)??i?1p(xi)Q(yixi)，所以

??p(xi)logp(yi)?(?p?lnp(yi))loge?(x)iQ(yixi)p(yi)loge。

解（4.2.1）式有

s?j?1Q(yixi)logQ(yixi)p(yi)rs???i?1j?1p(xi)Q(yixi)Q(yixi)p(yi)loge???0

（对i?1,2,?,r都成立） 又因为

r ?k?1p(xk)Q(ykxk)?p(yj)

s ?Q(yj?1jxi)?1,i?1,2,?,r

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

s

?j?1rQ(yjxi)logQ(yjxi)p(yj)???loge(i?1,2,?,r)

?i?1p(xi)?1

假设使得平均互信息I(X;Y)达到极值的输入概率分布{p1,p2,?pr}这样有

rs

??i?1j?1p(xi)Q(yjxi)logQ(yjxi)p(yj)???loge

从而上式左边即为信道容量，得 C???loge 现在令

s I(xi;Y)??j?1Q(yjxi)logQ(yjxi)p(yj)

式中，I(xi;Y)是输出端接收到Y后获得关于X?xi的信息量，即是信源符号X?xi对输出端Y平均提供的互信息。

一般来讲，I(xi;Y)值与xi有关。根据（4.2.2）式和（4.2.3）式， I(xi;Y)?C (i?1,2,?,r) 所以对于一般离散信道有如下定理。

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

(a) I(x1;Y)?C 对所有的xi,p(xi)?0 (b) I(xi;Y)?C 对所有的xi,p(xi)?0 这时C就是所求的信道容量。

对于离散信道来说，其实信道容量还有一个解法：迭代解法。

定理4.2.2 设信道的向前转移概率矩阵为Q?(Q(yjxi))K?J，P是任给的输入字母的一个初始概率分布，其所有分量P(xk)?0。按照下式不断地对概率分布进行迭代，更新：

r?1r00P(xk)?P(xk)?k(P)Kr

?i?1rP(xi)?i(P)

rr其中 ?k(P)?exp[I(X?xk;Y)]P?Pr

??J??exp??Q?yjxk?log?j?1

???Q?yjxi????Kr ?PQ?yjxi???i?1?由此所得的I?P,Q?序列收敛于信道容量C。

r我们还可以将上述过程写成算法以便编制程序实现（如图4.2.1）

K IL?log{?k?1P(xk)?k(P)}

IU?log{max?k(P)}

k 开始

KIL?log{?k?1P(xk)?k(P)} P0?P IU?log{max?k(P)} k?k(P) IL(P)

IU(P)

IU?IL??

C?IL

P(x)?P(x)

图4.2.1 信道容量的迭代算法

对于一些特殊的离散信道，我们有方便的方法计算其信道容量。

?(P)??1P(x)?(P) 定义4.2.1 设X和Y分别表示输入信源与输出信源，则我们称H?XY?为损失熵，

H?YX?为信道噪声熵。

如果信道的损失熵H?XY??0，则次信道容量为

C??maxI?X;Y??max?H(x)?H?XYP(x)P(x)???maxH(X)?1ogr（bit/符号）这里输入

P(x)信源X的信源符号个数为r。

如果信道的噪声熵H?YX??0，则此信道容量为

C???maxI?X;Y??maxH(Y)?logs（bit/符号）

P(x)P(x)这里输出信源符Y的符号个数为s.

定义4.2.2 一个信道Q称为对称离散信道，如果它满足下面的性质： （1）信道Q矩阵中每一行是另一行的置换； （2）每一列式另一列的置换。 例如，信道矩阵

??Q?????131613161613?11????26?11?和Q???6?3??1??31312161??6?1? ?31??2?满足对称性，所以对应信道是对称离散信道。 定义4.2.3 对称离散信道的信道容量为

C?logs?H?P1?,P2?,?,Ps?? （bit/符号）

上式只与対称信道矩阵中行矢量{P1?,P2?,?,Ps?}和输出符号集的个数s有关。

证明 I(X;Y)?H(Y)?H?YX? 而 H?YX?? ??xP(x)?P?yx?logy1p?yx?

?xP(x)H?YX?x?

由于信道的对称性，所以H?YX?x?与x无关，为一常熟，即 C?max?H(Y)?H?P1?,P2?,?,Ps???

P(x) ?logs?H(P1?,P2?,?,Ps?) 接着举一个例子加以说明。

例4.2.1 某对称离散信倒的信道矩阵为

??? P?????1316131616131??6?? 1??3?用公式计算信道容量

C?log4?H(,,?1?313131111,)

3366 ?2??log?log13?16log16?16log1?? 6? ?0.0817（bit/符号）

定义4.2.3 若信道矩阵Q的列可以划分成若干互不相交的子集矩阵BK，即

Bi?Bj??,(i?j)且B1?B2???Bn?Y。由BK为列组成的矩阵Qk是对称矩阵，

则称信道矩阵Q所对应的信道为准对称信道。

例如，信道矩阵

???P1?????1316131316161??6??0.7?P? ?2??0.21??3?

0.10.10.2??? 0.7?都是准对称信道，在信道矩阵P1中，Y可以划分为三个子集，由子集的列组成的矩阵为

??? ????13161??6?? ， 1??3??1????3??? ， ?1????3????????1??6?? 1??3?它们满足对称性，所以P1对应的信道是准对称信道。同理P2可划分为 ???0.7?0.20.2??? ， 0.7??0.1????? ?0.1?这两个矩阵也满足对称性。

下面，我们给出准对称离散信道的信道容量计算公式

n C?logr?H(P1?,P2?,?,Ps?)??k?1NklogMk

其中，r是输入符号集的个数，(P1?,P2?,?,Ps?)为准对称信道矩阵中的行矢量。设矩阵可划分为n个互不相交的子集。Nk是第k个子矩阵Qk中行元素之和，Mk是第k个子矩阵Qk中列元素之和，即 Nk??P?yx?

iy?Yk

Mk??P?yx?,y?Yixk,(k?1,2,?,n)

并且可以证明达到准对称离散信道容量的输入分布式等概分布，我们将推导作为习题留给读者。

例4.2.2 设信道传递矩阵为

0 0 p?1?p?qq? 1-p-q ?P???? pq1?p?q? ? q 可表示成如图4.2.2所示，计算其信道容量

p 根据上面计算公式可得

N1?1?q,N2?q p 2 M1?1?q,M2?2q q 则有

C?log2?H(1?p?q,q,p) 1-p-q 1 1 (?q)?qlog2q ?(1?q)log12(?p?q)?(1?q)log ?plogp?(1?p?q)log11?q 图4.2.2

下面我们举一些其他信道容量的例子

例4.2.3 设离散信道如图4.2.3所示，输入符号集为{a1,a2,a3,a4,a5}，输出符号集为{b1,b2}，信道矩阵为

X Y a1 a2 b1

a3 a4 b2

a5

图4.2.3

?????P?????? ?1112000??0???1?2??1??1?

a5由于输入符号a3传递到b1和b2是等概率的，所以a3可以省去。而且a1,a2与a4，

都分别传递到b1和b2，因此可只取a1和a5，所以设输入概率分布P(a1)?P(a5)?P(a2)?P(a3)?P(a4)?0，可以计算得P(b1)?P(b2)?1212，

，由定理4.2.1得

I(x?a1;Y)?I(x?a2;Y)?log2 I(x?a4;Y)?I(x?a5;Y)?log2 I(x?a3;Y)?0

可见，此假设分布满足定理4.2.1，因此，信道容量 C?log2?1 （bit/符号） 最佳分布是P(a1)?P(a5)?12,p(a2)?P(a3)?P(a4)?0

14,P(a3)?0。同理可得

若设输入分布为P(a1)?P(a2)?P(a4)?P(a5)?P(b1)?P(b2)?12，根据定理4.2.1有

I(xi;Y)?log2 (xi?a1,a2,a4,a5) I(xi;Y)?log2 (xi?x3) 从而，输入分布P(a1)?P(a2)?P(a4)?P(a5)?14,P(a3)?0也是最佳分布，可

见，信道最佳输入分布不是唯一的。

对于一般的离散信道，我们很难利用特殊计算方法，因此只能采用解方程组式（4.2.2）的方法。

我们将（4.2.2）式的前r个方程组改写成

?Q?yj?1sixi?log?yixi???Q?yj?1sixi?logP(yi)?C

(i?1,2,?,r)

移项后得

?Q?yj?1sjxi?C?logP(yj)????Q?yj?1sjxi?logQ?yjxi?

(i?1,2,?,r) 令?j?C?logP(yj)，代入上式得

?Q?yj?1sjxi??j??Q?yj?1sjxi?log?yjxi?

(i?1,2,?,r) 化为矩阵形式为

?H?Yx1????1??????H?Yx2????2? Q??????

??????????H?Yx??r??s??这是含有s个未知数?j,r个方程的非齐次线性方程组。

如果设r?s，信道矩阵Q为非奇异矩阵，则此方程组有解，并且可以求出?j的数值，然后根据?P?yj??1求得信道容量

j?1s C?log?2j?j （bit/符号）

由这个C值可解得对应的输出概论分布P(yj)。 P(yj)?2r?j?C (j?1,2,?,s)

再根据P(yj)?分布{P(xi)}。

?i?1P(xi)Q?yjxi?,j?1,2,?s,即可解出达到信道容量的最佳输入

下面给出一例。

例4.2.4 设离散无记忆信道输入X的符号集为{a1,a2,a3,a4}，输出Y的符号集为

{b1,b2,b3,b4}，如图4.2.4所示。其信道矩阵为

?????Q???????12001414100001141??4??0? 0???1??2? X Y a1 1/2 1/4 1/4

a2 1 b2 a3 1 b3

b1

1/4 1/4 a4 1/2 b4 我们才用上面所讲的方法来计算信道容量： 12?1?14?2?14?4?12log12?14log14?14log14

?2?0 ?3?0

14?1?14?3?14?4?14log14?14log14?12log12

解方程组得

?2??3?0;?1??4??2;

信道容量 C?log2(2又求得输出分布

?2?2?2?200?2)?log25?1 （bit/符号）

P(b1)?P(b4)?2 P(b3)?P(b2)?因此可以求得最佳输入分布为 P(a1)?P(a4)?(?2?log25?1)?110

410

430

P(a2)?P(a3)?1130

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

Q?y1x1?

X2 信道 2 Y2 Q?y2x2?

解 根据定理4.1.1有

2 I(X1X2;Y1Y2)??i?1I(Xi;Yi)

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

2 C1,2?maxI(X1X2;Y1Y2)?p(x1x2)?Ci?1i

Ci?maxI(Xi,Yi)，是个独立信道的信道容量。

p(xi) 只有当输入符号xi互相独立，且输入符号xi的概率分布达到各子信道容量的概率分布时，独立并联信道的信道容量才等于各信道容量之和，即

2 C1,2??Ci?1i

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

N C1,2,?,N?maxp(x1x2?xN)I(X1X2?XN;Y1Y2?YN)??Ci?1i

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

X 信道 Y Z 信道Ⅰ 信道Ⅱ

图4.2.6

则此信道容量为 C串(?,??)?maxI(X;Z)

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

0,?X???? ?????1,?P(x)??21?1? ?2?

X 二 元 对 信 Y 二 元 对 称 Z 称信 道 Ⅰ 道 Ⅱ

图4.2.7 而两个信道的信道矩阵分别为 Q1?Q2?????1?pp??? 1?p?p所以串联信道总的信道矩阵为

?(1?p)2?p2 Q?Q1?Q2????2p(1?p)2p(1?p)?? 22?(1?p)?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;Xn)?0。

n??对于本例中两个串联的二元离散对称信道，其信道容量为

C串(?,??)?maxI(X;Z)?1?H(2p(1?p)) （bit/符号）

p(x)

0,?X???? ?????1,?P(x)??21?1? ?2?

X 二 元 对 信 Y 二 元 对 称 Z 称信 道 Ⅰ 道 Ⅱ

图4.2.7 而两个信道的信道矩阵分别为 Q1?Q2?????1?pp??? 1?p?p所以串联信道总的信道矩阵为

?(1?p)2?p2 Q?Q1?Q2????2p(1?p)2p(1?p)?? 22?(1?p)?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;Xn)?0。

n??对于本例中两个串联的二元离散对称信道，其信道容量为

C串(?,??)?maxI(X;Z)?1?H(2p(1?p)) （bit/符号）

p(x)

本文来源：https://www.bwwdw.com/article/vku3.html