第一组信道容量的迭代算法

信道容量的迭代算法组长：20090710107胡思宇组员：20090710611蒙晶20090710902樊璐20090710904傅予20090710928郑国盛20090711022夏阳20090711201卜红丽信道容量的迭代算法[键入文字]信道容量的迭代算法目录信道容量的迭代算法........................................................................................................................1目录...................................................................................................................................................1一、指数迭代......................................................................................................................................2原理：..............................................................................................................................................2程序流程图：..................................................................................................................................3计算结果示例：..............................................................................................................................3二、线性乘法迭代..............................................................................................................................6原理：..............................................................................................................................................6程序流程图：..................................................................................................................................7计算结果示例：..............................................................................................................................7三、算法对比......................................................................................................................................8时间复杂度：..................................................................................................................................8空间复杂度：两个算法的空间复杂度差别不大。....................................................................10四、附件（源程序及其它）..........................................................................................................11指数迭代：....................................................................................................................................11指数迭代（C语言版）：...............................................................................................................13线性乘法迭代：............................................................................................................................15成员分工说明书:..............................................................................................................................18信道容量的迭代算法[键入文字]一、指数迭代原理：由平均互信息的定义可知：XYjijijibPabPabPaPYXI)()|(log)|()();(所以得到平均互信息与输入分布概率和反向传递概率的关系：risjijiijiaPbaPabPaPI11)()|(log)|()()φP,(其中：输入概率：)(iaP反向传递概率：)|(jibaP假设输入概率给定，令偏导数为零得到最优的反向传递概率为：riijiijijiabPaPabPaPbaP1*)|()()|()()|(假设反向传递概率给定，令偏导数为零得到最优输入概率：iriiiiiaPaPaP1*)()()(其中：])|()()|(ln)|(exp[11sjriijiijijiabPaPabPabP★在反向传递概率与输入概率中每次固定一个求另一个的最佳值，如此交替迭代从而逼近平均互信息的最大值，即信道容量。信道容量的迭代算法[键入文字]程序流程图：计算结果示例：示例一：信道容量的迭代算法[键入文字]示例说明：所用矩阵为题目给定的第一个矩阵，精度：1E-6第一个返回值是每一步得到的信道容量，第二个返回值是最后的输入概率分布，第三个返回值是每一步的用时，第四个返回值是运算的步长（迭代次数）示例二：（节选部分结果）......示例说明：所用矩阵为题目给定的第二个矩阵其余同示例一信道容量的迭代算法[键入文字]示例三：（C语言版矩阵一）示例四（C语言版矩阵二）信道容量的迭代算法[键入文字]二、线性乘法迭代原理：以输入作为唯一变量，以泰勒级数展开可得到平均互信息关于输入概率分布的增量公式：sjjjjriiiqqqdYXIYXI11'log');();('进一步转化得：)exp(1);();('1111riijijsjjriiiPqqdYXIYXI其中：增加前的平均互信息：);(YXI增加后的平均互信息：);('YXI增加前的信息量偏差：sjijijijiYXIPYXIYXIqPPd11);();();(log增加前后的输入概率：iP'iP信道转移概率：ijP输出概率：jq'jq输入概率的增量：i★选取合适的i使);(YXI单调递增从而逼近最大值即信道容量。i的实际选取方法如下：设iiidtP取21hht其中：riiidPh11sjkriijiijPPdqqhj1112)(信道容量的迭代算法[键入文字]程序流程图：计算结果示例：示例一：NY函数声明设初值结束输出结果与计时时间I(X,Y)-IË令I=I(X,Y)计算I(X,Y)并计时开始信道容量的迭代算法[键入文字]示例说明：使用题目给定矩阵一精度：1E-6C:各步计算出的信道容量的逼近值；P_x:最终的输入概率分布T_a:个不计算的时间;T_d:总迭代次数示例二：示例说明：使用题目给定矩阵一其余同示例一三、算法对比时间复杂度：按时间收敛：矩阵一：信道容量的迭代算法[键入文字]矩阵二：按步长收敛：矩阵一信道容量的迭代算法[键入文字]矩阵二：结论：从迭代次数的角度来说，简单的传递矩阵迭代后两种差距并不明显，一旦传递矩阵的规模扩大，线性乘法迭代达到计算精度所用的次数明显比指数迭代少。但是从计算速度的角度来说，指数迭代比线性乘法迭代更快达到要求。空间复杂度：两个算法的空间复杂度差别不大。信道容量的迭代算法[键入文字]四、附件（源程序及其它）指数迭代：%=========================================================%FileName:(文件名：)%II2CC.m%Author:（作者：你改动了文件就在后面加名字）%FuYu(傅予)%SamHu([e-mail])(胡思宇)%FunctionTable:（函数表：）%[]=II2CC()（函数声明）%{%Function:ApproachChannelCapacity%(功能：逼近信道容量)%Method:IndexIteration%(方法：指数迭代)%}%%TestEnvironment:（测试环境：）%Win7/Matlab7.8.0/7.10.0（傅予/胡思宇）%ModificationHistory:（文件修改的记录：做了啥改动啥时候）%Builtin2011/12/16by傅予；%Modifiedin2011/12/18by胡思宇；%=========================================================function[IL,p,T_a,n]=II2CC(p_yx,Tol)%====I/OTable====（输入输出表）%Input:%--p_yx:ProbabilityofChannelTransition(信道转移矩阵)%--Tol:Tolerance(误差容限)%Output:%--IL:ApproximatevalueofChannelCapacity(近似结果)%--p:ProbabilityofInputVector(输入向量)%--T_a:EvaluationofTimeconsumption(算法时间)%--n:Steps(迭代次数/步长)%==EndofI/OTable==[N,M]=size(p_yx);s=zeros(N,1);d=zeros(N,1);p=zeros(N,1);q=zeros(M,1);a=zeros(N,1);T_a=zeros(2,1);信道容量的迭代算法[键入文字]%DefaultTolerance:1E-6(误差容限默认为1*10^-6)ifnargin2Tol=1E-6;endfori=1:N%各行概率累加求和s(i)=0;forj=1:Ms(i)=s(i)+p_yx(i,j)