信道容量的计算

1、i=1i=14.2信道容量的计算这里，我们介绍一般离散信道的信道容量计算方法，根据信道容量的定义，就是在固定信道的条件下，对所有可能的输入概率分布P(x)求平均互信息的极大值。前面已知I(X;Y)是输入概率分布的上凸函数，所以极大值一定存在。而I(X;Y)是r个变量p(x),p(x),p(x)的多元函数。并且满足yp(x)，1。所以可用拉格朗日乘子法来12riz=1计算这个条件极值。引入一个函数：i(x；y)-yp(x)解方程组ii0I(X;Y)Xyp(x.)4i-，03p.)dp(x.)4.2.1)yp(x)，iQ(yx)iiip(y)i可以先解出达到极值的概率分布和拉格朗日乘子的值，然后在

2、解出信道容量C。因为I(X;Y)，Hp(x)Q(yx)logi,1j,1i=1i=1i=1i=1而p(y.)，工P(x)Q(yx)，所以iiii，1dlogp(y)=(Tlnp(y)lo呂=oWGlo呂。dp(xi)idp(xi)ip(yi)解(4.2.1)式有Q(yx)logij,1Q(yx)yy(“()/Jyyp(x)Q(yx)p(y.),1izT7=1Q(yx)iiloge，0ip(y)i又因为(对i，1,2,r都成立)Yp(xk)Q(yklxk),p(yj)k,1yQ(yx)，1,i，1,2,rjj,1所以(4.2.1)式方程组可以转化为yQ(yx)logjj,1Q(yx)_j=九+l

3、oge(i=1,2,r)ip(y)j)1i=1)1i=1假设使得平均互信息I(X；Y)达到极值的输入概率分布Pi，P2,Pr这样有工工p(x)Q(ylx)logijii=1j=1从而上式左边即为信道容量，得Q(yx)jip(y)j=X+loge现在令C=XlogeI(x;Y)=工Q(yx)logijj=1x)Q(yiP(y)j式中，I(x;Y)是输出端接收到Y后获得关于X=x的信息量，即是信源符号X=x对输iii出端Y平均提供的互信息。一般来讲，I(x；Y)值与x有关。根据(4.2.2)式和(4.2.3)式,iiI(x；Y)=C(i=1,2,r)i所以对于一般离散信道有如下定理。定理4.2.1

4、般离散信道的平均互信息I(X;Y)达到极大值(即等于信道容量)的充要条件是输入概率分布p(I，P(xn)满足(a)I(xi；Y)=C对所有的xi，P(xi)0(b)I(x;Y)C对所有的x,p(x)=0iii这时C就是所求的信道容量。对于离散信道来说，其实信道容量还有一个解法：迭代解法。定理42.2设信道的向前转移概率矩阵为Q=(QW，P0是任给的输入字母的一个初始概率分布其所有分量P0(xk)0。按照下式不断地对概率分布进行迭代，更新:Pr1(x)=Pr(x)kk，Pr(x)P(Pr)iii=1其中P(Pr)=expI(X=x;Y)|kkP=PrxkQ(yxPrQyxj由此所得的IW,序列收

5、敛于信道容量C。我们还可以将上述过程写成算法以便编制程序实现(如图4.2.1)I二logP(X)(P)Lkkk=1I=logmax(P)Ukk图4.2.1信道容量的迭代算法对于一些特殊的离散信道，我们有方便的方法计算其信道容量。定义4.2.1设X和Y分别表示输入信源与输出信源，则我们称HG|Y)为损失熵,hqx)为信道噪声熵。如果信道的损失熵HGy)=0，则次信道容量为这里输入C，maxI(X;Y)，maxH(x)-H(X|Y=maxH(X)，1ogr(bit/符号)P(x)P(x)P(x)0，则此信道容量为信源X的信源符号个数为r。如果信道的噪声熵HCX)，C；，maxI(X;Y)=maxH

6、(Y)，logs(bit/符号)P(x)P(x)这里输出信源符Y的符号个数为s.定义4.2.2一个信道Q称为对称离散信道，如果它满足下面的性质信道Q矩阵中每一行是另一行的置换；每一列式另一列的置换。例如，信道矩阵(1316131616131613丿(121613131216161312丿所以对应信道是对称离散信道。满足对称性定义4.2.3对称离散信道的信道容量为C，logsH(P,P,P)(bit/符号)12s上式只与対称信道矩阵中行矢量P；P,P和输出符号集的个数s有关。12证明I(X;Y)，H(Y)-HG|X)而H(Y|X)，P(x)Pxhgx，P(x)HCx，x)由于信道的对称性，所以H

7、EX，x丿与x无关，为一常熟，即C，maxh(Y)-H(P；P,P)P(x)12s，logs-H(P,P,P)12s接着举一个例子加以说明。例4.2.1某对称离散信倒的信道矩阵为用公式计算信道容量C=窗一H（il，6,6）c11E1E1E1二2+3lOg3+3lOg3+6lOg6+6lOg6,=0.0817（bit/符号）定义4.2.3若信道矩阵Q的列可以划分成若干互不相交的子集矩阵Bk，即例如，信道矩阵r11113366P=111116363丿12则称信道矩阵Q所对应的信道为准对称信道。0.70.10.20.10.20.7丿BnB=,(i丰j)且BB-B=Y。由B为列组成的矩阵Q是对称矩阵,

8、ij都是准对称信道，在信道矩阵P中，Y可以划分为三个子集，由子集的列组成的矩阵1为r11r1r1363611，1，163丿3丿3丿它们满足对称性，所以p对应的信道是准对称信道。同理匚可划分为0.70.2（0.1、0.20.7丿，0.1丿这两个矩阵也满足对称性。下面，我们给出准对称离散信道的信道容量计算公式C二logr-H（P；P；,P）-工NlogM12skkk=1其中，r是输入符号集的个数，(p;p;,P)为准对称信道矩阵中的行矢量。设矩阵可划分为n个互不相交的子集。N是第k个子矩阵Q中行元素之和，M是第k个子矩kkk阵Q中列元素之和，即k=工P（y|x）4545M，PQx)ygY,(k，1

9、,2,n)kikx并且可以证明达到准对称离散信道容量的输入分布式等概分布，我们将推导作为习题留给读者。例4.2.2设信道传递矩阵为P,卩_p_qqp、Ipqi-p-q丿可表示成如图4.2.2所示，计算其信道容量根据上面计算公式可得N，1-q,N，qi2M，1-q,M，2q12则有C，log2H(1pq,q,p)(1q)log1(-q)qlog2q01-p-qqP2Pq1-p-q11图4.2.2plogp+(1一p-q)log1(-p-q)+(1一q)lo下面我们举一些其他信道容量的例子例4.2.3设离散信道如图4.2.3所示，输入符号集为a,a,a,a,a，输出符号12345集为b,b，信道矩

