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

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

姓名：*** 学号：********** 专业：通信工程

一 引言

信源编码的设计准则是, 设计完成的编码必须是唯一可译码才能够被使用。根据唯一可译码的定义: 任意有限长的码元序列, 只能被唯一地分割成一个个的码字, 便被称为唯一可译码[ 2 ] , 希望在得到一组编码之后, 能够判断所设计出来的是否是唯一可译码。唯一可译码存在性的判别, 可以通过Kraft不等式给出唯一可译码存在的充分必要条件, 即: D进制码字集合C = {C1, C2,… ,Cn }, 码集中每一C i ( i =1, 2,…, n) 都是一个D 进制符号串, 设C1, C2,…,Cn 对应的码长分别是L1, L 2,… , Ln , 则存在唯一可译码的充要条件是i1DnLi≤1 显然, 克劳夫特不等式只涉及唯一

可译码的存在问题而不涉及具体的码。它强调的是存在, 但这并不是唯一可译码判断的充要条件。也就是说,唯一可译码一定满足克拉夫特不等式, 但是反之, 满足克拉夫特不等式的码不一定是唯一可译码。 二 算法的实现

目前, 常用的判别唯一可译码的方法有两种: 一种是根据异前缀码来进行判断的方法, 另一种是由A. A. Sardinas和G. W. patterson于1957年提出的算法。以下具体描述这两种算法。

方法一: 根据异前缀码是唯一可译码来进行判断。其步骤如下:首先, 观察是否为非奇异码。若是奇异码, 肯定不是唯

一可译码;其次, 计算是否满足K raft不等式。若不满足一 定不是唯一可译码;最后, 将码画成一棵码树图, 观察是否满足异前缀码的码树图的构造, 若满足则是唯一可译码。这种方法的理论基础是异前缀码一定是唯一可译码, 通过经典的Kra ft不等式及码树图进行判别。但它的缺点也是显而易见的, 若不是异前缀码时, 则此方法无法判断是否是唯一可译码。

方法二: 使用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

end if end for

for 所有Wi∈X0

for 所有Wj∈ Xn－1

if Wi 是Wj 的前缀，

即将相应的后缀作为一个尾随后缀放入新

集合Xn中

else if Wj是Wi的前缀，

即将相应的后缀作为一个

尾随后缀放入新集合Xn中 end if end for end for

构造尾随后缀集合X←Xi

if 有码字Wi∈X0，Wi∈X，则非唯一可译码

二 流程框图

如果 c[i]=d[i]= ’ Y ’/0 N Y

如果c[i]=’/0’,将d的剩余部分放入尾随后缀集合 开始 输入两个要计算 尾随后缀的字符i=0 比较c[i]、d[i] N Y

如果d[i]=’/0’,将c的剩余部分放入尾随后缀集合 N 如果 c[i]=d[i] N Y

i++； break

三

数据结构：

本文需设计的程序中，码字可用如下结构（即条件限制）

表示：

char c[100][50]

尾随后缀用如下结构（即条件限制）表示: char f[300][50]

四 程序代码：

#include #include char c[100][50]; char f[300][50];

int N,sum=0; //N为输入码字的个数，sum为尾随后缀集合中码字的个数 int flag; //判断是否唯一可译标志位

void patterson(char c[],char d[]) //检测尾随后缀 {

int i,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;kif(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;kif(strcmp(f[sum],f[k])==0) /*查看当前生成的尾随后缀在

f集合中是否存在*/

{

sum--;break; } }

sum++; break; }

if(c[i]!=d[i])//字符不一样了也退出 break; } }

/*主函数*/ main() {

int i,j;

printf(\"请输入码字的个数（小于100）:\");//输入码得个数 scanf(\"%d\ while(N>100) { printf(\"输入码字个数过大，请输入小于100的数\\n\"); printf(\"请输入码字的个数（小于100）:\"); scanf(\"%d\ }

flag=0;

printf(\"请分别输入码字（每个码字长度小于50个字符）:\\n\"); for(i=0;iscanf(\"%s\ }

for(i=0;iif(strcmp(c[i],c[j])==0) {flag=1;break;} }

if(flag==1)//如果码本身有重复，就可以断定它不是唯一可译码 {

printf(\"这不是唯一可译码。\\n\"); } else {

for(i=0;i入f中*/

{

for(j=i+1;jpatterson(c[i],c[j]); } }

for(i=0;;i++) //根据原始码与s[i]生成s[i+1]也放入f[i] {

int s=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;jif(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\

五 输入编码： 举简例如下： 1: 10，0, 100 2: 10, 110，1110 六 运行结果 1 输入10, 0, 100时，

2 输10, 110，1110时，