《信息论上机实习报告(共27页).docx》由会员分享，可在线阅读，更多相关《信息论上机实习报告(共27页).docx（27页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、精选优质文档-倾情为你奉上信息论上机实习报告姓名：夏勇 学院：数学与物理学院 专业号： 学号：目录判断唯一可译码题目分析1) 问题描述编一个程序判断一组码是不是唯一可译码.2) 基本要求 利用萨德纳斯和彼特森的判断思想来编辑程序.算法分析1) 算法原理B1B2B3BmA1A2A3Am由图可知，B1一定是A1的前缀，而A1的尾随后缀一定是另一码字B2的前缀；又B2的尾随后缀又是其他码字的前缀。最后，若码符号序列的尾部是码字，则其是非唯一可译码。2) 算法设计和思想首先，由于在比较前缀时，码字的长度也是一个重要的量，所以需要设计一个结构体来存放码字和其长度。然后首先判断源码字中的所有的尾随后缀，运
2、用了两个for循环来实现，使得每个源码字都作为前缀和所有的其他码字比较，找出所有的尾随后缀及其长度，放在对象f中。具体判断时，如果作为前缀的码字的长度大于其他的，则剔除，判断下一个。接着，我们比较源码字和f中的码字，在这里，源码字和f中的码字都要作为前缀和其他的码字比较，找出尾随后缀码及其长度放入f中，判断方法和前面的相同。最后，比较f中的码字是否有和源码字相同的，若有，则其不是唯一可译码，否则，其是唯一可译码。设计中遇到的问题及其解决方法在起初设计中，一直不知道应该怎么比较码字来找出尾随后缀，后来仔细分析后，明白了在比较的时候牵扯到了码字的长度，既然有多个变量，那么就运用结构体变量。然后在比
3、较的时候，就可以根据它的长度来划分它的尾随后缀码，其的长度也就知道了。在具体编程时，要避免变量在多处运用。因为如果你忘记了初始化就会导致错误，而且很难找出来，所以尽量不要多处使用，如果你一定要用的话，那就在它的后面加上标注。另外，在设计当中从老师那里学会了一种检错方法，就是一步一步的调试，虽然有点麻烦，但是效果相当不错。调试结果源代码#include#include#include#define N 1typedef structint a20;/数据int len;/码字长度Code;main()int i,j,z=0,n,b,count=0,flag=0,flag1=0,sum=0,h,m
4、;char c20,*p;/过渡，接收每个码字Code d100,f100;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+)dz.aj=pj-0;dz.len=i;z+;n=z;/码字个数p=p+i;/*for(i=0;in;i+)for(j=0;jdi.len;j+)printf(%d,di.aj);printf(n);*/检验码字是否正确输入数组for(i=0;in;i+)for(j=i+1;jn;j+)if(di.
5、len=dj.len)for(z=0;zdi.len;z+)if(di.az=dj.az)sum+;if(sum=di.len) break;else sum=0;if(sum=di.len)break;if(sum!=0) printf(此码组不是唯一可译码组!n);else for(i=0;in;i+)/前缀for(j=0;jn;j+)if(dj.lendi.len|di.a0!=dj.a0|dj.len=di.len)continue;b=di.len;while(b) b-;if(di.ab=dj.ab) flag=1;elseflag=0;break;b=di.len;if(flag
6、!=0)for(z=0;z(dj.len-di.len);z+)fcount.az=dj.ab+z;fcount.len=dj.len-di.len;count+;/f中码字的个数/在源码字里找前缀m=count;for(h=0;hN;h+)/使得f最终收敛for(i=0;in;i+)for(j=0;jfj.len)b=fj.len;flag=0;while(b) b-;if(di.ab=fj.ab) flag=1;elseflag=0;break;b=fj.len;if(flag!=0)for(z=0;z(di.len-fj.len);z+)fcount.az=di.ab+z;fcount.
7、len=di.len-fj.len;count+;elseb=di.len;flag=0; while(b)b-;if(di.ab=fj.ab) flag=1;elseflag=0;break;b=di.len;if(flag!=0)for(z=0;z(fj.len-di.len);z+)fcount.az=fj.ab+z;fcount.len=fj.len-di.len;count+;for(i=0;in;i+)/作比较，看f中是否有源码字for(j=0;jcount;j+)if(di.len=fj.len)for(z=0;zdi.len;z+)if(di.az=fj.az) flag1=1
8、;elseflag1=0;break;if(flag1=1) printf(此码组不是唯一可译码组!n);break;if(flag1=1) printf(此码组不是唯一可译码组!n);break;if(flag1=0) printf(此码组是唯一可译码组!n);香农编码题目分析1) 问题描述用香农方法编一个程序来对各符号编码。2) 基本要求需要用香农编码方法。算法分析1) 算法原理首先将输入的概率按递减的次序排列，然后计算累加概率Fi=k=1i-1pk，接着计算每个符号的码字的长度li，它应该是不小于log2pi的最小整数。最后将每个符号对应的累加概率转变成二进制的数，码字就取其二进制数的前
9、li位。这样就得到了每个符号的码字。2) 算法设计思想array函数用来把输入的概率按递减的次序排列好，用的方法是先找最大的放第一个，再找次大的放第二个，如此反复。chang函数用来把累加函数由十进制变到二进制，在函数中，一位一位的比较，比较了一位，就用累加函数值减去此位的数0或1的2i倍，i表示是第几位。算法中遇到的问题及解决方法由于香农编码比较的简单，所以在编码时基本上没有什么问题，只要把chang函数编好就行。调试结果源代码#include#include#includeint k100;int c100;void array(double a,int n)/排序int i,j;doub
10、le m;for(i=0;in;i+)for(j=i;jn;j+)if(aiaj)m=ai;ai=aj;aj=m;void chang(double p,int l)int i,j=0,z=2; for(i=0;i100;i+)/初始化ci=-1;if(p=0)for(i=0;il;i+)ci=0;elsefor(i=0;i=1.0/z) cj+=1;p-=1.0/z;z*=2;else cj+=0;z*=2;main()double a100,b100,sum=0.0,m;int n,i,j;printf(请输入信源符号的个数: n);scanf(%d,&n);doprintf(请依次输入各
11、信源符号的概率: n);for(i=0;in;i+)scanf(%lf,&ai);for(i=0;in;i+)sum+=ai;while(sum!=1);/检验概率和是否是1array(a,n); b0=0.0;for(i=1;in;i+)bi=bi-1+ai-1;/累加for(i=0;ij&m=j+1)ki=j+1;break;for(i=0;i100;i+)/初始化ci=-1;printf(按概率降序排列码字依次为: );for(i=0;in;i+)printf(%.3f ,ai);printf(n);for(i=0;in;i+)printf(该码字对应累加概率为: %.3f 该码字码长为
12、: %d ,bi,ki);chang(bi,ki);printf(码字为: );for(j=0;jki;j+)printf(%d,cj);printf(n);费诺编码题目分析1) 问题描述对于给定的概率，按照费诺编码方法编码。2) 基本要求按照费诺编码方法编码。算法分析1) 算法基本原理首先，将信源符号以概率递减的次序排列起来，将排列好的信源符号划分成两大组，使每组的概率和近于相同，并各赋予一个二元码符号“0”，“1”。然后，将每一大组的信源符号再分成两组，使同一组的两个小组的概率和近于相同，并又分别赋予一个二元码符号。依次下去，直到每小组只剩一个信源符号为止。这样，信源符号所对应的码符号序列
13、则为编得的码字。2) 算法设计思想首先，也要编一个array函数来排列概率，这与上面的香农编码相同。在这个设计中，主要是运用了一个递归算法来划分概率组，先定义起点和终点，然后按照概率相近的要求来划组，再把上面一部分赋予“0”，下面一部分赋予“1”，这都是存在一个二维数组中，其每一行对应一个概率的码字，接着再递归这两个小组。算法设计中遇到的问题和解决方法在费诺编码中，主要的难题就是怎么来划分组。这有点类似于我们学数据结构时需要编的遍历算法。所以我就运用了递归算法，这大大简便了算法设计，因为它的划分组的方法是一样的，不用递归算法，那么你就是一直在重复编写相同的划分程序，其中改变了一些变量值。所以递
14、归在这里是一个好的方法。运行结果 源代码#include#include#includechar p100100;void array(double f,int n)/排序int i,j;double m;for(i=1;i=n;i+)for(j=i;j=n;j+)if(fifj)m=fi;fi=fj;fj=m;void F(int m,int n,double f)/递归算法int i,k; double sum=0.0,s=0.0,s1,a20; if(m=n) return; for(i=1;i=n;i+) ai=fi; for(i=m;i=n;i+) sum=sum+ai;k=m; w
15、hile(s=sum-s) s1=s;s=s+fk+;if(sum-2*s1)=(2*s-sum) k-;for(i=m;ik;i+) strcat(pi,0);/编码上面的为0for(i=k;i=n;i+) strcat(pi,1);/编码下面的为1F(m,k-1,f);F(k,n,f); main()double sum=0.0,f100;int n,i;printf(请输入信源符号的个数: n);scanf(%d,&n);doprintf(请依次输入各信源符号的概率: n);for(i=1;i=n;i+)scanf(%lf,&fi);for(i=1;i=n;i+)sum+=fi;while(sum!=1);/检验概率和是否是1*/array(f,n);F(1,n,f);printf(按降序排列的概率为: );for(i=1;i=n;i+)printf(%.3f ,fi);printf(n);for(i=1;i=n;i+)printf(对应的码字为: %s,pi);printf(n);专心-专注-专业