10、阵为12XY图4.2.3iiiiiiiiP=11220101丿由于输入符号a传递到b和b是等概率的，所以a可以省去。而且a,a与a,a31231245都分别传递到b和b，因此可只取a和a，所以设输入概率分布P(a)=P(a)=1，1215152P(a)=P(a)=P(a)=0,可以计算得P(b)=P(b)=1，由定理4.2.1得234122I(x=a;Y)=I(x=a;Y)=log212I(x=a;Y)=I(x=a;Y)=log245I(x=a;Y)=03可见，此假设分布满足定理4.2.1，因此，信道容量C=log2=1(bit/符号)最佳分布是P(a)=P(a)=,p(a)=P(a)=P(a

11、)=0TOC o 1-5 h z152234若设输入分布为P(a)=P(a)=P(a)=P(a)=,P(a)=0。同理可得124543P(b)=P(b)=，根据定理4.2.1有122I(x;Y)=log2(x=a,a,a,a)ii1245I(x;Y)log2(x=x)ii3从而，输入分布P(a)=P(a)=P(a)=P(a)=,P(a)=0也是最佳分布，可124543见，信道最佳输入分布不是唯一的。对于一般的离散信道，我们很难利用特殊计算方法，因此只能采用解方程组式(4.2.2)的方法。我们将(422)式的前r个方程组改写成ogP(y)=CiQ(yxhg(yx)-Q(yx)j=1j=1(i=1

12、,2,r)移项后得jij1+logP(yjj1x4ogQyxi:)i(i1,2,r)令P=C+logP(y)，代入上式得jjQCx)3=QCx)ogCx)jijjijij=1(i=1,2,r)化为矩阵形式为P1P2P丿sHC|x)丿r/这是含有s个未知数卩，r个方程的非齐次线性方程组。j如果设r=s，信道矩阵Q为非奇异矩阵，则此方程组有解，并且可以求出P的数j值，然后根据乙P丿1求得信道容量jj=1C=log2pj(bit/符号)j由这个C值可解得对应的输出概论分布p(y)。jP(y)=2Pj-C(j=1,2,s)j再根据P(y)=P(x)Qlx)j=1,2,s,即可解出达到信道容量的最佳输入

13、jijii=1分布P(x)。i下面给出一例。例4.2.4设离散无记忆信道输入X的符号集为a1，a2,a3,a4，输出Y的符号集为b1，b2,b3,b4，如图4.2.4所示。其信道矩阵为1/41/41/21/41/41/2】log我们才用上面所讲的方法来计算信道容量：2卩广4卩2+4卩4=2log2+410卜4P031n1n1n-1-1-1p+n+n=io片+io片+iog-4尸14尸34尸44审4审2违解方程组得叮卩3二0；叮卩47（bit/符号）信道容量Clog(2-2+2o+2o+2-2)=log5122又求得输出分布P(b)P(b)2(-2-iog25+1)丄TOC o 1-5 h z1

14、42104P(b)P(b)-3210因此可以求得最佳输入分布为4P(a)P(a)-1/30例4.2.5P(a2)空)j0设有两个独立并联信道如图4.2.5，计算它的信道容量。*信道1Q9x*信道2Q*X解根据定理4.1.1有I(XX;YY)LI(X;Y)1212iii1即联合平均互信息不大于各自信道的平均互信息之和，因此得到独立并联信道的信道容量为CmaxI(XX;YY)C1,21212iCmaW(X,Y)，是个独立信道的信道容量。iii只有当输入符号x互相独立，且输入符号x的概率分布达到各子信道容量的概率分布ii时，独立并联信道的信道容量才等于各信道容量之和，即C工C1,2ii1这个方法推广到N个独立并联信道容量的计算，即有CmaxI(XXX;YYY)1Lc1,2,N12N12Nip(x1x2xN)i1对于信道I和II,我们将它串联起来组成新的信道(如图)X.信道IY_&辛口Zr信道IIP1口宀丄丄图4.2.6则此信道容量为C(I)maxI(X;Z)串p(x)例4.2.6设有两个离散二元对称信道(BSC信道)，其串联信道如图4.2.7,并设第一