唯一可译码的判别程序实现.doc
- 文档编号:652495
- 上传时间:2023-04-29
- 格式:DOC
- 页数:9
- 大小:77.61KB
唯一可译码的判别程序实现.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;i for(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时,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 唯一可译码 判别 程序 实现
![提示](https://static.bingdoc.com/images/bang_tan.gif)