信息论实验报告.doc

前 言 信息论是现代通信与信息工程的理论基础。作为电子信息科学与技术专业本科生的学科基础课，本课程主要讲授：信息的定义和测度、信源和信息熵、连续熵和信息变差、信道和互信息、平均互信息和信道容量、数据处理和信息测量理论、无失真信源编码理论和编码方法等内容。 本课程按“单符号离散信息系统”、“多符号离散信息系统”、“连续信息系统”三个“系统”层面，逐步深入展开，以严密的数学分析贯串始终。通过教学，使学生掌握信息理论的基本概念和信息分析方法，为今后进一步研究信息科学和信息技术打下坚实的理论基础。 Sardinas－Patterson算法 三、实验原理、方法和手段 Sardinas－Patterson算法描述： 设C为码字集合，按以下步骤构造此码的尾随后缀集合F： (1) 考查C中所有的码字，若Wi是Wj的前缀，则将相应的后缀作为一个尾随后缀放入集合F0中； (2) 考查C和Fi两个集合，若Wj∈C是Wi∈Fi的前缀或Wi∈Fi 是Wj∈C的前缀，则将相应的后缀作为尾随后缀码放入集合Fi+1中； (3)F=∪Fi即为码C的尾随后缀集合； (4) 若F中出现了C中的元素，则算法终止，返回假(C不是唯一可译码)；否则若F中没有出现新的元素，则返回真。 在我们设计的算法中，需要注意的是我们需要的是先输出所有尾随后缀的集合，然后再判断该码是否是唯一可译码，即如F中出现了C中的元素，则C不是唯一可译码，否则若F中没有出现新的元素，则C为唯一可译码。而不是F中出现C中的元素就终止，这也是在本题的要求中需要注意的问题。 概要设计： 由于需要判断尾随后缀，所以我们需要反复的比较C和F中的码字。 首先我们用一个b[30][30]的数组来存放所有的尾随后缀的集合；用Q记录所有尾随后缀的个数； 用数组a[30][30]来存放输入的码字，L[30]来存放码字的长度； 通过一个双重循环并调用houzhui（a[i],a[j],L[i],L[j]）函数来找到a[30][30]中的为随后缀，即： for(i=0;in-1;i++) { for(j=0;jn;j++) { if(i!=jL[i]L[j]) HuoZhui(a[i],a[j],L[i],L[j]); } } 通过判断Q是否大于0，如果不大于0，即b[30][30]中没有码字，也就是不存在尾随后缀，那么可判断a[30][30]是唯一可译码，否则进行如下操作； 计算b[30][30]中尾随后缀的长度，用k1表示；并调用HuoZhui(b[i],a[j],k1,L[j])其中k1L[j]来a[30][30]中所存在的后缀，并加入到b[30][30]中，通过一个循环，找到a[30][30]中所有尾随后缀；即 for(i=0;iQ;i++) { k1=strlen(b[i]); for(j=0;jn;j++) { if(k1L[j]) HuoZhui(b[i],a[j],k1,L[j]); } } 寻找b[30][30]中的尾随后缀；用k2表示b[30][30]中码字的长度，并调用HuoZhui(a[i],b[j],L[i],k2)来实现，其中k2L[j];通过循环调用即可找到b[30][30]中的所有尾随后缀，最后再将他们分别存放在b[30][30]中；即通过 for(i=0;in;i++) { for(j=0;jQ;j++) { k2=strlen(b[j]); if(k2L[i]) { HuoZhui(a[i],b[j],L[i],k2); } } } 在反复调用HuoZhui(a[i],a[j],L[i],L[j])函数中如果b[30][30]中有重复出现的，即尾随后缀相同的不用再次放入b[30][30]中。 在调用函数中所需要注意的问题就是一个比较的问题，也就是实现6）中所提到的。 四，实验数据源 1： 10,0.100 2: 10,110，1110 五、实验组织运行要求 以学生自主训练为主的开放模式组织教学 六、实验条件 计算机 Windows XP VC++ 6.0 七、实验内容 １．实验源程序 #include iostream.h #include stdlib.h #include string.h struct strings { char *string; struct strings *