发布时间 : 星期二 文章信息论与编码实习报告更新完毕开始阅读6bcb5c6ba6c30c2258019e46
实验二 计算信道容量
一、实验题目
写一个程序，它在输入信道转移概率矩阵后计算出信道容量。
1、已知：信源符号个数X_Num、信宿符号个数Y_num、信道转移概率矩阵P。 2、输入：任意的一个信道转移概率矩阵。信源符号个数、信宿符号个数和每个具体的转移概率在运行时从键盘输入。 3、输出：信道容量C。
二、实验目的
1、理解和掌握信道容量的概念和物理意义； 2、理解一般离散信道容量的迭代算法； 3、编程实现迭代算法。
三、实验原理
1、信道容量的定义: 信道容量定义为平均互信息的最大值：C?max{I(X;Y)}。
p(X)C?maxI(X;Y)P(xj)?max??P(xj)P(yi|xj)logP(xj)j?0i?0q?1r?1P(yi|xj) P(yi)2、信道容量表征了一个信道传送信息的最大能力，实际中传送的信息量小于信道容量，否则传送过程中出现错误。
3、由信道容量的定义可知，I(X,Y)的值由信道的传送概率决定的，因而信道的传递概率决定了信道的信道容量。
四、迭代算法
1、信道容量：
C?maxI(X;Y)P(xj)?max??P(xj)P(yi|xj)logP(xj)j?0i?0q?1r?1P(yi|xj) P(yi)2、当正向传输的信道容量和反向传输的信道容量在误差范围内时表示此时信道稳定，该信道容量即为所求。
3、计算正、反向传输的信道容量的迭代算法公式如下：
ai?exp[?P(yi|xj)logjP(yi|xj)P(yi)]
cap_max?log(max(ai))
icap_result?log(?P(xi)ai)
i P(xi)??P(x)aiiP(xi)ai
i
图6 算法流程图
附：详细推导如下
C?max{I(X,Y)}?max{??PX(x)PY|X(y|x)logp(x)p(x)xyPX(x)PY|X(y|x)PX(x)?PX(x)PY|X(y|x)X}PY|X(y|x)?max{??PX(x)P}Y|X(y|x)logp(x)??P(x)P(y|x)xy?XY|XX
?max{max??PX(x)PY|X(y|x)logp(x)P(y|x)xyPX|Y(x|y)PX(x)}求信道容量C就是在Pi的约束下，求I(X;Y)的极大值。为计算方便，重写下I(X;Y)式，公式中的对数取自然数。
I(X,Y)???pipijlnijpij?ppii （1）
ij首先引入反条件概率，即
PX|Y(ai|bj)?qji （2）
则
I(X,Y)???pipijlnijqjipi （3）
迭代算法的要点是，当信道固定（即
pij固定）时，把I(X;Y)看成是pi和qji的函数，
用公式（3）进行信道容量计算的迭代。每一次迭代有两步组成：
将
pi(n)固定，在约束
?qiji?1的条件下变动；此时
qji，得到I(X;Y)的极大值，记为
I(X,Y)?C(pi(n);q(jin))?C(n,n)q(jin)?
q(jin)满足（2）式，重写为：
pi(n)pij?pi(n)ipij （4）
i(b) 将
q(jin)固定，在约束
?pi?1的条件下变动
pi，得到I(X;Y)的极大值，记为
I(X,Y)?C(pi(n?1);q(jin))?C(n?1,n)(n?1)pi；此时满足：
p
(n?1)i?ei?pijlnq(jin)j?e?pijlnq(jin)j （5）
(n)pi（4）与（5）是迭代的基本公式。先取一组（n=1）的初始值，通常选取均匀分布，
由（4）计算
q(jin)
(n?1)pi，再将此值代入（5）计算，依此反复计算下去。每次迭代都要利用
（3）计算I(X;Y)的值。可以设置门限值，当相临的两次计算值I(X;Y)小于门限值时，就结束迭代过程，此时I(X;Y)的值就是信道容量C。
可以采用下述方法，避免计算反向条件概率，使算法简化： 将（4）代入（5）得
p(n?1)i?ipi(n)e?pijln(pij/q(jn))j(n)p?ie?pijln(pij/q(jn)j （6）
其中
qj(n)??pi(n)piji （7）
将（6）（5）代入（3），得
C(pi(n?1);q(jin))?ln?pi(n)ei?pijln(pij/q(jn)j
五、实验程序
#include
#include
int X_num,Y_num; // X_num为信源个数，Y_num为信宿个数 int n=1;
double e; // 迭代法精度误差
double PXi[50]; // 输入符号的概率P(xi)数组 double P[50][50]; // 信道转移概率矩阵 double a[50];
double cap_result; double cap_max;
double result; // 信道容量
/*************************************************************** 函数名：double Calculate_a(int k,double PXi[]) 功能：计算并输出迭代法所需的参数a[k]