信息论上机实习报告

信息论上机实习报告姓名：夏勇学院：数学与物理学院专业号：123092学号：20091001897目录信息论上机实习报告.......................................................................................................................1判断唯一可译码...................................................................................................................2题目分析...........................................................................................................................2算法分析...........................................................................................................................2设计中遇到的问题及其解决方法...................................................................................3调试结果...........................................................................................................................4源代码...............................................................................................................................6香农编码.............................................................................................................................15题目分析.........................................................................................................................15算法分析.........................................................................................................................15算法中遇到的问题及解决方法.....................................................................................16调试结果.........................................................................................................................16源代码.............................................................................................................................17费诺编码.............................................................................................................................21题目分析.........................................................................................................................21算法分析.........................................................................................................................22算法设计中遇到的问题和解决方法.............................................................................22运行结果.........................................................................................................................23源代码.............................................................................................................................24判断唯一可译码题目分析1)问题描述编一个程序判断一组码是不是唯一可译码.2)基本要求利用萨德纳斯和彼特森的判断思想来编辑程序.算法分析1)算法原理由图可知，B1一定是A1的前缀，而A1的尾随后缀一定是另一码字B2的前缀；又B2的尾随后缀又是其他码字的前缀。最后，若码符号序列的尾部是码字，则其是非唯一可译码。2)算法设计和思想首先，由于在比较前缀时，码字的长度也是一个重要的量，所以需要设计一个结构体来存放码字和其长度。然后首先判断源码字中的所有的尾随后缀，运用了两个B1B2B3⋯⋯⋯BmA1A2A3⋯⋯⋯Amfor循环来实现，使得每个源码字都作为前缀和所有的其他码字比较，找出所有的尾随后缀及其长度，放在对象f中。具体判断时，如果作为前缀的码字的长度大于其他的，则剔除，判断下一个。接着，我们比较源码字和f中的码字，在这里，源码字和f中的码字都要作为前缀和其他的码字比较，找出尾随后缀码及其长度放入f中，判断方法和前面的相同。最后，比较f中的码字是否有和源码字相同的，若有，则其不是唯一可译码，否则，其是唯一可译码。设计中遇到的问题及其解决方法在起初设计中，一直不知道应该怎么比较码字来找出尾随后缀，后来仔细分析后，明白了在比较的时候牵扯到了码字的长度，既然有多个变量，那么就运用结构体变量。然后在比较的时候，就可以根据它的长度来划分它的尾随后缀码，其的长度也就知道了。在具体编程时，要避免变量在多处运用。因为如果你忘记了初始化就会导致错误，而且很难找出来，所以尽量不要多处使用，如果你一定要用的话，那就在它的后面加上标注。另外，在设计当中从老师那里学会了一种检错方法，就是一步一步的调试，虽然有点麻烦，但是效果相当不错。调试结果源代码#includestdio.h#includestring.h#includemath.h#defineN1typedefstruct{inta[20];//数据intlen;//码字长度}Code;main(){inti,j,z=0,n,b,count=0,flag=0,flag1=0,sum=0,h,m;charc[20],*p;//过渡，接收每个码字Coded[100],f[100];printf(按次序依次输入每个码字:\n);gets(c);p=c;while(*p!='\0'){if(*p=='')p++;else{i=0;while(*(p+i)!=''&&*(p+i)!='\0')i++;for(j=0;ji;j++)d[z].a[j]=p[j]-'0';d[z].len=i;z++;n=z;//码字个数p=p+i;}}/*for(i=0;in;i++){for(j=0;jd[i].len;j++)printf(%d,d[i].a[j]);printf(\n);}*///检验码字是否正确输入数组for(i=0;in;i++){for(j=i+1;jn;j++){if(d[i].len==d[j].len){for(z=0;zd[i].len;z++)if(d[i].a[z]==d[j].a[z])sum++;}if(sum==d[i].len)break;elsesum=0;}if(sum==d[i].len)break;}if(sum!=0)printf(此码组不是唯一可译码组!\n);else{for(i=0;in;i++)//前缀{for(j=0;jn;j++){if(d[j].lend[i].len||d[i].a[0]!=d[j].a[0]||d[j].len==d[i].len)continue;b=d[i].len;while(b){b--;if(d[i].a[b]==d[j].a[b])flag=1;else{flag=0;break;}}b=d[i].len;if(flag!=0){for(z=0;z(d[j].len-d[i].len);z++)f[count].a[z]=d[j].a[b+z];f[count].len=d[j].len-d[i].len;count++;//f中码字的个数}}}//在源码字里找前缀m=count;for(h=0;hN;h++)//使得f最终收敛{for(i=0;in;i++){for(j=0;jm;j++){if(d[i].len!=f[j].len){if(d[i].lenf[j].len){b=f[j].len;flag=0;while(b){b--;if(d[i].a[b]==f[j].a[b])flag=1;else{flag=0;break;}}b=f[j].len;if(flag!=0){for(z=0;z(d[i].len-f[j].len);z++)f[count].a[z]=d[i].a[b+z];f[count].len=d[i].len-f[j].len;count++;}}else{b=d[i].len;flag=0;while(b){b--;if(d[i].a[b]==f[j].a[b])flag=1;else{flag=0;break;}}b=d[i].len;if(flag!=0){for(z=0;z(f[j].len-d[i].len);z++)f[count].a[z]=f[j].a[b+z];f[count].len=f[j].len-d[i].len;count++;}}}}}}}for(i=0;in;i++)//作比较，看f中是否有源码字{for(j=0;jcount;j++){if(d[i].len==f[j].len){for(z=0;zd[i].len;z++){if(d[i].a[z]==f[j].a[z])flag1=1;else{flag1=0;break;}}}if(flag1==1){printf(此码组不是唯一可译码组!\n);break;}}if(flag1==1){printf(此码组不是唯一可译码组!\n);break;}}if(flag1==0)printf(此码组是唯一可译码组!\n);}香农编码题目分析1)问题描述用香农方法编一个程序来对各符号编码。2)基本要求需要用香农编码方法。算法分析1)算法原理首先将输入的概率