唯一可译码的判别

1、信息论与编码技术课程设计(论文)设计（论文）题目唯一可译码的判别学院名称管理科学学院专业名称信息与计算科学学生姓名曹昌杰学生学号201307020102指导教师乐千桤设计（论文）成绩教务处 制2015 年 12 月 12 日唯一可译码的判别摘 要唯一可译码的判别原理是：设S0为原始码字的集合，再构造一系列集合S1，S2，为得到集合S1，首先考察S0中所有的码字。若码字j是码字i的前缀，即i=jA，则将后缀A列为S1中的元素，S1是由所有具有这种性质的A构成的集合。再从新产生的集合中拿出一个元素，从原始集合S0中拿出一个元素，看有没有一个码字是另一个码字的前缀这种情况，如果有就将后缀放入更新的集

2、合中，直到更新的集合为空集为止，一种码是唯一可译码的充要条件是S1，S2，中没有一个含有S0中的码字。关键词: 原始码字；前缀；后缀；更新集合；空集第1章 前 言1.1内容及要求(或课题背景)对于用户输入指定的编码个数及编码，判断出输入的码为唯一可译码。1.2 本文研究思路及结构安排设计判定唯一可译码的思路如下：1）、考察S0中所有的码字。若码字j是码字i的前缀，即i=jA，则将后缀A列为S1中的元素，构造S1。2)、从新产生的集合中拿出一个元素，从原始集合S0中拿出一个元素，找有没有一个码字是另一个码字的前缀这种情况，如果有，就将后缀放入更新的集合中。3）、如此构造的S1,S2，集合中没有一

3、个含有S0中的码字，此编码即为唯一可译码，否则，该编码不是唯一可译码。第2章 相关理论知识唯一可译码充要判定条件：设S0为原始码字的集合，再构造一系列集合S1，S2，为得到集合S1，首先考察S0中所有的码字。若码字j是码字i的前缀，即i=jA，则将后缀A列为S1中的元素，S1是由所有具有这种性质的A构成的集合。再从新产生的集合中拿出一个元素，从原始集合S0中拿出一个元素，看有没有一个码字是另一个码字的前缀这种情况，如果有就将后缀放入更新的集合中，直到更新的集合为空集为止，若S1，S2，中没有一个含有S0中的码字，则为唯一可译码。第3章 算法设计与分析1）、虽然编码为数字编码，但如“001”、“

4、010”类型的编码不能使用int类型数组进行存储，因为编码为字符串类型，尝试用二维字符数组去存储它们，考虑到还有字符串长度等变量，可以使用一个Code的结构体去存储。2）进行判断的第一步，首先考虑S0内部，若码字j是码字i的前缀，即i=jA，则将后缀A列为S1中的元素，构造S1。否则，可以直接判定该编码为唯一可译码。3）从新产生的集合中拿出一个元素，从原始集合S0中拿出一个元素，找有没有一个码字是另一个码字的前缀这种情况，如果有，就将后缀放入更新的集合中。直到这个更新的集合为空集为止。4）、比较构造的S1,S2，集合中没有一个含有S0中的码字，此编码即为唯一可译码，否则，该编码不是唯一可译码。

5、第4章 程序实现与测试程序运行截图如下：1、 输入唯一可译码：01、10、00、112、 输入非唯一可译码：00、101、001、100、111、000第5章 结 论在定理“对任意的正整数N，如果一种编码方法的N次扩展码都是非奇异的，则该编码方法就是唯一可译码”对唯一可译码的判定显然在实际应用中很难发挥作用，因为不可能一一检查所有N次扩展码的奇异性。但可以通过构造后缀集合的方式，在结论“一种码是唯一可译码的充要条件是S1,S2，集合中没有一个含有S0中的码字”下(S1,S2，集合均是后缀集合)可以很好地解决唯一可译码的判定问题。参考文献1 2 姜楠.王健 信息论与编码理论M.北京:清华大学出版

6、社.2010年5月.附录：源程序清单#include<stdio.h>#include<string.h>struct Codechar code10010;int len100;int p; /码字或尾缀的个数;int main()struct Code s100,F,C;int N,i,j,l,t,p;printf("输入码字的个数: ");scanf("%d",&N);printf("输入编码:");for(i=0;i<N;i+)scanf("%s",s0.codei);

7、s0.leni=strlen(s0.codei);s0.p=N;F.p=0;p=0;/循环结束条件为新的尾缀和F中的尾缀比较若没有新的尾缀出现 while(1) /使循环一直执行下去，以break形式跳出C.p=0;sp+1.p=0;for(i=0;i<N;i+) /判断s0中是否有码字是其他码字的前缀for(j=0;j<sp.p;j+)if(i=j&&p=0)continue;if(s0.leni>=sp.lenj)continue;for(l=0;l<s0.leni;l+) /判断s0中的码字是否为sp中码字的前缀if(s0.codeil!=sp.c

8、odejl)break;if(l=s0.leni) /将尾缀存到sp+1中t=0;for(;l<sp.lenj;l+)sp+1.codesp+1.pt=sp.codejl;t+;sp+1.codesp+1.pt='0'sp+1.lensp+1.p=t;sp+1.p+;for(j=0;j<sp.p;j+)if(p=0)break;for(i=0;i<N;i+)if(s0.leni<=sp.lenj)continue;for(l=0;l<sp.lenj;l+) /判断sp中码字是否是s0中码字的前缀if(sp.codejl!=s0.codeil)bre

9、ak;if(l=sp.lenj) /将尾缀存到sp+1中t=0;for(;l<s0.leni;l+)sp+1.codesp+1.pt=s0.codeil;t+;sp+1.codesp+1.pt='0'sp+1.lensp+1.p=t;sp+1.p+;p+;t=F.p;/还要判断sp中是否有相同的元素 for(i=0;i<sp.p;i+) for(j=i+1;j<sp.p;j+)if(strcmp(sp.codei,sp.codej)=0)break;if(j=sp.p) for(l=0;l<sp.leni;l+)C.codeC.pl=sp.codeil;

10、C.codeC.pl='0'C.lenC.p=l;C.p+; /比较Cp和F中的元素/并判断Cp中是否有新的元素for(i=0;i<C.p;i+) for(j=0;j<t;j+)if(strcmp(C.codei,F.codej)=0)break;if(j=t) /表示没有相同的元素,表示有新的尾缀出现for(l=0;l<C.leni;l+)F.codeF.pl=C.codeil;sp.codeF.p-tl=C.codeil;F.codeF.pl='0'sp.codeF.p-tl='0'F.lenF.p=l;F.p+;if(F.

11、p-t=0)break; /将F中的尾缀和s0中的码字进行比较for(i=0;i<s0.p;i+)for(j=0;j<F.p;j+)if(strcmp(s0.codei,F.codej)=0)break;if(j!=F.p)printf("此编码不是唯一可译码!n");printf("尾缀集合为:");for(t=0;t<F.p;t+)printf("%s ",F.codet);printf("n");break;if(i=s0.p)printf("此编码是唯一可译码!n");printf("尾缀集合为:");for(t=0;t<F.p;t+)printf("%s ",F.codet);printf("n");return 0;学生学习心得 通过本次的上机实习，我深刻认识到了自己在编程方面的不足之处，不能灵活的将算法运用到编程之中，需要以后在学习过程中不断实践，不断努力来提高自己的编程水准，并且在信息论方面的知识没有建立足够的体系，在实验过程中，表