zhoujie信息论与编码

1、信 息 论-课程设计报告 班 级： 12309107指导老师： 余林琛姓 名： 周杰学 号：20091001587实 习 日 期 ：2010年10月实习一：设计程序判断唯一可译码一、题目分析 设计一个程序实现判断输入码组是否为可译码组这一功能。在我们学习使用了克拉夫特不等式之后，知道唯一可以码必须满足克拉夫特不等式。但是克拉夫特不等式仅仅是存在性的判定定理，即该定理不能作为判断一种码是否为唯一可译码的依据。也就是说当码字长度和码符号数满足克拉夫特不等式时，则必可以构造出唯一可译码，否则不能构造出唯一可译码。因此我们必须找到一种能够判断一种码是否为唯一可译码的方法-SardinasPatters

2、on算法。二、算法分析SardinasPatterson算法描述： 设C为码字集合，按以下步骤构造此码的尾随后缀集合F： (1) 考查C中所有的码字，若Wi是Wj的前缀，则将相应的后缀作为一个尾随后缀放入集合F0中； (2) 考查C和Fi两个集合，若WjC是WiFi的前缀或WiFi 是WjC的前缀，则将相应的后缀作为尾随后缀码放入集合Fi+1中； (3)F=Fi即为码C的尾随后缀集合； (4) 若F中出现了C中的元素，则算法终止，返回假(C不是唯一可译码)；否则若F中没有出现新的元素，则返回真。在我们设计的算法中，需要注意的是我们需要的是先输出所有尾随后缀的集合，然后再判断该码是否是唯一可译码

3、，即如F中出现了C中的元素，则C不是唯一可译码，否则若F中没有出现新的元素，则C为唯一可译码。而不是F中出现C中的元素就终止，这也是在本题的要求中需要注意的问题。简明流程图开始输入码字个数和码字进行尾随后缀编码判断是否为唯一码调用main（）函数结束三、概要设计：由于需要判断尾随后缀，所以我们需要反复的比较C和F中的码字。1） 首先我们用一个b4040的数组来存放所有的尾随后缀的集合；用Q记录所有尾随后缀的个数；2） 用数组a4040来存放输入的码字，L50来存放码字的长度；通过一个双重循环并调用Hz（ai,aj,Li,Lj）函数来找到a4040中的为随后缀，即：for(i=0;in-1;i+

4、) for(j=0;jn;j+) if(i!=j&LiLj) Hz(ai,aj,Li,Lj); 3） 通过判断Q是否大于0，如果不大于0，即b4040中没有码字，也就是不存在尾随后缀，那么可判断a4040是唯一可译码，否则进行如下操作；4） 计算b4040中尾随后缀的长度，用k1表示；并调用Hz(bi,aj,k1,Lj)其中k1Lj来a4040中所存在的后缀，并加入到b4040中，通过一个循环，找到a4040中所有尾随后缀；即 for(i=0;iQ;i+) k1=strlen(bi); for(j=0;jn;j+) if(k1Lj;通过循环调用即可找到b4040中的所有尾随后缀，最后再将他们分

5、别存放在b4040中；即通过 for(i=0;in;i+) for(j=0;jLi) Hz(ai,bj,Li,k2); 6） 在反复调用Hz(ai,aj,Li,Lj)函数中如果b4040中有重复出现的，即尾随后缀相同的不用再次放入b4040中。7） 在调用函数中所需要注意的问题就是一个比较的问题，也就是实现6）中所提到的。四、测试结果4.1、测试数据为0 10 1100 1110 1011 11014.2、测试数据为110 11 100 00 10五、源代码#include#includechar b4040;int Q;void Hz(char c,char d,int L1,int L2)

6、 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(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); prin

7、tf(请分别输入码字: ); 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(k1Lj) 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

8、;jQ;j+) if(strcmp(ai,bj)=0) temp=0; break; else continue; printf(n); if(temp=0)printf(该码不是唯一可译码!n); else printf(该码是唯一可译码!n); else printf(该码组是唯一可译码!); f+; printf(n);实习二：香农编码一、 题目分析对于给定的信源的概率分布，按照香农编码的方法进行计算机实现。二 、算法分析 2.1、算法基本原理给定某个信源符号的概率分布，通过以下的步骤进行香农编码：1）信源符号按概率从大到小排列；2）对信源符号求累加和，表达式： Pi=Pi-1+p(xi

9、)；3）求自信息量，确定码字长度。自信息量I(xi)=-log(p(xi);码字长度取大于等于自信息量的最小整数；4）将累加和用二进制表示，并取小数点后码字的长度的码 。简明流程图开始对概率进行降排序计算累加概率计算相应码长编码并输出码字调用main（）函数结束2.2、主要函数设计及分析1）paixu()函数本函数的功能主要是对用户输入的各个符号对应的概率进行降序排列，以便于计算累加概率和编码。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;i

10、n;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.19 0.17 0.15 0.10 0.01 0.18四、分析与探讨只是在对概率取对数并向上取整时遇到一定的困难，经过思考，利用上述的模拟手工出发圆满的解决了这一难题，使得程序能够得以完成。五、源代码#include#include#

11、includeusing 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)

