对于一般离散信道来说,信道容量的计算比较复杂。迭代计算是一种常用的近似方法。

设单符号离散信道的输入符号集X:{a1,a2,…,ar}、输出符号集Y:{b1,b2,…,bs},信道的传递概率P(Y/X):{p(bj/ai)(i=1,2,…,r;j=1,2,…,s)}。若输入符号集X:{a1,a2,…,ar}的概率分布P(X):{p(ai)(i=1,2,…,r)},则信道的平均交互信息量

是输入信源X:{a1,a2,…,ar}的概率分布P(X):{p(ai)(i=1,2,…,r)}和后验概率P(X/Y):{p(ai/bj)(i=1,2,…,r;j=1,2,…,s)}的函数

而先验概率p(ai)和后验概率p(ai/bj)不是两个独立的变量,他们之间按照如下关系式

发生相应的变化。

为了导出近似算法,暂时把后验概率p(ai/bj)当作自变量,而把本来要随之发生相应变化的应急变量p(ai)近似看作固定不变量。由于p(bj/ai)也固定不变,则(3.34)式所示的平均交互信息量I(X;Y)就可以看作是后验概率p(ai/bj)的函数

由于“底”大于1的对数是∩型凸函数,所以I [p(ai/bj)]具有上凸性。这样,就可以在条件

的约束下,对变量p(ai/bj)求∩型凸函数I [p(ai/bj)]的条件极大值,以及达到极大值的p(ai/bj)(i=1,2,…,r;j=1,2,…,s)

为此,作辅助函数

取函数F[p(ai/bj),λ]对p(ai/bj)的偏导数,并置之为零,得到稳定点方程

把式(3.34)代入式(3.39),有

即有

由约束条件式(3.38),得

则可以得到

这表明,当采用“把后验概率P(X/Y):{p(ai/bj)(i=1,2,…,r;j=1,2,…,s)}看作变量,信源X:{a1,a2,…,ar}的概率分布P(X):{p(ai)(i=1,2,…,r)}看作固定不变的量”这种近似处理的方法时,使平均交互信息量I [p(ai/bj)]达到最大值,即信道容量C的后验概率p*(ai/bj),就是信源X:{a1,a2,…,ar}的概率分布P(X):{p(ai)(i=1,2,…,r)}时,给定信道P(Y/X):{p(bj/ai)(i=1,2,…,r;j=1,2,…,s)}的一般意义下的后验概率p(ai/bj)。这是因为对给定信道P(Y/X):{p(bj/ai)(i=1,2,…,r;j=1,2,…,s)}来说,当输入信源X:{a1,a2,…,ar}的概率分布P(X):{p(ai)(i=1,2,…,r)}固定不变时,其信道的平均交互信息量I(X;Y)=I[p(ai),p(bj/ai)]只有一个确定的值,其最大值也只可能就是这唯一的确定值。达到这唯一确定值的后验概率p*(ai/bj)当然只可能就是由(3.36)式所规定的一般意义下的后验概率p(ai/bj)。所以,由(3.43)式可知,当变动后验概率p(ai/bj),而固定信源X:{a1,a2,…,ar}的概率分布P(X):{p(ai)(i=1,2,…,r)}时,信道容量

另一方面,同样可把信源X:{a1,a2,…,ar}的概率分布P(X):{p(ai)(i=1,2,…,r)}当作自变量,把本来要随之发生相应变化的应变量p(ai/bj)近似的看作是固定不变的量。在采用这种近似处理时,由于p(bj/ai)和p(ai/bj)都是固定不变,则式(3.34)所示的平均交互信息量I(X;Y)就可以看作是先验概率p(ai)的函数

由于I[p(ai)]是p(ai)的∩型凸函数,所以可在条件

的约束下,对变量p(ai)求函数I[p(ai)]的条件极大值,以及达到极大值的p*(ai)(i=1,2,…,r;j=1,2,…,s)(www.daowen.com)

为此,作辅助函数

取函数F[p(ai),λ]对p(ai)的偏导,并置之为零,得到稳定点方程

把式(3.34)代入式(3.47),有

即有

即

由约束条件式(3.45),得

即得

则可以得到

若令

由式(3.51),得

则信道容量

综上所述,式(3.44)是在信源X:{a1,a2,…,ar}的概率分布P(X):{p(ai)(i=1,2,…,r)}固定不变,变动后验概率P(X/Y):{p(ai/bj)(i=1,2,…,r;j=1,2,…,s)}的假设前提下,传递概率为P(Y/X):{p(bj/ai)(i=1,2,…,r;j=1,2,…,s)}的给定信道的信道容量C的近似迭代公式。式(3.53)是在后验概率P(X/Y):{p(ai/bj)(i=1,2,…,r;j=1,2,…,s)}固定不变,变动信源X:{a1,a2,…,ar}的概率分布P(X):{p(ai)(i=1,2,…,r)}的假设前提下,传递概率为P(Y/X):{p(bj/ai)(i=1,2,…,r;j=1,2,…,s)}的给定信道的信道容量C的近似迭代公式。实际上,由式(3.36)可知,对于传递概率固定为p(bj/ai)的给定信道,在变动后验概率p(ai/bj)时,先验概率p(ai)不可能固定不变;在变动先验概率p(ai)时,不可能后验概率p(ai/bj)固定不变。迭代计算法就是用分别单独变动p(ai/bj)和p(ai)的方法,逼近p(ai/bj)和p(ai)同时变动的实际情况,求得信道容量C的近似值。

先假定一组p(ai)(i=1,2,…,r)作为起始值,并记为p(ai)(1)(i=1,2,…,r)。把p(ai)(1)(i=1,2,…,r)作为固定值,变动p(ai/bj)(i=1,2,…,r;j=1,2,…,s)。由式(3.43)求得后验概率

由式(3.44)求得信道容量

再把由式(3.54)所得的p(ai/bj)(1)作为固定值,变动先验概率p(ai),由式(3.52)求得使平均交互信息量I[p(ai)]达到最大值的输入信源X:{a1,a2,…,ar}的概率分布

由式(3.53)求得信道容量

在实际计算中,逐段比较p(ai)(n)和p(ai)(n+1);p(ai/bj)(n)和p(ai/bj)(n+1);C(n,n)和C(n+1,n)的值。当n次迭代和(n+1)次迭代的计算值的差,已小到可以允许的程度,就可认为达到了所求信道容量值C。