§4.2信道容量的计算
这里,我们介绍一般离散信道的信道容量计算方法,根据信道容量的定义,就是在固定信道的条件下,对所有可能的输入概率分布P(x)求平均互信息的极大值。前面已知I(X;Y)是输入概率分布的上凸函数,所以极大值一定存在。而I(X;Y)是r个变量
{p(x1),p(x2), p(xr)}的多元函数。并且满足∑p(xi)=1。所以可用拉格朗日乘子法来
i=1
r
计算这个条件极值。引入一个函数:φ=I(X;Y)-λ
∂φ
i∂[I(X;Y)-λ
∑p(x)解方程组
i
i
∑p(xi)]
i
ii
=0
∑p(x)=1 (4.2.1)
i
可以先解出达到极值的概率分布和拉格朗日乘子λ的值,然后在解出信道容量C。因为
r
s
I(X;Y)=∑∑p(xi)Q(yixi)log
i=1j=1
Q(yixi)
p(yi)
而p(yi)=
i∑p(x)Q(yx),所以
i
i
i
i=1
r
logp(yi)=(e=ilnp(yi))log
Q(yixi)
iloge。
解(4.2.1)式有
Q(yixi)rsQ(yixi)
Q(yixi)log-∑∑p(xi)Q(yixi)loge-λ=0 ∑p(y)p(y)j=1i=1j=1ii
s
(对i=1,2, ,r都成立) 又因为
∑p(x)Q(y
k
k=1
r
k
xk)=p(yj)
Q(y∑ j=1
s
j
xi)=1,i=1,2, ,r
所以(4.2.1)式方程组可以转化为
∑Q(yjxi)log
j=1r
s
Q(yjxi)p(yj)
=λ+loge(i=1,2, ,r)
∑p(x)=1
i
i=1
假设使得平均互信息I(X;Y)达到极值的输入概率分布{p1,p2, pr}这样有
∑∑p(xi)Q(yjxi)log
i=1j=1
rs
Q(yjxi)p(yj)
=λ+loge
从而上式左边即为信道容量,得 C=λ+loge 现在令
I(xi;Y)=
∑Q(yjxi)log
j=1
s
Q(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是任给的输入字母的一个初始概率分布,其所有分量P0(xk)≠0。按照下式不断地对概率分布进行迭代,更新:
P(xk)=P(xk)
r+1r
βk(Pr)
∑P(x)β(P)
r
r
i
i
i=1
K
r
其中 βk(P)=exp[I(X=xk;Y)]P=Pr
⎧⎫⎪Q(yjxi)⎪⎪J⎪=exp⎨∑Q(yjxk)logK⎬
r⎪j=1 PQ(yjxi)⎪ ∑⎪⎪i=1⎩⎭
由此所得的IPr,Q序列收敛于信道容量C。
我们还可以将上述过程写成算法以便编制程序实现(如图4.2.1) IL=log{
()
∑P(x)β(P)}
k
k
k=1
k
K
IU=log{maxβk(P)}
IL=IU=
图4.2.1 信道容量的迭代算法
对于一些特殊的离散信道,我们有方便的方法计算其信道容量。
定义4.2.1 设X和Y分别表示输入信源与输出信源,则我们称HX为损失熵,
()
H(YX)为信道噪声熵。
如果信道的损失熵HXY=0,则次信道容量为
()
C'=maxI(X;Y)=max(H(x)-H(X))=maxH(X)=1ogr(bit/符号)这里输入
P(x)
P(x)
P(x)
信源X的信源符号个数为r。
如果信道的噪声熵HYX=0,则此信道容量为
()
C''=maxI(X;Y)=maxH(Y)=logs(bit/符号)
P(x)
P(x)
这里输出信源符Y的符号个数为s.
定义4.2.2 一个信道Q称为对称离散信道,如果它满足下面的性质: (1)信道Q矩阵中每一行是另一行的置换; (2)每一列式另一列的置换。 例如,信道矩阵
⎛1 Q= 3
1 ⎝613161613
⎛11⎫
⎪ 26⎪11⎪和Q=
6⎪
3⎭ 1
⎝3
131216
1⎫⎪6⎪1⎪ ⎪31⎪⎪2⎭
满足对称性,所以对应信道是对称离散信道。 定义4.2.3 对称离散信道的信道容量为
'2', ,Ps') (bit/符号) C=logs-H(P1,P
'2', ,Ps'}和输出符号集的个数s有关。 上式只与対称信道矩阵中行矢量{P1,P
证明 I(X;Y)=H(Y)-HYX 而 HYX=
()
(
)∑P(x)∑P(yx)log1
pyxx
y
=
∑P(x)H(YX=x)
x
由于信道的对称性,所以HYX=x与x无关,为一常熟,即
()
'2', ,Ps')] C=max[H(Y)-H(P1,P
P(x)
'2', ,Ps') =logs-H(P1,P
接着举一个例子加以说明。
例4.2.1 某对称离散信倒的信道矩阵为
⎛1 3
P=
1 ⎝6
1316
16131⎫⎪6⎪⎪ 1⎪⎪3⎭
用公式计算信道容量
C=log4-H(,,,) =2+ log+log+ =0.0817(bit/符号)
定义4.2.3 若信道矩阵Q的列可以划分成若干互不相交的子集矩阵BK,即
11113366
⎛1⎝3
1133
11111⎫
log+log⎪ 36666⎭
Bi⋂Bj=φ,(i≠j)且B1 B2 Bn=Y。由BK为列组成的矩阵Qk是对称矩阵,
则称信道矩阵Q所对应的信道为准对称信道。
例如,信道矩阵
⎛1 3P1=
1 ⎝6
1313
16161⎫⎪6⎪⎛0.70.10.2⎫
P=⎪2 0.20.10.7⎪⎪ ⎝⎭1⎪
⎪3⎭
都是准对称信道,在信道矩阵P1中,Y可以划分为三个子集,由子集的列组成的矩阵为
⎛1 3
1 ⎝61⎫⎪6⎪⎪ , 1⎪⎪3⎭⎛1⎫ ⎪ 3⎪ ⎪ , 1⎪ ⎪⎝3⎭⎛1⎫ ⎪ 6⎪ ⎪ 1⎪ ⎪⎝3⎭
它们满足对称性,所以P1对应的信道是准对称信道。同理P2可划分为
⎛0.70.2⎫
⎪ , ⎪
⎝0.20.7⎭⎛0.1⎫ 0.1⎪⎪ ⎝⎭
这两个矩阵也满足对称性。
下面,我们给出准对称离散信道的信道容量计算公式
'2', ,Ps')- C=logr-H(P1,P
∑N
k=1
n
k
logMk
'2', ,Ps')为准对称信道矩阵中的行矢量。设矩阵可其中,r是输入符号集的个数,(P1,P
划分为n个互不相交的子集。Nk是第k个子矩阵Qk中行元素之和,Mk是第k个子矩阵Qk中列元素之和,即 Nk=
y∈Yk
∑P(yx)
i
Mk=
∑P(yx),y∈Y,(k=1,2, ,n)
i
k
x
并且可以证明达到准对称离散信道容量的输入分布式等概分布,我们将推导作为习题留给读者。
例4.2.2 设信道传递矩阵为
p⎫⎛1-p-qq⎪ P= ⎪pq1-p-q⎭⎝
可表示成如图4.2.2所示,计算其信道容量
根据上面计算公式可得
N1=1-q,N2=q M1=1-q,M2=2q 则有
2-H(1-p-q,q,p) C=log1(-q)-qlog2q -(1-q)log
=plogp+(1-p-q)log1(-p-q)+(1-q)lo下面我们举一些其他信道容量的例子
例4.2.3 设离散信道如图4.2.3所示,输入符号集为{a1,a2,a3,a4,a5},输出符号集为{b1,b2},信道矩阵为
2
图4.2.2 1-q
X Y
a a2b1
a3a4 b2
a5
图4.2.3
⎛1 1 P= 1
2 0 ⎝00⎫
⎪0⎪⎪1⎪⎪2⎪⎪1⎪⎪1⎭
由于输入符号a3传递到b1和b2是等概率的,所以a3可以省去。而且a1,a2与a4,a5都分别传递到b1和b2,因此可只取a1和a5,所以设输入概率分布P(a1)=P(a5)=
1
,2
P(a2)=P(a3)=P(a4)=0,可以计算得P(b1)=P(b2)=
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/符号)
1
,由定理4.2.1得 2
1
,p(a2)=P(a3)=P(a4)=0 2
1
若设输入分布为P(a1)=P(a2)=P(a4)=P(a5)=,P(a3)=0。同理可得
4
1
P(b1)=P(b2)=,根据定理4.2.1有
2
最佳分布是P(a1)=P(a5)=
I(xi;Y)=log2 (xi=a1,a2,a4,a5) I(xi;Y)
1
,P(a3)=0也是最佳分布,可4
见,信道最佳输入分布不是唯一的。
对于一般的离散信道,我们很难利用特殊计算方法,因此只能采用解方程组式(4.2.2)的方法。
我们将(4.2.2)式的前r个方程组改写成
∑Q(yx)log(yx)-∑Q(yx)logP(y)=C
i
i
i
i
i
i
i
j=1
j=1
ss
(i=1,2, ,r)
移项后得
∑Q(yx)[C+logP(y)]=∑Q(yx)logQ(yx)
j
i
j
j
i
j
i
j=1
j=1
ss
(i=1,2, ,r) 令βj=C+logP(yj),代入上式得
∑Q(yx)β=∑Q(yx)log(yx)
j
i
j
j
i
j
i
j=1
j=1
ss
(i=1,2, ,r) 化为矩阵形式为
⎛H(Yx1)⎫⎛β1⎫ ⎪ ⎪
H(Yx2)⎪ β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(yj)。 P(yj)=2
r
βj-C
(j=1,2, ,s)
再根据P(yj)=分布{P(xi)}。
∑P(x)Q(yx),j=1,2, s,即可解出达到信道容量的最佳输入
i
j
i
i=1
下面给出一例。
例4.2.4 设离散无记忆信道输入X的符号集为{a1,a2,a3,a4},输出Y的符号集为
{b1,b2,b3,b4},如图4.2.4所示。其信道矩阵为
⎛1 2 0 Q=
0 1 ⎝4
14100
001141⎫⎪4⎪0⎪⎪ 0⎪⎪⎪1⎪⎪2⎭
b1
X Y a1
a2 b2 a3 b3 a4 b4 我们才用上面所讲的方法来计算信道容量: 111111111β1+β2+β4=lo+lo+lo 244224444
β2=0
β3=0
111111111β1+β3+β4=lo+lo+lo 444444422
β2=β3=0;β1=β4=-2;
信道容量 C=log2(2+2+2+2)=log25-1 (bit/符号) 又求得输出分布
P(b1)=P(b4)=2 P(b3)=P(b2)=因此可以求得最佳输入分布为 P(a1)=P(a4)=
(-2-log25+1)
-200-2
=
1
10
4 104 30
P(a2)=P(a3)=
11 30
例4.2.5 设有两个独立并联信道如图4.2.5,计算它的信道容量。 X
1
Y1
Qy1x1
()
X2Y2 Qy2x2
解 根据定理4.1.1有
I(X1X2;Y1Y2)≤
()
∑I(X;Y)
i
i
i=1
2
即联合平均互信息不大于各自信道的平均互信息之和,因此得到独立并联信道的信道容量为 C1,2=maxI(X1X2;Y1Y2)≤
p(x1x2)
∑C
ii=1
2
Ci=maxI(Xi,Yi),是个独立信道的信道容量。
p(xi)
只有当输入符号xi互相独立,且输入符号xi的概率分布达到各子信道容量的概率分布时,独立并联信道的信道容量才等于各信道容量之和,即 C1,2=
∑C
ii=1
2
这个方法推广到N个独立并联信道容量的计算,即有 C1,2, ,N=
p(x1x2 xN)
maxI(X1X2 XN;Y1Y2 YN)≤∑Ci
i=1
N
对于信道Ⅰ和Ⅱ,我们将它串联起来组成新的信道(如图4.2.6)
图4.2.6
则此信道容量为 C串(I,II)=maxI(X;Z)
p(x)
例4.2.6 设有两个离散二元对称信道(BSC信道),其串联信道如图4.2.7,并设第一个信道输入符号集的概率空间为
0,1⎫⎛X⎫⎛ ⎪ P(x)⎪⎪= 1,1⎪ ⎝⎭⎝22⎭
图4.2.7
而两个信道的信道矩阵分别为
Q1=Q2= p⎝
所以串联信道总的信道矩阵为 ⎛1-pp⎫⎪ 1-p⎪⎭
⎛(1-p)2+p2
Q=Q1⋅Q2= 2p(1-p)⎝
根据平均互信息定义
I(X;Y)=1-H(p) (bit/符号)
I(X;Z)=1-H[2p(1-p)] (bit/符号) 2p(1-p)⎫⎪ 22⎪(1-p)+p⎭
其中,I(X;Y)≥I(X;Z)(根据信息不增原理)。因此,当串联信道数目越多时,损失的信息越多,可证:limI(X;Xn)=0。 n→∞
对于本例中两个串联的二元离散对称信道,其信道容量为
C串(I,II)=maxI(X;Z)=1-H(2p(1-p)) (bit/符号) p(x)