ListInitiate(&head1); x2=strlen(c2);
for(s2[0]='A';s2[0]>='A'&&s2[0]<='Z';s2[0]++,num++) {
strcpy(C2.lable,s2); C2.code=num;
ListInsert(head,ListLength(head),C2); ListInsert(head1,ListLength(head1),C2); }
for(s1[0]='a';s1[0]>='a'&&s1[0]<='z';s1[0]++,num++) {
strcpy(C2.lable,s1); C2.code=num;
ListInsert(head,ListLength(head),C2); ListInsert(head1,ListLength(head1),C2); }
s1[0]='.';
strcpy(C2.lable,s1);C2.code=num++; ListInsert(head,ListLength(head1),C2);
dictionary(head,x1,c1,num); dictionary(head1,x2,c2,num);
return 0; }
五、实验结果
下面的运行结果是以例句1来进行编码和译码的，结果如图1-图4所示。
图2 例句1及其编码结果
图3 例句1编码生成的字典
图4 例句1编码后对编码后的数据进行解码的结果
图5 例句1同步解码同步生成的字典
实验二 计算信道容量
一、实验题目
写一个程序，它在输入信道转移概率矩阵后计算出信道容量。
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）