《zhoujie信息论与编码》由会员分享，可在线阅读，更多相关《zhoujie信息论与编码（17页珍藏版）》请在金锄头文库上搜索。
1、氏01册0107 -珮mw拯Z8glo26ooz 申 游 怆“如 載 mtZOI6ogzI “賺 卑实习一：设计程序判断唯一可译码一、题目分析设计一个程序实现判断输入码组是否为可译码组这一功能。在我们学习使用了克拉夫特不等式之后，知道唯一可以码必须满足克拉夫特不等式。但 是克拉夫特不等式仅仅是存在性的判定定理，即该定理不能作为判断一种码是否为唯一可译 码的依据。也就是说当码字长度和码符号数满足克拉夫特不等式时，则必可以构造出唯一可 译码，否则不能构造出唯一可译码。因此我们必须找到一种能够判断一种码是否为唯一可译 码的方法-SardinasPatterson 算法。二、算法分析SardinasP
2、atterson 算法描述：设C为码字集合，按以下步骤构造此码的尾随后缀集合F：(1) 考查C中所有的码字，若Wi是Wj的前缀，则将相应的后缀作为一个尾随后缀 放入集合 F0 中；(2) 考查C和Fi两个集合，若W/WC是WiUFi的前缀或WiFi是W/WC的前缀，则将相应的后缀作为尾随后缀码放入集合Fi+1中；(3) F= UFi即为码C的尾随后缀集合；(4) 若F中出现了 C中的元素，则算法终止，返回假(C不是唯一可译码)；否则若F 中没有出现新的元素，则返回真。在我们设计的算法中，需要注意的是我们需要的是先输出所有尾随后缀的集合，然后再判断该码是否是唯一可译码，即如F中出现了 C中的元素
3、，则C不是唯一可译 码，否则若F中没有出现新的元素，则C为唯一可译码。而不是F中出现C中的元素 就终止，这也是在本题的要求中需要注意的问题。简明流程图三、概要设计：由于需要判断尾随后缀，所以我们需要反复的比较C和F中的码字。1)首先我们用一个b4040的数组来存放所有的尾随后缀的集合；用Q记录所有尾随后缀的个数；2) 用数组a4040来存放输入的码字，L50来存放码字的长度；通过一个双重循环并调用Hz (ai,aj,Li,Lj)函数来找到a4040中的为随后缀, 即：for(i=0;in-1;i+) for(j=0;jn;j+)if(i!=j&LiLj) Hz(ai,aj,Li,Lj);3)
4、通过判断Q是否大于0,如果不大于0,即b4040中没有码字，也就是不存在尾 随后缀，那么可判断a4040是唯一可译码，否则进行如下操作；4) 计算b4040中尾随后缀的长度，用k1表示;并调用Hz(bi,aj,kl,Lj)其中klvLj 来a4040中所存在的后缀，并加入到b4040中，通过一个循环，找到a4040 中所有尾随后缀；即for(i=0;iQ;i+)kl=strlen(bi);for(j=0;jn;j+) if(klLj;通过循环调用即可找到b4040中的所有 尾随后缀，最后再将他们分别存放在b4040中；即通过for(i=0;in;i+) for(j=0;jLi)Hz(ai,bj
5、,Li,k2); 6) 在反复调用Hz(ai,aj,Li,Lj)函数中如果b4040中有重复出现的，即尾随后缀 相同的不用再次放入b4040中。7) 在调用函数中所需要注意的问题就是一个比较的问题，也就是实现6)中所提到的。四、测试结果4.1、测试数据为 0 10 1100 1110 1011 11011011011 11010 100 011aro_S ha nn n.exe G:DebijgF111 0 10 11000 t- 611 码 :0:1译 r 丁 巾码合一 码疋 入次后不随码Press any key to continue11100 00 10 G:DebugFano_S h
6、a nn o n. exe4.2、测试数据为 110 11 100 00 1005 1 t-1 0 nrp. 頁译 个码合可 T*-随码any key to continue五、源代码#include #include char b4040;int Q;void Hz(char c,char d,int L1,int L2) int i,j,temp=0;char m50; for(i=0;iL1;i+) if(ci=di)continue; else break;if(i=L1)for(j=0;jL2-L1;j+) mj=dL1+j; mj=0;for(i=0;iQ;i+)if(strcmp
7、(bi,m)=0) temp=1;break;if(temp!=1)strcpy(bQ,m); Q+;void main()int i,j,k,k1,k2,n;char a4040;int L50;int temp=1;int f=0;printf(请输入码字个数：”)；scanf(%d,&n);printf(请分别输入码字:);for(i=0；in；i+)scanf(%s,&ai); Li=strlen(ai);for(i=0;in-1;i+) for(j=0;jn;j+) if(i!=j&Li0)for(i=0;iQ;i+)k1=strlen(bi);for(j=0;jn;j+)if(k1
8、Lj)Hz(bi,aj,k1,Lj);for(k=0;kn;k+)for(j=0;jLk) Hz(ak,bj,Lk,k2);printf(”尾随后缀集合为:”)；for(i=0;iQ;i+)printf(%s ,bi)；for(i=0；in&temp!=0；i+)for(j=0；jQ；j+)if(strcmp(ai,bj)=0)temp=0；break；else continue; printf(n);if(temp=O)printf(” 该码不是唯一可译码!n); else printf(该码是唯一可译码!n);else printf(该码组是唯一可译码!)； f+;printf(n);实习
9、二：香农编码一、题目分析对于给定的信源的概率分布，按照香农编码的方法进行计算机实现。二 、算法分析2.1、算法基本原理 给定某个信源符号的概率分布，通过以下的步骤进行香农编码：1) 信源符号按概率从大到小排列；2) 对信源符号求累加和，表达式： Pi=Pi-1+p(xi)；i i-1 i3) 求自信息量，确定码字长度。自信息量I(x)=-log(p(x);码字长度取大于等于自1 1信息量的最小整数；4) 将累加和用二进制表示，并取小数点后码字的长度的码 。 简明流程图2.2、主要函数设计及分析1) paixu() 函数 本函数的功能主要是对用户输入的各个符号对应的概率进行降序排列，以便于计算累
10、加 概率和编码。for(i=0;in-1;i+)for(j=i+1;jn;j+)if(pipj)e=pi; pi=pj;pj=e;2) length()函数 本函数的功能主要是求每个符号概率对应码字的长度。for(i=0;in;i+)I=-log(pi)/log(2);m=int(I); ki=m+1;3) mazi() 函数本函数的功能主要是将累加概率转换为二进制，从而根据码长计算出相应的码字，在这 里用到对浮点数转换为二进制的算法。for(i=0;in;i+)s=pai;for(j=0;j=1) stri+=1; s=s-1;else stri+=0;三、测试结果测试数据为：0.20 0.
11、19 0.17 0.15 0.10 0.01 0.18” G:Deb ugFano_S harm o n. exe个的 号号 源源 =_口=一口n=7率依次为：0-2 0p Pa Ki0.2190.190.180.170.150.10.01any key0.20.390.570.740.890.9947 to continue0.18 0.17 0.15 0.1 0.01码字00000101110010111101111110四、分析与探讨只是在对概率取对数并向上取整时遇到一定的困难，经过思考，利用上述的模拟手工出 发圆满的解决了这一难题，使得程序能够得以完成。五、源代码 #include #
12、include #include using namespace std; void paixu(double *p,int n) int i,j; double e=0.0; for(i=0;in-1;i+) for(j=i+1;jn;j+) if(pipj)e=pi; pi=pj; pj=e; void leijia(double *p,double *pa,int n)int i;double sum=0.0;for(i=0;in;i+)pai=sum;sum+=pi;void length(double *p,int *k,int n)int i,m;double I;for(i=0;in;i+)I=-log(pi)/log(2);m=int(I);ki=m+1;void mazi(int *k,double *pa,string *str,int n)int i,
