信息论与编码课程设计报告.doc

信息论与编码课程设计报告姓名:时旭东专业:电科10-01学号:3**********指导老师:成凌飞完成日期:。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。,使学生进一步巩固信源熵、信源编码的基本原理,掌握具体的编码方法,熟悉编程软件的使用,培养学生自主设计、编程调试的开发能力,同时提高学生的实践创新能力。::利用尾随后缀法判断任意输入的码是否为唯一可译码。:设计一个程序实现判断输入码组是否为唯一可译码这一功能。在我们学****使用了克劳夫特不等式之后,知道唯一可译码必须满足克劳夫特不等式。但是克劳夫特不等式仅仅是存在性的判定定理,即该定理不能作为判断一种码是否为唯一可译码的依据。也就是说当码字长度和码符号数满足克劳夫特不等式时,则必可以构造出唯一可译码,否则不能构造出唯一可译码。因此我们必须找到一种能够判断一种码是否为唯一可译码的方法—尾随后缀法。:尾随后缀法算法描述:设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中的元素就终止,这也是在本题的要求中需要注意的问题。简明流程图开始输入码字个数和码字进行尾随后缀编码判断是否为唯一码调用main():由于需要判断尾随后缀,所以我们需要反复的比较C和F中的码字。首先我们用一个b[40][40]的数组来存放所有的尾随后缀的集合;用Q记录所有尾随后缀的个数;用数组a[40][40]来存放输入的码字,L[50]来存放码字的长度;通过一个双重循环并调用Hz(a[i],a[j],L[i],L[j])函数来找到a[40][40]中的为随后缀,即:for(i=0;i<n-1;i++) { for(j=0;j<n;j++) { if(i!=j&&L[i]<L[j]) Hz(a[i],a[j],L[i],L[j]); } }通过判断Q是否大于0,如果不大于0,即b[40][40]中没有码字,也就是不存在尾随后缀,那么可判断a[40][40]是唯一可译码,否则进行如下操作;计算b[40][40]中尾随后缀的长度,用k1表示;并调用Hz(b[i],a[j],k1,L[j])其中k1<L[j]来a[40][40]中所存在的后缀,并加入到b[40][40]中,通过一个循环,找到a[40][40]中所有尾随后缀;即for(i=0;i<Q;i++) { k1=strlen(b[i]); for(j=0;j<n;j++) { if(k1<L[j]) Hz(b[i],a[j],k1,L[j]); } }寻找b[40][40]中的尾随后缀;用k2表示b[40][40]中码字的长度,并调用Hz(a[i],b[j],L[i],k2)来实现,其中k2>L[j];通过循环调用即可找到b[40][40]中的所有尾随后缀,最后再将他们分别存放在b[40][40]中;即通过for(i=0;i<n;i++) { for(j=0;j<Q;j++) { k2=strlen(b[j]); if(k2>L[i]) { Hz(a[i],b[j],L[i],k2); } } }在反复调用Hz(a[i],a[j],L[i],L[j])函数中如果b[40][40]中有重复出现的,即尾随后缀相同的