信息论—— - 副本

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

1、周鹏版权所有，违者必究版权所有，违者必究版权所有，违者必究版权所有，违者必究版权所有，违者必究版权所有，违者必究版权所有，违者必究版权所有，违者必究版权所有，违者必究版权所有，违者必究版权所有，违者必究版权所有，违者必究唯一可译码判决准则一、实验内容编程实现唯一可译码的判决准则―――Sardinas－Patterson算法二、实验环境1.计算机2.Windows73.VC++6.0三、实验目的1.进一步熟悉唯一可译码判决准则；1.掌握VC开发环境的使用；2.掌握C语言编程（尤其是字符串处理）四、实验要求1.提前预习实验，认真阅读实

2、验原理。2.认真高效的完成实验，实验过程中服从实验室管理人员以及实验指导老师的管理。3.认真填写实验报告。五、关于唯一可译码1、唯一可译变长码判别准则A.A.Sardinas和G.W.Patterson于1957年提出下述算法用于判断码C的唯一可译性．此算法的原理如下所示：其中Ai,Bi都是码字。可知，当且仅当某个有限长的码符号序列能译成两种不同的码字序列时，此码不是唯一可译码，此时B1一定是A1的前缀，而A1的尾随后缀一定是另一码字B2的前缀；而B2的尾随后缀又是其他码字的前缀．最后，码符号序列的尾部一定是一个码字。将码C中所有

3、可能的尾随后缀组成一个集合F，当且仅当集合F中没有包含任一码字，便可判断此码C为唯一可译变长码六、实现唯一可译码的判决准则过程1、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中的元素，则算法终止，返

4、回假(C不是唯一可译码)；否则若F中没有出现新的元素，则返回真。输入码字集合X0for所有Wi，Wj∈X0if码字Wi是码字Wj的前缀，即将相应的后缀作为一个尾随后缀放入新集合X1endifendforfor所有Wi∈X0for所有Wj∈Xn－1ifWi是Wj的前缀，即将相应的后缀作为一个尾随后缀放入新集合Xn中elseifWj是Wi的前缀，即将相应的后缀作为一个尾随后缀放入新集合Xn中endifendforendfor构造尾随后缀集合X←Xiif有码字Wi∈X0，Wi∈X，则非唯一可译码2、算法流程1.算法流程六、实验设计1、

5、数据结构本实验所需设计的程序中，码字可用如下结构体表示：2、关键算法3、函数调用关系图七、实验结果3、关键算法（判断前缀形成Fi）intjudge(char**C,intnum,int*l){intt=0,p=-1;inttemp=-1;int*k=newint[num-1];//F中第i+1行有k[i]个字符char**F;F=newchar*[num-1];for(inti=0;i<=num-1;i++){//F0形成F[i]=newchar[100];for(intj=i+1;j

6、],C[j])==0)return0;//C中有相同码字elseif(l[i]>l[j]){if(strncmp(C[i],C[j],l[j])==0){k[++p]=l[i]-l[j];t=l[i]-l[j];post(C,F,i,t,p,num);}}else{if(strncmp(C[i],C[j],l[i])==0){k[++p]=l[j]-l[i];t=l[j]-l[i];post(C,F,j,t,p,num);}}}}4、函数调用关系图判断前缀形成Fi调用judge（）主函数main（）比较C和F中有无相同项post（

7、）七、用户手册首先根据提示输入码字集合中码字的个数，然后分别输入码字六、实验结果输入6个码字：0、10、1100、1110、1011、1101，并判断出该码字集合不是唯一可译码输入5个码字：xx、xz、y、zz、xyz，判断出该码字集合是可译码。六、源程序（C++）#include#include#include//usingnamespacestd;intjudge(char**C,intnum,int*l);voidpost(char**C,char**F,intb

8、,intt,intp,intnum);voidmain(){intz;char**C;//码字集合intnum;//n行cout<<"请输入码字集合中码字个数"<>num;//输入行数int*l=newint[num];//C中