信息论与编码 - 副本

《信息论与编码 - 副本》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、信息论---课程设计报告班级：192081-12指导老师：余林琛姓名：熊松学号：20081002220实习地点：信息楼810实习日期：2010年10月一、唯一可译码1、问题描述：在我们学习使用了克拉夫特不等式之后，知道唯一可译码必须满足克拉夫特不等式。但是克拉夫特不等式仅仅是存在性的判定定理，即该定理不能作为判断一种码是否为唯一可译码的依据。也就是说当码字长度和码符号数满足克拉夫特不等式时，则必可以构造出唯一可译码，否则不能构造出唯一可译码。因此我们必须找到一种能够判断一种码是否为唯一可译码的方法---Sard

2、inas－Patterson算法。2、需求分析：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中没有出现新的元素，则

3、返回真。在我们设计的算法中，需要注意的是我们需要的是先输出所有尾随后缀的集合，然后再判断该码是否是唯一可译码，即如F中出现了C中的元素，则C不是唯一可译码，否则若F中没有出现新的元素，则C为唯一可译码。而不是F中出现C中的元素就终止，这也是在本题的要求中需要注意的问题。3、概要设计：由于需要判断尾随后缀，所以我们需要反复的比较C和F中的码字。1）首先我们用一个b[30][30]的数组来存放所有的尾随后缀的集合；用Q记录所有尾随后缀的个数；2）用数组a[30][30]来存放输入的码字，L[30]来存放码字的长度；

4、通过一个双重循环并调用houzhui（a[i],a[j],L[i],L[j]）函数来找到a[30][30]中的为随后缀，即：for(i=0;i

5、oZhui(b[i],a[j],k1,L[j])其中k1

6、中k2>L[j];通过循环调用即可找到b[30][30]中的所有尾随后缀，最后再将他们分别存放在b[30][30]中；即通过for(i=0;iL[i]){HuoZhui(a[i],b[j],L[i],k2);}}}2）在反复调用HuoZhui(a[i],a[j],L[i],L[j])函数中如果b[30][30]中有重复出现的，即尾随后缀相同的不用再次放入b[30][30]中。3）在调用函数中所需要注意的问题就是一个比较

7、的问题，也就是实现6）中所提到的。4详细设计如下：#include#includecharb[30][30];intQ;voidHuoZhui(charc[],chard[],intL1,intL2){inti,j,temp=0;charm[30];for(i=0;i

8、