离散信道容量的迭代算法.pdfVIP

维普资讯 2006年 12月 应用数学与计算数学学报 第20卷 第 2期 Dec．，2006 COMM ．ON APPL．MATH．AND COMPUT VOi．20 No．2 离散信道容量的迭代算法 管 宇 浙江林学院应用数学系， 杭州， 311300 摘 要t引入信息量偏差概念， 给出平均交互信息量关于输入概率的增量公式， 设 计出离散信道容量线性乘法迭代和线性常系数迭代算法， ．-~qj都优于现有的指数迭代算 法． 并证明在所有单步迭代算法中它们几乎是最好的算法． 关键词。离散信道容量， 信息量偏差，迭代算法 1．引 言 设信源 (输x)x空问；P=e(x=ai)；信宿 (输出)Y空间：qj=P(Y：bj)；信 道矩阵 (条件概率)： P(y／X)：(p)×。， i，=1…．，r；J=1…．，s 输出与输入的平均交互信息量 (信息传输率)： r S z(x，l，)=∑∑PtPijl。g ／qJ】， i=lj=l 其中： log常以2或e为底， 为数学处理方便本文取e．对数中若有零则去掉相应整 个项，后面不再讨论零的问题·信道容量：c ；j{(，(，y))· 定义 1 设信息量偏差 = … ，… 其中： (nt，y)= ∑Pijlogb~j／qj】为从输入具体符号ai中获取关于输出符号 (不论是 』=1 哪一个符号)的平均交互信息量；I(X，Y)=∑piI(ai，Y)是全体 I(ai，Y)关于Pi的平 均值， dt则是每个 I(ai，Y)与I(X，Y)的偏差． 信息量偏差 的性质： (1)∑pidi：0； (2)当P0时， d=0；当P=0时， d0；i=1，2，… ，r． 注。本文字母右上角加 扣“’的均表示 I(X，Y)达到最大值时对应的各值． 本文2003年 11月21日收到． 浙江省教育厅基金资助项目(编号 维普资讯 20 应用数学与计算数学学报 20卷 信息量偏差 既是两个互信息量的差又是平均交互信息量与其偏导数的差， 它将 信息量的差与导数结合在一起， 因此可充分利用微积分来研究信道理论．本文设计 出计算离散信道容量的线性乘法和线性常系数迭代算法， 分析其与现有指数迭代算 法关系 [卜 并证明了前两者几乎是最好的单步迭代算法． 2．x(x，Y)关于 P(x)的增量公式 假设 (Pl…．，P)和 (P… ．，)是输入符号， (al…．，a)的两组概率分布，wi= P一Pi，∑Wi：0，／=∑P~pij=qJ+∑wiPlj， =一∑PljlogPij，W=max(1wil}， d=md．x{IdtI)，i=1，…，r，J=1，… ，8． 定理 1 平均交互信息量关于输入的增量公式： (，y)一(，y)：∑widi+∑ l。g = 叫t + 塞 塞 喜 = ∑ 也+1一∑qJexp(一盯∑wlp)． (1) 证明首先由于 ∑∑叫僦』l。g =∑叫t(也+(，y))=∑叫t， ：1f=1 ， ：1 ：1 (，y)_，( p~PijlogPij一 p g詈