信息论—— - 副本.doc

周鹏版权所有，违者必究版权所有，违者必究版权所有，违者必究版权所有，违者必究版权所有，违者必究版权所有，违者必究版权所有，违者必究版权所有，违者必究版权所有，违者必究版权所有，违者必究版权所有，违者必究版权所有，违者必究 唯一可译码判决准则一、实验内容编程实现唯一可译码的判决准则SardinasPatterson算法二、实验环境1. 计算机2. Windows 73. VC+ 6.0三、实验目的1. 进一步熟悉唯一可译码判决准则；2. 掌握VC开发环境的使用；3. 掌握C语言编程（尤其是字符串处理）四、实验要求1. 提前预习实验，认真阅读实验原理。2. 认真高效的完成实验，实验过程中服从实验室管理人员以及实验指导老师的管理。3. 认真填写实验报告。五、关于唯一可译码 1、唯一可译变长码判别准则 A.A.Sardinas和G.W.Patterson于1957年提出下述算法用于判断码C的唯一可译性此算法的原理如下所示： 其中Ai,Bi都是码字。可知，当且仅当某个有限长的码符号序列能译成两种不同的码字序列时，此码不是唯一可译码，此时B1一定是A1的前缀，而A1的尾随后缀一定是另一码字B2的前缀；而B2的尾随后缀又是其他码字的前缀最后，码符号序列的尾部一定是一个码字。将码C中所有可能的尾随后缀组成一个集合F，当且仅当集合F中没有包含任一码字，便可判断此码C为唯一可译变长码六、实现唯一可译码的判决准则过程 1、SardinasPatterson算法设C为码字集合，按以下步骤构造此码的尾随后缀集合F： (1) 考查C中所有的码字，若Wi是Wj的前缀，则将相应的后缀作为一个尾随后缀放入集合F0中； (2) 考查C和Fi两个集合，若WjC是WiFi的前缀或WiFi 是WjC的前缀，则将相应的后缀作为尾随后缀码放入集合Fi+1中； (3)F=Fi即为码C的尾随后缀集合； (4) 若F中出现了C中的元素，则算法终止，返回假(C不是唯一可译码)；否则若F中没有出现新的元素，则返回真。输入码字集合X0for 所有Wi，WjX0if 码字Wi 是码字Wj 的前缀，即将相应的后缀作为一个尾随后缀放入新集合X1 end ifend forfor 所有WiX0for 所有Wj Xn1if Wi 是Wj 的前缀，即将相应的后缀作为一个尾随后缀放入新集合Xn中 else if Wj是Wi的前缀，即将相应的后缀作为一个尾随后缀放入新集合Xn中 end if end for end for 构造尾随后缀集合XXiif 有码字WiX0，WiX，则非唯一可译码 2、算法流程1. 算法流程6、 实验设计 1、数据结构 本实验所需设计的程序中，码字可用如下结构体表示： 2、关键算法 3、函数调用关系图7、 实验结果 3、关键算法（判断前缀形成Fi）int judge(char * C,int num, int * l) int t=0,p=-1;int temp=-1; int *k=new intnum-1; /F中第i+1行有ki个字符 char *F; F=new char*num-1; for (int i=0;i=num-1;i+) /F0形成 Fi=new char100;for(int j=i+1;jlj) if(strncmp(Ci,Cj,lj)=0) k+p=li-lj; t=li-lj; post(C,F,i,t,p,num); else if(strncmp(Ci,Cj,li)=0) k+p=lj-li; t=lj-li; post(C,F,j,t,p,num); 4、函数调用关系图判断前缀形成Fi调用judge（） 主函数 main（）比较C和F中有无相同项 post（）七、用户手册 首先根据提示输入码字集合中码字的个数，然后分别输入码字8、 实验结果 输入6个码字：0、10、1100、1110、1011、1101，并判断出该码字集合不是唯一可译码 输入5个码字：xx、xz、y、zz、xyz，判断出该码字集合是可译码。9、 源程序（C+）#include #include #include /using namespace std;int judge(char * C,int num, int * l);void post(char * C,char * F,int b,int t,int p,int num);void main() int z; char *C; /码字集合 int num; /n行 cout请输入码字集合中码字个数num; /输入行数 int * l=new intnum; /C中第i+1行有li个字符 C=new char*num;/创建行指针 cout请依次输入码字endl; for(int i=0;inum;i+) cout第i+1行:endl; Ci=new char100;/为各行分配指针 gets(Ci); li=strlen(Ci); z=judge(C,num,l); if(z) cout该码是唯一可编译码endl; else cout该码不是唯一可编译码endl; delete l;/判断前缀形成Fiint judge(char * C,int num, int * l) int t=0,p=-1;int temp=-1; int *k=new intnum-1; /F中第i+1行有ki个字符 char *F; F=new char*num-1; for (int i=0;i=num-1;i+) /F0形成 Fi=new char100;for(int j=i+1;jlj) if(strncmp(Ci,Cj,lj)=0) k+p=li-lj; t=li-lj; post(C,F,i,t,p,num); else if(strncmp(Ci,Cj,li)=0) k+p=lj-li; t=lj-li; post(C,F,j,t,p,num); while(1) if (temp=p) break; temp=p; for(int a=0;anum;a+) for (int b=0;bkb) if(strncmp(Ca,Fb,la)=0) k+p=la-kb; t=la-kb; post(C,F,a,t,p,num); for (int j;jnum;j+) if(!strcmp(Fp,Cj) return 0; else if(strncmp(Ca,Fb,kb)=0) k+p=kb-la; t=kb-la; post(C,F,b,t,p,num); for (int j;jnum;j+) if(!strcmp(Fp,Cj) return 0; return 1;void post(char * C,char * F,int b,int t,int p,int num) int a=0; char * temp=new char100; while(!Cbt+) tempa+=Cbt+; for (int i=0;ip;i+) if(strcmp(temp,Fi) strcmp(F+p,temp); 十、参考书1. 信息论基础理论及应用傅祖芸，电子工业出版社2. C+程序设计谭浩强，清华大学出版社Shannon编码一、实验内容编程实现Shannon编码算法二、实验环境1. 计算机2. Windows 73. VC+ 6.0三、实验目的1. 进一步熟悉Shannon编码算法；2. 掌握C语言编程（尤其是数值的进制转换，数值与字符串之间的转换等）四、实验要求1. 提前预习实验，认真阅读实验原理。2. 认真高效的完成实验，实验过程中服从实验室管理人员以及实验指导老师的管理。3. 认真填写实验报告。五、关于Shannon码 1、Shannon码编码的原理 香农第一定理指出，可选择每个码字的长度满足关系式： 或： x 表示不小于 x 的整数。按不等式选择的码长所构成的码称香农码。香 农码满足克拉夫特不等式，所以一定存在对应码字的长度的惟一可译码。 2、Shannon编码特点 由于累加概率总是进一取整，香农编码方法不一定是最佳的； 由于第一个消息符号的累加概率总是为0,故它对应码字总是0、00、000、00的式样； 码字集合是唯一的，且为即时码； 先有码长再有码字； 对于一些信源，编码效率不高，冗余度稍大，因此其 实用性受到较大限制。 3、香农编码优缺点 香农码考虑了信源的统计特性，使经常出现的信源符号对应较短的码字，使信源的平均码 长缩短，从而实现了对信源的压缩； 香农码有系统的、惟一的编码方法，但在很多情况下编码效率不是很高；六、Shannon码编程实现过程 1、香农编码步骤 1、将信源发出的N个消息符号按其概率的递减次序依次排列。 2、按下式计算第i个消息的二进制代码组的码长，并取整。 3、为了编成唯一可译码，首先计算第i个消息的累加概率 4、将累加概率Pi （为小数）变成二进制数 5、去除小数点，并根据码长li ，取小数点后li 位数作为第i个消息的码字。 2、算法流程输入信源符号个数q，信源概率分布P降序排列pifor i=1 q 计算编码长度 ； 计算累加概率； 将累加概率F(si) （十进制小数）变成二进制数取小数点后li 位数作为第i个消息的码字。 end for 3、关键算法 冒泡排序法for(i=0;in-1;i+)for(j=1;jn-1-i;j+)if(bjbj+1)float nNumber=bj;bj=bj+1;bj+1 = nNumber;char temp=aj;aj=aj+1;aj+1=temp; 4、流程简图输入消息符号及其概率按概率的降序排序计算码组长度计算各个消息的累加概率将累加概率转化成二进制求出码字 第一步：按照概率递减排序 5、香农码举例第三步，计算累加概率第二步，确定码长 七、用户手册及总结 1、先根据提示输入消息符号的个数，enter键结束 2、根据提示输入消息符号及其概率，按enter键结束 通过此次的编程实现shannon码我比以前上课的时候更加清楚的了解了shannon码编码的过程及原理，同时对我的编程技术也有所练习提高 八、程序运行结果 九、香农编码源程序（C+）#include#includechar a5;int len15;float b15,d15;int h2020;void main()int i,j,n;cout请输入消息符号的数量：n;cout请输入该n个消息符号及其概率：endl;for(i=1;in+1;i+)cout符号iai;cout 其概率为（0xbi;coutendl;/按概率降序排列，用冒泡排序法for(i=0;in-1;i+)for(j=1;jn-1-i;j+)if(bjbj+1)float nNumber=bj;bj=bj+1;bj+1 = nNumber;char temp=aj;aj=aj+1;aj+1=temp;for(i=1;in+1;i+