欢迎来到天天文库
浏览记录
ID:42503435
大小:339.73 KB
页数:12页
时间:2019-09-16
《信息论上机实习报告》由会员上传分享,免费在线阅读,更多相关内容在工程资料-天天文库。
1、信息论上机实习报告(2011年11月)姓名:钱利明学号:20091002413班序号:123092—19院系:数学与物理学院专业:信息与计算科学授课教师:余林琛唯一可译码1、问题描述:在我们学习使用了克拉夫特不等式之后,知道唯一可以码必须满足克拉夫特不等式。但是克拉夫特不等式仅仅是存在性的判定定理,即该定理不能作为判断一种码是否为唯一可译码的依据。也就是说当码字长度和码符号数满足克拉夫特不等式时,则必可以构造出唯一可译码,否则不能构造出唯一可译码。因此我们必须找到一种能够判断一种码是否为唯一可译码的方法…Sardinas—Patterson算法。2、需求分析:Sardinas—Patte
2、rson算法描述:设C为码字集合,按以下步骤构造此码的尾随后缀集合(1)考查C中所有的码字,若皿是呵的前缀,则将相应的后缀作为一个尾随后缀放入集合F0屮;(2)考查C和刃两个集合,若Wj^C是W/WFi的前缀或WieFZ是Wj^C的前缀,则将相应的后缀作为尾随后缀码放入集合刃+/中;⑶F=UFi即为码C的尾随后缀集合;(4)若F中出现了C中的元素,则算法终止,返回假(C不是唯一可译码);否则若F中没有11!现新的元素,则返回真。在我们设计的算法中,需要注意的是我们需要的是先输出所有尾随后缀的集合,然后再判断该码是否是唯一可译码,即如F中岀现了C中的元素,则C不是唯一可译码,否则若F屮没有
3、岀现新的元素,则C为唯一可译码。而不是F屮出现C屮的元素就终止,这也是在本题的要求中需要注意的问题。3、概要设计:由于需要判断尾随后缀,所以我们需要反复的比较C和F中的码字。1)首先我们用一个b[30][30]的数组來存放所有的尾随后缀的集合;用Q记录所有尾随后缀的个数;2)用数组a[30][30]来存放输入的码字,L[30]来存放码字的长度;通过一个双重循环并调用houzhui(a[i],a[j],L[i],LLi])函数来找到a[30][30]屮的为随后缀,即:for(i=0;i4、(a[i],a[j],L[i],L[j]);}}3)通过判断Q是否大于0,如果不大于0,即b[30][30]屮没有码字,也就是不存在尾随后缀,那么可判断aL30Jl30]>唯一可译码,否则进行如下操作;4)计算b[30][30]中尾随后缀的长度,用kl表示;并调用HouZhui(b[i],a[j],kl,L[j])其中kl5、j])HouZhui(b[i]6、,a7、j],kl,L[j]);}}1)寻找b[3O][3O]中的尾随后缀;用k2表示b[30][30]中码字的长度,并调用HouZhui(a[i],b[j],L[i],k2)来实现,其中k2>L[j];通过循环调用即可找到b[30][30冲的所有尾随后缀,最后再将他们分别存放在b[30]f30冲;即通过for(i=0;iL[i]){HouZhui(a[i],b[j],L[i],k2);2)在反复调用HouZhui(a[i],a[j],L[i],L8、jD函数中如果b[30][30]中有重复出现的,9、即尾随后缀相同的不用再次放入b[3O][3O]中。3)在调用函数屮所需要注意的问题就是一个比较的问题,也就是实现6)中所提到的。4.详细程序如下:#include#includecharb[3O][3O];intQ;voidHouZhui(charc[],chard[],intLI,intL2){inti,j,temp=0;charm[30];fbr(i=O;i10、++){if(strcmp(b[i],m)==O){temp=1;break;}}if(temp!=l){strcpy(b[QJ,m);Q++;voidmain(){inti,j,k,kl,k2,n;chara[3O][3O];intL13OJ;inttemp=1;intmm=0;printfC*请输入码字个数:”);scanf(”%d",&n);printfC*请分别输入码字:”);for(i=0;i
4、(a[i],a[j],L[i],L[j]);}}3)通过判断Q是否大于0,如果不大于0,即b[30][30]屮没有码字,也就是不存在尾随后缀,那么可判断aL30Jl30]>唯一可译码,否则进行如下操作;4)计算b[30][30]中尾随后缀的长度,用kl表示;并调用HouZhui(b[i],a[j],kl,L[j])其中kl5、j])HouZhui(b[i]6、,a7、j],kl,L[j]);}}1)寻找b[3O][3O]中的尾随后缀;用k2表示b[30][30]中码字的长度,并调用HouZhui(a[i],b[j],L[i],k2)来实现,其中k2>L[j];通过循环调用即可找到b[30][30冲的所有尾随后缀,最后再将他们分别存放在b[30]f30冲;即通过for(i=0;iL[i]){HouZhui(a[i],b[j],L[i],k2);2)在反复调用HouZhui(a[i],a[j],L[i],L8、jD函数中如果b[30][30]中有重复出现的,9、即尾随后缀相同的不用再次放入b[3O][3O]中。3)在调用函数屮所需要注意的问题就是一个比较的问题,也就是实现6)中所提到的。4.详细程序如下:#include#includecharb[3O][3O];intQ;voidHouZhui(charc[],chard[],intLI,intL2){inti,j,temp=0;charm[30];fbr(i=O;i10、++){if(strcmp(b[i],m)==O){temp=1;break;}}if(temp!=l){strcpy(b[QJ,m);Q++;voidmain(){inti,j,k,kl,k2,n;chara[3O][3O];intL13OJ;inttemp=1;intmm=0;printfC*请输入码字个数:”);scanf(”%d",&n);printfC*请分别输入码字:”);for(i=0;i
5、j])HouZhui(b[i]
6、,a
7、j],kl,L[j]);}}1)寻找b[3O][3O]中的尾随后缀;用k2表示b[30][30]中码字的长度,并调用HouZhui(a[i],b[j],L[i],k2)来实现,其中k2>L[j];通过循环调用即可找到b[30][30冲的所有尾随后缀,最后再将他们分别存放在b[30]f30冲;即通过for(i=0;iL[i]){HouZhui(a[i],b[j],L[i],k2);2)在反复调用HouZhui(a[i],a[j],L[i],L
8、jD函数中如果b[30][30]中有重复出现的,
9、即尾随后缀相同的不用再次放入b[3O][3O]中。3)在调用函数屮所需要注意的问题就是一个比较的问题,也就是实现6)中所提到的。4.详细程序如下:#include#includecharb[3O][3O];intQ;voidHouZhui(charc[],chard[],intLI,intL2){inti,j,temp=0;charm[30];fbr(i=O;i10、++){if(strcmp(b[i],m)==O){temp=1;break;}}if(temp!=l){strcpy(b[QJ,m);Q++;voidmain(){inti,j,k,kl,k2,n;chara[3O][3O];intL13OJ;inttemp=1;intmm=0;printfC*请输入码字个数:”);scanf(”%d",&n);printfC*请分别输入码字:”);for(i=0;i
10、++){if(strcmp(b[i],m)==O){temp=1;break;}}if(temp!=l){strcpy(b[QJ,m);Q++;voidmain(){inti,j,k,kl,k2,n;chara[3O][3O];intL13OJ;inttemp=1;intmm=0;printfC*请输入码字个数:”);scanf(”%d",&n);printfC*请分别输入码字:”);for(i=0;i
此文档下载收益归作者所有