唯一可译码的判别程序实现.doc

《唯一可译码的判别程序实现.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、唯一可译码的判别程序实现姓名：周浩勇学号：1023013455专业：通信工程一引言信源编码的设计准则是,设计完成的编码必须是唯一可译码才能够被使用。根据唯一可译码的定义:任意有限长的码元序列,只能被唯一地分割成一个个的码字,便被称为唯一可译码[2],希望在得到一组编码之后,能够判断所设计出来的是否是唯一可译码。唯一可译码存在性的判别,可以通过Kraft不等式给出唯一可译码存在的充分必要条件,即:D进制码字集合C={C1,C2,…,Cn},码集中每一Ci(i=1,2,…,n)都是一个D进制符号串,设C1,

2、C2,…,Cn对应的码长分别是L1,L2,…,Ln,则存在唯一可译码的充要条件是i≤1显然,克劳夫特不等式只涉及唯一可译码的存在问题而不涉及具体的码。它强调的是存在,但这并不是唯一可译码判断的充要条件。也就是说,唯一可译码一定满足克拉夫特不等式,但是反之,满足克拉夫特不等式的码不一定是唯一可译码。二算法的实现目前,常用的判别唯一可译码的方法有两种:一种是根据异前缀码来进行判断的方法,另一种是由A.A.Sardinas和G.W.patterson于1957年提出的算法。以下具体描述这两种算法。方法一:根据

3、异前缀码是唯一可译码来进行判断。其步骤如下:首先,观察是否为非奇异码。若是奇异码,肯定不是唯一可译码;其次,计算是否满足Kraft不等式。若不满足一定不是唯一可译码;最后,将码画成一棵码树图,观察是否满足异前缀码的码树图的构造,若满足则是唯一可译码。这种方法的理论基础是异前缀码一定是唯一可译码,通过经典的Kraft不等式及码树图进行判别。但它的缺点也是显而易见的,若不是异前缀码时,则此方法无法判断是否是唯一可译码。方法二:使用A.A.Sardinas和G.W.Patterson设计的判断法。其判断准则为

4、:计算分组码C中所有可能的尾随后缀集合F,观察F中有没有包含任一码字,若无则为唯一可译码;若有则一定不是唯一可译码。算法中的关键为尾随后缀集合F的构造。步骤如下：(1)考查C中所有的码字，若Wi是Wj的前缀，则将相应的后缀作为一个尾随后缀放入集合F0中；(2)考查C和Fi两个集合，若Wj∈C是Wi∈Fi的前缀或Wi∈Fi是Wj∈C的前缀，则将相应的后缀作为尾随后缀码放入集合Fi+1中；(3)F=∪Fi即为码C的尾随后缀集合；(4)若F中出现了C中的元素，则算法终止，返回假(C不是唯一可译码)；否则若

5、F中没有出现新的元素，则返回真。本文将以方法二来实现唯一可译码的判别。一算法流程：输入码字集合X0for所有Wi，Wj∈X0if码字Wi是码字Wj的前缀，即将相应的后缀作为一个尾随后缀放入新集合X1endifendforfor所有Wi∈X0for所有Wj∈Xn－1ifWi是Wj的前缀，即将相应的后缀作为一个尾随后缀放入新集合Xn中elseifWj是Wi的前缀，即将相应的后缀作为一个尾随后缀放入新集合Xn中endifendforendfor构造尾随后缀集合X←Xiif有码字Wi∈X0，Wi∈X，则非唯一可

6、译码二流程框图开始输入两个要计算尾随后缀的字符串i=0比较c[i]、d[i]如果c[i]=d[i]=’/0’YN如果c[i]=’/0’,将d的剩余部分放入尾随后缀集合YN如果d[i]=’/0’,将c的剩余部分放入尾随后缀集合Y如果c[i]=d[i]NNi++；Ybreak三数据结构：本文需设计的程序中，码字可用如下结构（即条件限制）表示：charc[100][50]尾随后缀用如下结构（即条件限制）表示:charf[300][50]四程序代码：#include#include

7、g.h>charc[100][50];charf[300][50];intN,sum=0;//N为输入码字的个数，sum为尾随后缀集合中码字的个数intflag;//判断是否唯一可译标志位voidpatterson(charc[],chard[])//检测尾随后缀{inti,j,k;for(i=0;;i++){if(c[i]==''&&d[i]=='')//2字符串一样，跳出break;if(c[i]=='')//d比c长，将d的尾随后缀放入f中{for(j=i;d[j]!='';j++

8、)f[sum][j-i]=d[j];f[sum][j-i]='';for(k=0;k