信息论与编码课程设计报.doc

信息论与编码课程设计报告姓名：时旭东专业:电科10-01学号：0指导老师：成凌飞完成日期：2013.03.20目录一课程描术。1二设计原理。2三设计内容。3四总结。22五参考文献。23一课程设计教学目的通过本次课程设计的练习，使学生进一步巩固信源熵、信源编码的基本原理，掌握具体的编码方法，熟悉编程软件的使用，培养学生自主设计、编程调试的开发能力，同时提高学生的实践创新能力。二题目一：判断唯一可译码一设计要求：利用尾随后缀法判断任意输入的码是否为唯一可译码。二题目分析： 设计一个程序实现判断输入码组是否为唯一可译码这一功能。在我们学习使用了克劳夫特不等式之后，知道唯一可译码必须满足克劳夫特不等式。但是克劳夫特不等式仅仅是存在性的判定定理，即该定理不能作为判断一种码是否为唯一可译码的依据。也就是说当码字长度和码符号数满足克劳夫特不等式时，则必可以构造出唯一可译码，否则不能构造出唯一可译码。因此我们必须找到一种能够判断一种码是否为唯一可译码的方法尾随后缀法。三算法分析：尾随后缀法算法描述： 设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中没有出现新的元素，则返回真。在我们设计的算法中，需要注意的是我们需要的是先输出所有尾随后缀的集合，然后再判断该码是否是唯一可译码，即如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;i<n-1;i+) for(j=0;j<n;j+) if(i!=j&&Li<Lj) Hz(ai,aj,Li,Lj); 3） 通过判断Q是否大于0，如果不大于0，即b4040中没有码字，也就是不存在尾随后缀，那么可判断a4040是唯一可译码，否则进行如下操作；4） 计算b4040中尾随后缀的长度，用k1表示；并调用Hz(bi,aj,k1,Lj)其中k1<Lj来a4040中所存在的后缀，并加入到b4040中，通过一个循环，找到a4040中所有尾随后缀；即 for(i=0;i<Q;i+) k1=strlen(bi); for(j=0;j<n;j+) if(k1<Lj) Hz(bi,aj,k1,Lj); 5） 寻找b4040中的尾随后缀；用k2表示b4040中码字的长度，并调用Hz(ai,bj,Li,k2)来实现，其中k2>Lj;通过循环调用即可找到b4040中的所有尾随后缀，最后再将他们分别存放在b4040中；即通过 for(i=0;i<n;i+) for(j=0;j<Q;j+) k2=strlen(bj); if(k2>Li) Hz(ai,bj,Li,k2); 6） 在反复调用Hz(ai,aj,Li,Lj)函数中如果b4040中有重复出现的，即尾随后缀相同的不用再次放入b4040中。7） 在调用函数中所需要注意的问题就是一个比较的问题，也就是实现6）中所提到的。五测试结果5.1、测试数据为0 10 1100 1110 1011 11015.2、测试数据为110 11 100 00 10五、源代码#include<stdio.h>#include<string.h>char b4040;int Q;void Hz(char c,char d,int L1,int L2) int i,j,temp=0; char m50; for(i=0;i<L1;i+) if(ci=di)continue;else break; if(i=L1) for(j=0;j<L2-L1;j+) mj=dL1+j; mj='0' for(i=0;i<Q;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;i<n;i+) scanf("%s",&ai); Li=strlen(ai); for(i=0;i<n-1;i+) for(j=0;j<n;j+) if(i!=j&&Li<Lj)Hz(ai,aj,Li,Lj); if(Q>0) for(i=0;i<Q;i+) k1=strlen(bi); for(j=0;j<n;j+) if(k1<Lj) Hz(bi,aj,k1,Lj); for(k=0;k<n;k+) for(j=0;j<Q;j+) k2=strlen(bj); if(k2>Lk) Hz(ak,bj,Lk,k2); printf("尾随后缀集合为:"); for(i=0;i<Q;i+) printf("%s ",bi); for(i=0;i<n&&temp!=0;i+) for(j=0;j<Q;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");题目二：哈夫曼编码1课题描述在这个信息量爆炸的时代，凡是能载荷一定信息量，且码字的平均长度最短，可分离的变长码的码字集合称为最佳变长码。为此，必须将概率大的信息符号编以短的码字，概率小的符号编以长的码字，使得平均码字最短。能获得最佳码的编码方法主要有：香农（Shannon）、费诺（Fano）、哈夫曼（Huffman）编码等。哈夫曼(Huffman)编码是一种常用的压缩编码方法，是Huffman于1952年为压缩文本文件建立的。它的基本原理是频繁使用的数据用较短的代码代替，较少使用的数据用较长的代码代替，每个数据的代码各不相同。哈夫曼压缩是个无损的压缩算法，一般用来压缩文本和程序文件。哈夫曼压缩属于可变代码长度算法一族。意思是个体符号用一个特定长度的位序列替代。因此，在文件中出现频率高的符号，使用短的位序列，而那些很少出现的符号，则用较长的位序列。哈夫曼编码是哈夫曼树的一个应用，是一种最优的前缀技术，然而其存在的不足却制约了它的直接应用。首先，其解码时间为O(lavg)，其中lavg为码字的平均长度；其次，更为重要的是，解码器需要知道哈夫曼编码树的结构，因而编码器必须为解码器保存或传输哈夫曼编码树。对于小量数据的压缩而言，这是很大的开销。因而，应用哈夫曼编码的关键是如何降低哈夫曼编码树的存储空间。目前流行的很多压缩方法都是用了该技术，如GZIB、ZLIB、PNC等。2设计原理对于多进制哈夫曼编码，为了提高编码效率，就要是长码的符号数量尽量少、概率尽量小，所以信源符号数量最好满足n=(m-1)*k+r,其中m为进制数，k为缩减的次数。设计步骤如下：1将信源符号按概率从大到小的顺序排列，令p(x1) p(x2) p(xn)2给两个概率最小的信源符号p(xn-1)和p(xn)各分配一个码位“0”和“1”，将这两个信源符号合并成一个新符号，并用这两个最小的概率之和作为新符号的概率，或者在新添加一个信源符号，令其概率为0，则个分配一个码位“0”、“1”和“2”，将其合并，结果得到一个只包含(n1)个信源符号的新信源。称为信源的第一次缩减信源，用S1表示。3将缩减信源S1的符号仍按概率从大到小顺序排列，此后每次合并3个信源符号，得到只含(n3)个符号的缩减信源S2。4重复上述步骤，直至最后，此时所剩符号的概率之和必为1。然后从最后一级缩减信源开始，依编码路径向前返回，就得到各信源符号所对应的码字。3 设计过程3.1软件介绍3.1.1 Visual C+ 6.0简介Visual C+ 6.0，简称VC或者VC6.0，是微软推出的一款C+编译器，将“高级语言”翻译为“机器语言（低级语言）”的程序。Visual C+是一个功能强大的可视化软件开发工具。自1993年Microsoft公司推出Visual C+1.0后，随着其新版本的不断问世，Visual C+已成为专业程序员进行软件开发的首选工具。Visual C+6.0由Microsoft开发, 它不仅是一个C+ 编译器，而且是一个基于Windows操作系统的可视化集成开发环境（integrated development environment，IDE）。Visual C+6.0由许多组件组成，包括编辑器、调试器以及程序向导AppWizard、类向导Class Wizard等开发工具。 这些组件通过一个名为Developer Studio的组件集成为和谐的开发环境。Microsoft的主力软件产品。Visual C+是一个功能强大的可视化软件开发工具。Visual C+6.0以拥有“语法高亮”，自动编译功能以及高级除错功能而著称。比如，它允许用户进行远程调试，单步执行等。还有允许用户在调试期间重新编译被修改的代码，而不必重新启动正在调试的程序。其编译及创建预编译头文件(stdafx.h)、最小重建功能及累加连结(link)著称。这些特征明显缩短程序编辑、编译及连结的时间花费，在大型软件计划上尤其显著。3.1.2主要部分1Developer Studio 图1 Developer Studio环境这是一个集成开发环境，我们日常工作的99%都是在它上面完成的，再加上它的标题赫然写着“Microsoft Visual C+”，所以很多人理所当然的认为，那就是Visual C+了。其实不然，虽然Developer Studio提供了一个很好的编辑器和很多Wizard，但实际上它没有任何编译和链接程序的功能，真正完成这些工作的幕后英雄后面会介绍。我们也知道，Developer Studio并不是专门用于VC的，它也同样用于VB，VJ，VID等Visual Studio家族的其他同胞兄弟。所以不要把Developer Studio当成Visual C+， 它充其量只是Visual C+的一个壳子而已。这一点请切记！ 2MFC从理论上来讲，MFC也不是专用于Visual C+，Borland C+，C+Builder和Symantec C+同样可以处理MFC。同时，用Visual C+编写代码也并不意味着一定要用MFC，只要愿意，用Visual C+来编写SDK程序，或者使用STL，ATL，一样没有限制。不过，Visual C+本来就是为MFC打造的，Visual C+中的许多特征和语言扩展也是为MFC而设计的，所以用Visual C+而不用MFC就等于抛弃了Visual C+中很大的一部分功能。但是，Visual C+也不等于MFC。 3Platform SDK这才是Visual C+和整个Visual Studio的精华和灵魂，虽然我们很少能直接接触到它。大致说来，Platform SDK是以Microsoft C/C+编译器为核心（不是Visual C+，看清楚了），配合MASM，辅以其他一些工具和文档资料。上面说到Developer Studio没有编译程序的功能，那么这项工作是由谁来完成的呢？是CL，是NMAKE，和其他许许多多命令行程序，这些我们看不到的程序才是构成Visual Studio的基石。3.2设计内容例：对如下单符号离散无记忆信源编三进制哈夫曼码。这里：m=3，n=8令k=3，m+k(m1)=9，则 s=9n=98=1所以第一次取ms=2个符号进行编码。由计算可得：平均码长为： （3.1）信息率为：（3.2）编码效率为：（3.3）可见：哈夫曼的编码效率相当高，对编码器的要求也简单得多。编码过程如下：表1 哈夫曼编码信源符号概率缩减信源码字码长0.40.090100.22201210 1.012010.181020.11120.11220.072120.062220.0520030.042013001212102图2 哈夫曼编码4编码程序及其分析/*哈夫曼编码*#include "stdio.h" #include"iostream.h" #include "math.h" #define MaxNo 100 typedef char ElemType; typedef struct ElemType dataMaxNo; double weight; /*信源概率*/ int parent,lchild,rchild; /*父亲和左右孩子节点*/ HTNode; typedef struct char cdMaxNo; /*存放编码用*/ int start; HCode; void CreateHCode(HTNode ht,HCode hcd,int n) /*哈夫曼编码子程序*/ int i,f,c; int choose; HCode hc;printf("请输入0或1进行编码方式选择："); /*方式选择*/ scanf("%d",&choose); for(i=0;i<n;i+) hc.start=n;c=i; f=hti.parent; if(choose=0) /*若选择0，则哈夫曼编码以先标0开始*/ while(f!=-1) if(htf.lchild=c) hc.cdhc.start-='0' else hc.cdhc.start-='1' c=f;f=htf.parent; hc.start+; hcdi=hc; else /*反之以先标1开始*/ while(f!=-1) if(htf.lchild=c) hc.cdhc.start-='1' else hc.cdhc.start-='0' c=f;f=htf.parent; hc.start+; hcdi=hc; void CreateHT(HTNode ht,int n) /*构造哈夫曼树子程序*/ int i,j,k; int s1,s2; /*节点*/ double min1,min2; for(i=0;i<2*n-1;i+) /*进行2*n-1次合并*/ hti.parent=hti.lchild=hti.rchild=-1; for(i=n;i<2*n-1;i+) min1=min2=32767; s1=s2=-1; for(k=0;k<=i-1;k+) /*不断循环组合最终生成Huffman树*/ if(htk.parent=-1) if(htk.weight<min1) min2=min1; s2=s1; min1=htk.weight; s1=k; else if(htk.weight<min2) min2=htk.weight; s2=k; hti.weight=hts1.weight+hts2.weight;/*组合树根节点权重为左右子之和*/ hti.lchild=s1; hti.rchild=s2; /*组合树左右子分别为s1,s2*/ hts1.parent=hts2.parent=i; /*新树加入数组*/ int main() int i,j,n; double average_length,sum=0; HTNode htMaxNo; HCode hcdMaxNo; float D100; /*各概率的对数 */ float H=0.00; float h100; /*存放信息熵*/ float R; /*编码效率*/cout<<"姓名：时旭东 学号：0"<<endl; cout<<"请输入信源符号个数："<<endl; while(scanf("%d",&n) cout<<"请输入各个信源符号及其概率，比如：A 0.12 ："<<endl; for(i=0;i<n;i+) scanf("%s%lf",&hti.data,&hti.weight); sum=hti.weight+sum; if(sum>1) /*避免总概率大于1*/ cout<<"概率大于1，请重新输入"<<endl; for(i=0;i<n;i+) Di=3.322*(-log10(hti.weight); hi=hti.weight*Di; /*各信源的熵*/ H=H+hi; CreateHT(ht,n); /*生成哈夫曼树*/ CreateHCode(ht,hcd,n); /*生成哈夫曼编码*/ cout<<"哈夫曼编码如下："<<endl; for(i=0;i<n;i+) printf("%s: ",hti.data); for(j=hcdi.start;j<=n;j+) printf("%c",hcdi.cdj); printf("n"); cout<<"下面将计算该码的平均码长、编码效率："<<endl; average_length=0; for(i=0;i<n;i+) average_length+=hti.weight*(n-hcdi.start+1); /*计算该信源的平均码长*/ cout<<"平均编码长度: K="<<average_length<<endl; R=H/average_length; /*编码效率*/ cout<<"编码效率: R="<<R<<endl; return 0; 二 截图图3 程序运行结果总 结在这次课程设计中，通过对程序的编写，调试和运行，使我更好的掌握了Huffman树等数据结构方面的基本知识和各类基本程序问题的解决方法，熟悉了各种调用的数据类型，在调试和运行过程中，加深我对程序运行的环境了解和熟悉的程度，同时也提高了我对程序调试分析的能力和对错误纠正的能力。这次信息论与编码的程序设计，对于我来说是一个挑战。我对数据结构的学习在程序的设计中也有所体现。课程设计是培养学生综合运用所学知识，发现问题、提出问题、分析问题和解决问题的过程，锻炼学生的逻辑思维能力和实践能力，是对学生实际工作能力的具体训练和考察过程。在整个课程程序中，我们充分应用和调用各个程序模块，从而部分实现了此次程序设计的所应该有的功能。就是我在课程设计是比较成功的方面，而在这个过程中，让我感觉收获最大的就是我们都能利用这次课程设计学到很多我们在课本上没有的知识，充分的发挥了我们的主动性，使我们学会了自主学习，和独立解决问题的能力。很多程序在结构上是独立的，但是本此设计的程序功能不是零散的，它有一个连接是的程序是一个整体，达到这种统一体十分重要，因为这个输出连接是贯穿始终的。这次的程序软件基本上运行成功，可以简单的输入进行压缩，并且运用简单的数字告诉程序的操作者下一步该如何进行，使得程序规模相对较小，即功能还不很全面，应用也不很普遍。原来数据结构可以涉及很多知识，而不是枯燥无聊的简单的代码部分而已，利用数据结构方面的知识，我们可以设计出更完善的软件。总而言之，这次数据结构课程设计让我们感触很深，使我们每个人都了解到学习不应该只局限于课本，因为课本上告诉我们的只是很有限的一部分，只是理论上的死知识，所涉及的范围也是狭窄的。我们若想在有限的范围内学习到无限的知识，就要我们自己懂得争取，懂得自学，懂得充分利用身边的任何资源。在我们的程序中有一部分查找许多该方面的资料，我竭力将所获得的信息变成自己的资源。我动手上机操作的同时，在了解和看懂的基础上对新学的知识进行改进和创新，但是在我们的程序软件中还有很多的不足，需要加以更新。通过这次课程设计，我们都意识到了自己动手实践的弱势，特别是在编程方面，于是我们知道了计算机的实践操作是很重要的，只有通过上机编程才能充分的了解自己的不足。通过这次的课程设计，我们深刻意识到自己在学习中的弱点，同时也找到了克服这些弱点的方法，这是在此活动中得到的一笔很大的财富。在以后的时间中，我们应该利用更多的时间去上机实验，多编写程序，相信不久后我们的编程能力都会有很大的提高，能设计出更多的更有创新的软件。同时也感谢老师给我们这次机会，发现自身存在的缺点与不足，从而在以后的大学生活中更好的提升和完善自我。参考文献1 傅祖芸.信息论基础理论与应用（第二版）.北京：电子工业出版社，2007.52 傅祖芸.信息论基础.北京：电子工业出版社，19893 R W汉明.朱雪龙译.编码和信息理论.北京：科学出版社，19844 王育民，梁传甲.信息与编码理论.西安：西安电子科技大学出版社，19865 周炯槃.信息理论基础.北京：人民邮电出版社，19836 钟义信.信息科学原理.北京：北京邮电大学出版社，1996