12、/log(2);m=int(I);ki=m+1;void mazi(int *k,double *pa,string *str,int n) int i,j;double s;for(i=0;in;i+)s=pai;for(j=0;j=1) stri+=1;s=s-1;else stri+=0;void main()int n,i;coutn;double *p=new doublen;cout信源符号的概率依次为：;for(i=0;ipi;paixu(p,n);double *pa=new doublen;leijia(p,pa,n);int *k=new intn;length(p,k,n

13、);string *str=new stringn;mazi(k,pa,str,n);couttp(ai)tPa(aj)tKit码字endl;for(i=0;in;i+)couttpitpaitkitstriendl;实习三、费诺编码一、 题目分析对于给定的信源的概率分布，按照费诺编码的方法进行计二、算法分析2.1、算法基本原理1）、将信源发出的N个消息符号按其概率的递减次序依次排列。2）、将依次排列的信源符号依概率分成两组，使两个组的概率和近于相同，并对各组赋予一个二进制代码符号“0”和“1”（编m进制 码就分成m组）。3）、将每一个大组的信源符号进一步再分成两组，使划分后的两个组的概率和近

14、于相同，并又分别赋予两组一个二进制符号“0”和“1”4）、如此重复，直至每组值只剩下一个信源符号为止5）、信源符号所对应的码符号序列即为费诺码开始简明流程图输入概率并计算概率和 否概率和是1对概率进行降排序 是进行费诺编码输出编码结束2.2、函数详细设计及分析1）main()函数本函数实现的主要功能有：实现需要编码符号相关信息的输入；判断输入的概率和是否为1；调用费诺编码函数fano()；对排序后的概率进行编码并输出编码结果。2）fano()函数本函数的主要功能是实现编码过程的2）和3）。本函数是一个递归函数 分组代码如下：fano(float p,int aMM,int n,int m,in

15、t k) float g=0.0,h=0.0,d,b,c; int i,j,flase=0; if(nm) for(i=n;i=m;i+) g=pi+g; g=g/2; for(i=n;ig) d=h-pi;b=h-g;c=g-d;if(cb) for(j=n;j=i;j+) ajk=0;fano(p,a,n,i,k+1);for(j=i+1;j=m;j+) ajk=1;fano(p,a,i+1,m,k+1);else for(j=n;j=i-1;j+) ajk=0;fano(p,a,n,i-1,k+1);for(j=i;j=m;j+) ajk=1;fano(p,a,i,m,k+1);brea

16、k; 三、测试结果测试数据为：0.32 0.22 0.18 0.16 0.08 0.04运行结果为：四、分析与探讨费诺编码应该是概率小的符号码字长度一定大于概率大的符号的码字长度，但是符号码字的长度和概率的大小没有绝对的关系，只能说一般情况下，概率小的符号码字长度大于概率大的符号的码字长度。五、源代码#include#include#define M 25int paMM;void fano(float p,int aMM,int n,int m,int k) float g=0.0,h=0.0,d,b,c; int i,j,flase=0; if(nm) for(i=n;i=m;i+) g=

17、pi+g; g=g/2; for(i=n;ig) d=h-pi;b=h-g;c=g-d;if(cb) for(j=n;j=i;j+) ajk=0;fano(p,a,n,i,k+1);for(j=i+1;j=m;j+) ajk=1;fano(p,a,i+1,m,k+1);else for(j=n;j=i-1;j+) ajk=0;fano(p,a,n,i-1,k+1);for(j=i;j=m;j+) ajk=1;fano(p,a,i,m,k+1);break; void main() int i,j,kM,n,flase=0; float pM,m=0.0,sum=0.0; cout输入信源符号个数n; cout输入各信源符号概率endl; for(i=1;ipi; for(i=1;i=n;i