zhoujie信息论编码

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

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

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

4、随后缀， 即：for(i=0;in-1;i+) 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+)

5、 if(k1Lj; 通过循环调用即可找到 b4040 中的所有 尾随后缀，最后再将他们分别存放在 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 1101* G ：D卡 b u gF oha 口 n o n .ex存陣干10 1100 合为=11

6、03 1 司诣码？1110110丄1 1101 a 100 an101Press any key to continue4.2、测试数据为 110 11 100 00 10G:DebugFa no_Sh 自入次屈疋 解随码 青主旦5 1 f 110码. 卞码合可 頁集一*ress anV key to con)tinue、源代码#in clude#in cludechar 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)c ontinue;else

7、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);printf( 请分别输入码字 : ); for(i=0;in;i+)scanf(%s,&ai);Li=strlen(ai);for(i=0;in-1;i+)

8、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;jQ;j+)if(strcmp(ai,bj)=0)temp=0;break;else continue;printf(n);!n);if(temp=0)printf( 该

9、码不是唯一可译码 else printf( 该码是唯一可译码 !n);else printf( 该码组是唯一可译码 !);f+;printf(n);实习二：香农编码一、题目分析对于给定的信源的概率分布，按照香农编码的方法进行计算机实现。二、算法分析2.1、算法基本原理给定某个信源符号的概率分布，通过以下的步骤进行香农编码：1) 信源符号按概率从大到小排列；2) 对信源符号求累加和，表达式：Pi=R-i +p(xj ；码字长度取大于等于自3) 求自信息量，确定码字长度。自信息量l(x i)=-log(p(x 小; 信息量的最小整数；4) 将累加和用二进制表示，并取小数点后码字的长度的码。 简明流

10、程图2.2、主要函数设计及分析1) paixu()函数以便于计算累加本函数的功能主要是对用户输入的各个符号对应的概率进行降序排列, 概率和编码。for(i=0;i n-1;i+)for(j=i+1;j n;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

11、;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经过思考，利用上述的模拟手工出* G:De bugF3no_Shannor.exe*宿源符号个数n =?彳言源特号的辄率依次为0-2 6-190.18 0.17 0.15 0.1 0.01Pa Ki码字0-2030000.190.230010.180-3930110.170.5731000.150.7431010.10.894111e.m0.9971111110Press anyto continue

12、H四、分析与探讨只是在对概率取对数并向上取整时遇到一定的困难, 发圆满的解决了这一难题，使得程序能够得以完成。五、源代码#in clude#in clude#in cludeusing n amespace std;void paixu(double *p,i nt n)int i,j;double e=0.0;for(i=0;i n-1;i+)for(j=i+1;j n;j+)if(pipj)e=pi;pi=pj;pj=e;void leijia(double *p,double *pa,i nt n)int i;double sum=0.0;for(i=0;in;i+)pai=sum;su

13、m+=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,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

14、(i=0;ipi; paixu(p,n); double *pa=new doublen; leijia(p,pa,n);int *k=new intn; length(p,k,n); string *str=new stringn; mazi(k,pa,str,n); couttp(ai)tPa(aj)tKit 码字 endl;for(i=0;in;i+) couttpitpaitkitstri endl;实习三、费诺编码一、题目分析对于给定的信源的概率分布，按照费诺编码的方法进行计二、算法分析2.1、算法基本原理1) 、将信源发出的N个消息符号按其概率的递减次序依次排列。2) 、将依次排列

15、的信源符号依概率分成两组，使两个组的概率和近于相同，并对各组赋予一个二进制代码符号 0”和“1”(编m进制 码就分成m组)。3) 、将每一个大组的信源符号进一步再分成两组，使划分后的两个组的概率和近于相同，并又分别赋予两组一个二进制符号0”和1 ”4) 、如此重复，直至每组值只剩下一个信源符号为止5) 、信源符号所对应的码符号序列即为费诺码 简明流程图开始输入概率并计算概率和对概率进行降排序进行费诺编码1卩输出编码结束2.2、函数详细设计及分析1) main()函数本函数实现的主要功能有：实现需要编码符号相关信息的输入；判断输入的概率和是否为1;调用费诺编码函数fano();对排序后的概率进行

16、编码并输出编码结果。2) fano()函数本函数的主要功能是实现编码过程的2)和3)。本函数是一个递归函数分组代码如下：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=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);elsef

17、or(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;三、测试结果 测试数据为： 0.32 0.22 0.18 0.16 0.08 0.04 运行结果为：G:Deb u gFa 口 o_Shd nnon. exe渝入各信源符号概率.32 0.22 U.18 0.16信源费诺编码如下；0061101101110111108 8.041=0.322=0.224=0.165=0.08 6=004码壬为码李为码码码码码rm22234fi*ess siny key to con

18、tinue四、分析与探讨费诺编码应该是概率小的符号码字长度一定大于概率大的符号的码字长度，但是符号码字的长度和概率的大小没有绝对的关系，只能说一般情况下，概率小的符号码字长度大于概率大的符号的码字长度。五、源代码#in clude#in clude#defi neM 25int paMM;voidfano(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=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);elsefor(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 输入各信源符号概率 e