唯一可译码的判别程序实现.doc
《唯一可译码的判别程序实现.doc》由会员分享，可在线阅读，更多相关《唯一可译码的判别程序实现.doc（9页珍藏版）》请在冰点文库上搜索。
唯一可译码的判别
程序实现
姓名：
周浩勇
学号：
1023013455
专业：
通信工程
一引言
信源编码的设计准则是,设计完成的编码必须是唯一可译码才能够被使用。
根据唯一可译码的定义:
任意有限长的码元序列,只能被唯一地分割成一个个的码字,便被称为唯一可译码[2],希望在得到一组编码之后,能够判断所设计出来的是否是唯一可译码。
唯一可译码存在性的判别,可以通过Kraft不等式给出唯一可译码存在的充分必要条件,即:
D进制码字集合C={C1,C2,…,Cn},码集中每一Ci（i=1,2,…,n）都是一个D进制符号串,设C1,C2,…,Cn对应的码长分别是L1,L2,…,Ln,则存在唯一可译码的充要条件是i≤1显然,克劳夫特不等式只涉及唯一可译码的存在问题而不涉及具体的码。
它强调的是存在,但这并不是唯一可译码判断的充要条件。
也就是说,唯一可译码一定满足克拉夫特不等式,但是反之,满足克拉夫特不等式的码不一定是唯一可译码。
二算法的实现
目前,常用的判别唯一可译码的方法有两种:
一种是根据异前缀码来进行判断的方法,另一种是由A.A.Sardinas和G.W.patterson于1957年提出的算法。
以下具体描述这两种算法。
方法一:
根据异前缀码是唯一可译码来进行判断。
其步骤如下:
首先,观察是否为非奇异码。
若是奇异码,肯定不是唯一可译码;其次,计算是否满足Kraft不等式。
若不满足一
定不是唯一可译码;最后,将码画成一棵码树图,观察是否满足异前缀码的码树图的构造,若满足则是唯一可译码。
这种方法的理论基础是异前缀码一定是唯一可译码,通过经典的Kraft不等式及码树图进行判别。
但它的缺点也是显而易见的,若不是异前缀码时,则此方法无法判断是否是唯一可译码。
方法二:
使用A.A.Sardinas和G.W.Patterson设计的判断法。
其判断准则为:
计算分组码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不是唯一可译码）；否则若F中没有出现新的元素，则返回真。
本文将以方法二来实现唯一可译码的判别。
一算法流程：
输入码字集合X0
for所有Wi，Wj∈X0
if码字Wi是码字Wj的前缀，
即将相应的后缀作为一个尾随后缀放入新集合X1
endif
endfor
for所有Wi∈X0
for所有Wj∈Xn－1
ifWi是Wj的前缀，
即将相应的后缀作为一个尾随后缀放入新集合Xn中
elseifWj是Wi的前缀，
即将相应的后缀作为一个尾随后缀放入新集合Xn中
endif
endfor
endfor
构造尾随后缀集合X←Xi
if有码字Wi∈X0，Wi∈X，则非唯一可译码
二流程框图
开始
输入两个要计算
尾随后缀的字符串
i=0
比较c[i]、d[i]
如果c[i]=d[i]=’/0’
Y
N
如果c[i]=’/0’,将d的剩余部分放入尾随后缀集合
Y
N
如果d[i]=’/0’,将c的剩余部分放入尾随后缀集合
Y
如果c[i]=d[i]
N
N
i++；
Y
break
三数据结构：
本文需设计的程序中，码字可用如下结构（即条件限制）表示：
charc[100][50]
尾随后缀用如下结构（即条件限制）表示:
charf[300][50]
四程序代码：
#include
#include
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]=='\0'&&d[i]=='\0'）//2字符串一样，跳出
break;
if（c[i]=='\0'）//d比c长，将d的尾随后缀放入f中
{
for（j=i;d[j]!
='\0';j++）f[sum][j-i]=d[j];
f[sum][j-i]='\0';
for（k=0;k{
if（strcmp（f[sum],f[k]）==0）/*查看当前生成的尾随后缀在f集合中是否存在*/
{
sum--;break;
}
}
sum++;
break;
}
if（d[i]=='\0'）//c比d长，将c的尾随后缀放入f中
{
for（j=i;c[j]!
='\0';j++）f[sum][j-i]=c[j];
f[sum][j-i]='\0';
for（k=0;k{
if（strcmp（f[sum],f[k]）==0）/*查看当前生成的尾随后缀在f集合中是否存在*/
{
sum--;break;
}
}
sum++;
break;
}
if（c[i]!
=d[i]）//字符不一样了也退出
break;
}
}
/*主函数*/
main（）
{
inti,j;
printf（"请输入码字的个数（小于100）:
"）;//输入码得个数
scanf（"%d",&N）;
while（N>100）
{
printf（"输入码字个数过大，请输入小于100的数\n"）;
printf（"请输入码字的个数（小于100）:
"）;
scanf（"%d",&N）;
}
flag=0;
printf（"请分别输入码字（每个码字长度小于50个字符）:
\n"）;
for（i=0;i{
scanf（"%s",&c[i]）;
}
for（i=0;ifor（j=i+1;j{
if（strcmp（c[i],c[j]）==0）
{flag=1;break;}
}
if（flag==1）//如果码本身有重复，就可以断定它不是唯一可译码
{
printf（"这不是唯一可译码。
\n"）;
}
else
{
for（i=0;i {
for（j=i+1;j {
patterson（c[i],c[j]）;
}
}
for（i=0;;i++）//根据原始码与s[i]生成s[i+1]也放入f[i]
{
ints=0;
for（j=0;j {
if（i==sum）
{s=1;break;}
else
patterson（f[i],c[j]）;
}
if（s==1）break;
}
for（i=0;i {
for（j=0;j {
if（strcmp（f[i],c[j]）==0）
{
flag=1;
break;
}
}
}
if（flag==1）
{
printf（"这不是唯一可译码。
\n"）;
}
else
printf（"这是唯一可译码。
\n"）;
}
printf（"尾随后缀集合为:
"）;
for（i=0;i<=sum;i++）
printf（"\n%s",f[i]）;
}
五输入编码：
举简例如下：
1:
10，0,100
2:
10,110，1110
六运行结果
1输入10,0,100时，
2输10,110，1110时，
升级会员 