《唯一可译码的判别程序实现》由会员分享，可在线阅读，更多相关《唯一可译码的判别程序实现（9页珍藏版）》请在金锄头文库上搜索。
1、唯一可译码的判别程序实现姓名：周浩勇学号： 1023013455 专业：通信工程一 引言信源编码的设计准则是, 设计完成的编码必须是唯一可译码才能够被使用。根据唯一可译码的定义: 任意有限长的码元序列 , 只能被唯一地分割成一个个的码字, 便被称为唯一可译码 2 , 希望在得到一组编码之后, 能够判断所设计出来的是否是唯一可译码。唯一可译码存在性的判别, 可以通过 Kraft 不等式给出唯一可译码存在的充分必要条件, 即: D 进制码字集合 C = C1, C2, ,Cn , 码集中每一 C i ( i =1, 2, n) 都是一个 D 进制符号串 , 设C1, C2, ,Cn 对应的码长分别
2、是L1, L 2, , Ln , 则存在唯一可译码的充要条件是niLD1i1 显然 , 克劳夫特不等式只涉及唯一可译码的存在问题而不涉及具体的码。它强调的是存在, 但这并不是唯一可译码判断的充要条件。也就是说, 唯一可译码一定满足克拉夫特不等式, 但是反之 , 满足克拉夫特不等式的码不一定是唯一可译码。二 算法的实现目前 , 常用的判别唯一可译码的方法有两种: 一种是根据异前缀码来进行判断的方法, 另一种是由 A. A. Sardinas和G. W. patterson于1957年提出的算法。以下具体描述这两种算法。方法一 : 根据异前缀码是唯一可译码来进行判断。其步骤如下: 首先 , 观察是
3、否为非奇异码。若是奇异码, 肯定不是唯一可译码 ; 其次 , 计算是否满足 K raft不等式。若不满足一定不是唯一可译码; 最后 , 将码画成一棵码树图, 观察是否满足异前缀码的码树图的构造, 若满足则是唯一可译码。这种方法的理论基础是异前缀码一定是唯一可译码, 通过经典的 Kra ft不等式及码树图进行判别。但它的缺点也是显而易见的 , 若不是异前缀码时, 则此方法无法判断是否是唯一可译码。方法二 : 使用 A. A. Sardinas和 G. W. Patterson设计的判断法。其判断准则为 : 计算分组码C 中所有可能的尾随后缀集合 F, 观察 F 中有没有包含任一码字, 若无则为唯
4、一可译码 ; 若有则一定不是唯一可译码。算法中的关键为尾随后缀集合 F 的构造。步骤如下：(1) 考查 C 中所有的码字，若Wi 是 Wj 的前缀，则将相应的后缀作为一个尾随后缀放入集合F0 中；(2) 考查 C 和 Fi 两个集合，若WjC 是 WiFi 的前缀或WiFi 是 WjC 的前缀，则将相应的后缀作为尾随后缀码放入集合 Fi+1(3)F= Fi 即为码 C(4) 若 F 中出现了 C 中的元素，则算法终止，返回假(C 不是唯一可译码 )；否则若 F 中没有出现新的元素，则返回真。本文将以方法二来实现唯一可译码的判别。一算法流程 ：输入码字集合X0 for 所有 Wi，WjX0 if
5、 码字 Wi 是码字 Wj的前缀， 即将相应的后缀作为一个尾随后缀放入新集合 X1 end if end for for 所有 WiX0 for 所有 Wj Xn1 if Wi 是 Wj的前缀， 即将相应的后缀作为一个尾随后缀放入新 集合 Xn中 else if Wj是 Wi的前缀， 即将相应的后缀作为一个 尾随后缀放入新集合Xn中 end if end for end for 构造尾随后缀集合XXi if 有码字 WiX0，WiX，则非唯一可译码二 流程框图Y N Y N Y N N Y 三 数据结构：本文需设计的程序中，码字可用如下结构（即条件限制）输入两个要计算尾随后缀的字符比较 ci
6、、di i=0 i+；如果 ci=di= /0如果 ci= /0 ,将 d的剩余部分放入尾随后缀集合如果 di= /0 ,将 c 的剩余部分放入尾随后缀集合开始break 如果 ci=di 表示：char c10050 尾随后缀用如下结构（即条件限制）表示: char f30050 四 程序代码：#include #include char c10050; char f30050; int N,sum=0; /N 为输入码字的个数， sum 为尾随后缀集合中码字的个数 int flag; /判断是否唯一可译标志位void patterson(char c,char d) /检测尾随后缀 int
7、 i,j,k; for(i=0;i+) if(ci=0 if(ci=0) /d 比 c 长，将 d 的尾随后缀放入 f 中 for(j=i;dj!=0;j+) fsumj-i=dj; fsumj-i=0; for(k=0;k100) printf(“ 输入码字个数过大，请输入小于100 的数n“); printf(“ 请输入码字的个数（小于100）:“); scanf(“%d“, flag=0; printf(“ 请分别输入码字（每个码字长度小于50 个字符） :n“); for(i=0;iN;i+) scanf(“%s“, for(i=0;iN-1;i+)/ 判断如果码本身是否重复 for(
8、j=i+1;jN;j+) if(strcmp(ci,cj)=0) flag=1;break; if(flag=1)/ 如果码本身有重复，就可以断定它不是唯一可译码 printf(“ 这不是唯一可译码。 n“); else for(i=0;iN-1;i+) /*此处是根据原始编码生成的尾随后缀集合s1放 入 f 中*/ for(j=i+1;jN;j+) patterson(ci,cj); for(i=0;i+) /根据原始码与 si生成 si+1也放入 fi int s=0; for(j=0;jN;j+) /*判断 si+1中的字符串是否与si中一样 ， 重复的则不再添加 */ if(i=sum
9、) s=1;break; else patterson(fi,cj); if(s=1)break; for(i=0;isum;i+) /*判断 p 里的字符串是否与s 中重复， 重复则不是唯一的 */ for(j=0;jN;j+) if(strcmp(fi,cj)=0) flag=1; break; if(flag=1) printf(“ 这不是唯一可译码。 n“); else printf(“ 这是唯一可译码。 n“); printf(“ 尾随后缀集合为 :“); for(i=0;i=sum;i+) printf(“n%s“,fi); 五 输入编码：举简例如下：1: 10，0, 100 2: 10, 110，1110 六 运行结果1 输入 10, 0, 100时，2 输 10, 110，1110 时，
