信息论与编码课程设计.docx

信息论与编码课程设计 报 告 书 学 院： 电气工程与自动化 专业班级： 指导老师： 成凌飞 团队成员： 本案作者： 学 号： 完成日期： 2013年3月26日 摘要 信息是从人类出现以来就存在于这个世界上，人类社会的生存和发展都离不开信息的获取、传递、处理、再生、控制和处理。而信息论正是一门把信息作为研究对象，以揭示信息的本质特性和规律为基础，应用概率论、随即过程和数理统计等方法来研究信息的存储、传输、处理、控制、和利用等一般规律的学科。主要研究如何提高信息系统的可靠性、有效性、保密性和认证性，以使信息系统最优化。在信息论的指导下，信息技术得到飞速发展，这使得信息论渗透到自然科学和社会科学的所有领域，并且应用与众多领域：编码学、密码学与密码分析、数据压缩、数据传输、检测理论、估计理论等。信息论的主要基本理论包括：信息的定义和度量；各类离散信源和连续信源的信源熵；有记忆，无记忆离散和连续信道的信道容量，平均互信息；无失真信源编码相关理论。 求离散性信源熵也是信息论课程实践学习中必须要经历，在了解常规的求解方式的同时，利用计算机语言进行实践编程。用预先规定的方法将文字、数字或其他对象编成数码，或将信息、数据转换成规定的电脉冲信号。编码在电子计算机、电视、遥控和通讯等方面广泛使用。其中哈夫曼编码有广泛的应用,通过本次实验,了解编码的具体过程,通过编程实现编码。本次实验所使用的机器语言均为C语言。关键字：信息论 离散和连续信源熵 哈夫曼编码 C语言编程设计目录摘要- 1 -第一章 课程设计概述及意义- 3 -第二章 设计任务与要求- 3 -1、设计目的- 3 -1.1- 3 -1.2- 3 -1.3- 3 -1.4- 4 -1.5- 4 -2设计内容- 4 -3设计要求- 4 -4设计条件- 4 -5设计思路- 4 -6.离散平稳信源熵求解说明- 5 -7.哈夫曼编码编程方式说明- 5 -第三章 设计流程图- 6 -1.信源熵编程计算设计流程图- 7 -2.哈夫曼编码程序设计流程图- 8 -3.软件介绍- 8 -3.1 Visual C+ 6.0简介- 8 -3. 2主要部分- 9 -第三章 程序运行及结果- 10 -1.计算信源熵结构截图- 10 -2.哈夫曼树编程截图结果- 11 -3.设计内容举例结果分析- 11 -第五章 课程设计心得体会- 13 -附录- 14 -1.参考文献- 14 -2.哈幅曼树调试程序- 14 -3.信源熵计算调试程序- 19 -第一章 课程设计概述及意义本课程设计是在学习了信息论与编码和相关开发的软件课程后，让我们通过实际的操作来熟悉信源编码微机实现，培养我们能够独立的完成对相关课题或者项目的分析能力、设计能力和调试能力。本课程设计是衔接在C课程、数据结构课程设计之后的，运用程序思想来完成的，联系信息论与编码所学内容，要求有独立的操作界面。在这次的课程设计中，着重培养的是我们的自学能力，以及独立分析互联网上和图书馆里的各种资料，来丰富自己的知识并且提高对数学公式的计算机实现、VC+等软件的实际操作能力。通过这次的课程设计，能够使我们对已经学习过的信息论与编码课程的进一步的掌握，能够对知识进行最大程度的消化融汇。因此这次的课程设计对我们有着非常重要的意义。 本课程设计中用VC编写出基于visual studio2010界面的简单软件以实现压缩信源熵求解及哈夫曼编码的目的。经过比较系统合理的编程操作，实现可视化的窗口以方便用户使用。通过简单校验确保信源正确性，保证软件的可靠性。最终将结果保存为文档方便记录编码结果。 通过让完成具体编码算法的程序设计和调试工作，达到提高编程能力和深刻理解编码理论及信源熵求解的目的。培养我们使用计算机和查阅参考资料的能力，提高我们的基本设计能力。培养了理论联系实际和独立思考的能力。并激发我们的实际开发创造的意识和能力。培养和提高我们的自学能力以及综合运用所学理论知识去分析解决实际问题的能力。第二章 设计任务与要求1、设计目的 1.1深刻理解信源熵的计算方法；1.2深刻理解信源编码的基本思想与目的；1.3理解哈夫曼编码方法的基本过程与特点；1.4提高综合运用所学理论知识独立分析和解决问题的能力；1.5提高使用C语言或其他语言进行编程的能力，以及visual studio 软件的应用能力。2设计内容 首先对拖入文件中的字符总个数进行统计 ，然后从文本头开始查找同一字符个数，并计算 其概率 最后由得出的字符概率求得信源熵 假设已知一个信源的各符号概率，编写适当函数，对其进行哈夫曼编码，得出M进制码字，平均码长和编码效率，总结此编码方法的特点和应用。3设计要求1、编写的函数要有通用性；2 学生可独立完成，或组队共同完成。每队人数不多于4人。3、提交一份独立完成的课程设计报告（纸质和电子版），做5分钟PPT汇报，并演示程序。每队选择1人汇报和演示程序，其他人答辩。4、课程设计报告包括设计任务与要求、设计思路、设计流程图、程序运行及结果、心得体会、参考文献、附录（源程序）等内容。4设计条件1、计算机、C语言或其他语言环境2、设计软件 visual studio20105设计思路信源熵的定义：信源各个离散消息的自信息量的数学期望 首先对拖入文件中的字符总个数进行统计，然后从文本头开始查找同一字符个数，并计算其概率，最后由得出的字符概率求得信源熵。 假设每种字符在电文中出现的次数为Wi，编码长度为Li，电文中有n种字符，则电文编码总长度为(W1*L1)+(W2*L2)+(Wi*Li)。若将此对应到二叉树上，Wi为叶结点，Li为根结点到叶结点的路径长度。那么，(W1*L1)+(W2*L2)+(Wi*Li)恰好为二叉树上带权路径长度。 因此，设计电文总长最短的二进制前缀编码，就是以n种字符出现的频率作权，构造一棵哈夫曼树6.离散平稳信源熵求解说明离散平稳信源也是一种非常重要的信源。不同时刻信源输出符号的概 率分布完全相同，则称为一维离散平稳信源。二维离散平稳信源就是信源输出的随机序列，X1,X2,Xi，满足其一维和二维概率分布与时间起点无关。这种各维联合概率分布均匀与时间起点无关的完全平稳信源称离散平稳信源。二维离散平稳信源的联和熵为：，此值表示原来信源X输出任意一对可能的消息的共熵，即描述信源X输出长度为2的平均不确定性，或所含的信息量，因此可用作为二维离散平稳信源的信息熵的近似值。在通信系统的各种信源中，离散随机信源是最基本的一种信源，信源输出是单个的符号的消息，并且消息之间是两两互不相容的。我们知道，事件发生的不确定性与事件发生的概率有关：事件的发生概率越小，不确定性就越大，事件发生的概率越大，不确定性就越小，对于发生概率为1的必然事件就不存在不确定性。设一离散信源的概率空间为： . . 即，如果知道已发生，则该事件所含有的信息量称自信息，表达式为：上面的自信息是指某一信源发出某一消息所含的信息量，但所发消息不同，它们所含信息量也就不同，所以自信息不能作为整个信源的信息测度，我们定义平均自信息量，即对每个事件各自所携带的信息量做一个加权平均，也称信息熵，表示如下：信息熵具有一些基本的性质，比如，对称性，确定性，非负性，扩展性，可加性等等。这里面有一个最大离散熵定理，表明:离散信源情况下，对于具有q个符号的离散信源，只有在q个信源符号等可能出现的情况下，信源熵才能达到最大值，这样也表明等概率分布信源的平均不确定性为最大。7.哈夫曼编码编程方式说明哈夫曼编码(Huffman Coding)是一种编码方式，也是可变字长编码(VLC)的一种。这种方法完全依据字符出现的概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫作哈夫曼编码。对于M进制哈弗曼编码，为了提高编码效率，就要使长码的符号数量尽量少、概率尽量小，所以应使合并的信源符号位于缩减信源序列尽可能高的位置上，以减少再次合并的次数，充分利用短码。在这个信息量爆炸的时代，凡是能载荷一定信息量，且码字的平均长度最短，可分离的变长码的码字集合称为最佳变长码。为此，必须将概率大的信息符号编以短的码字，概率小的符号编以长的码字，使得平均码字最短。能获得最佳码的编码方法主要有：香农（Shannon）、费诺（Fano）、哈夫曼（Huffman）编码等。哈夫曼(Huffman)编码是一种常用的压缩编码方法，是Huffman于1952年为压缩文本文件建立的。它的基本原理是频繁使用的数据用较短的代码代替，较少使用的数据用较长的代码代替，每个数据的代码各不相同。哈夫曼压缩是个无损的压缩算法，一般用来压缩文本和程序文件。哈夫曼压缩属于可变代码长度算法一族。意思是个体符号用一个特定长度的位序列替代。因此，在文件中出现频率高的符号，使用短的位序列，而那些很少出现的符号，则用较长的位序列。哈夫曼编码是哈夫曼树的一个应用，是一种最优的前缀技术，然而其存在的不足却制约了它的直接应用。首先，其解码时间为O(lavg)，其中lavg为码字的平均长度；其次，更为重要的是，解码器需要知道哈夫曼编码树的结构，因而编码器必须为解码器保存或传输哈夫曼编码树。对于小量数据的压缩而言，这是很大的开销。因而，应用哈夫曼编码的关键是如何降低哈夫曼编码树的存储空间。目前流行的很多压缩方法都是用了该技术，如GZIB、ZLIB、PNC等。对于多进制哈夫曼编码，为了提高编码效率，就要是长码的符号数量尽量少、概率尽量小，所以信源符号数量最好满足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。然后从最后一级缩减信源开始，依编码路径向前返回，就得到各信源符号所对应的码字。第三章 设计流程图1.信源熵编程计算设计流程图 2.哈夫曼编码程序设计流程图3.软件介绍3.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. 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的基石。第三章 程序运行及结果1.计算信源熵结构截图2.哈夫曼树编程截图结果3.设计内容举例结果分析例：对如下单符号离散无记忆信源编三进制哈夫曼码。这里：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 哈夫曼树 第五章 课程设计心得体会此次课程设计，受益颇多。将书本上的理论知识应用到实例中，进一步掌握了信源熵与与哈夫曼编码的相关知识点，也更熟悉的掌握了C语言编码。在课程设计的过程中，也遇到了一些问题，但这也正是课程设计的目的所在，发现自身的不足。我们深刻意识到自己在学习中的弱点，同时也找到了克服这些弱点的方法，这是在此活动中得到的一笔很大的财富。在以后的时间中，我们应该利用更多的时间去上机实验，多编写程序，相信不久后我们的编程能力都会有很大的提高。同时也感谢老师给我们这次机会，发现自身存在的缺点与不足，从而在以后的大学生活中更好的提升和完善自我。附录 1.参考文献1曹雪虹，张宗橙.信息论与编码.北京：清华大学出版社，2007.2王慧琴.数字图像处理.北京：北京邮电大学出版社，2007.3严蔚敏，吴伟民.数据结构（C语言版）。北京：清华大学出版社，2009.4贾宗璞，许合利.C语言程序设计：人民邮电出版社,2010.2.哈幅曼树调试程序#include #include #include #include #include #define KongJian 200typedef struct Hafumanchar ZiMu;double weight;int parent,lchild,rchild;HTNode, *HafumanTree;typedef char* *HafumanCode;void initial(HafumanTree &HT, int n)for(int i = 0; i 1.0)printf(输入有错误，请关闭命令窗重新运行n);elseprintf(n请输入第%d个符号:,i+1);scanf( %c,&HTi.ZiMu);printf(n 请输入 %c的概率:,(HT+i)-ZiMu);scanf( %lf,&HTi.weight);sum += (HT+i)-weight ;*H = *H + ( - log(HTi.weight) * HTi.weight ) /log(2.0);HTi.lchild = HTi.rchild = i;printf(n实验结果如下：n);initial(HT, i);return i;void select(HafumanTree s, int n, int* a, int* b)double min = 1.0;for(int i = 0; i (s+i)-weight ) & (s+i)-parent = 0 )min = (s+i)-weight;*a = i;min = 1.0;for(int i = 0; i (s+i)-weight & (s+i)-parent = 0 )min = (s+i)-weight;*b = i;void creatHafumanTree(HafumanTree &HT, int n)int s1 = 0,s2 = 0;for( int i = n; i 2 * n - 1; i+)select(HT, i, &s1, &s2);HTs1.parent = i;HTs2.parent = i;HTi.lchild = s1;HTi.rchild = s2;HTi.weight = HTs1.weight + HTs2.weight;int cmp(const void* a, const void* b)return -1;int creatHafumanCode(HafumanTree HT, HafumanCode &HC, int n, double* CL)if( (HC = (HafumanCode)malloc( n * sizeof(char*) = NULL)return 0;char* code = NULL;int num_1 = 0,j = 0,start = 0,number = 0;for (int i=0; i n; i+)if( (code = (char*)malloc( n * sizeof(char) ) ) = NULL )return 0;start = 0;num_1 = HTi.parent;j = i;while ( num_1 != 0 )if( HTnum_1.lchild = j )codestart+ = 0;elsecodestart+ = 1;number += 1;j = num_1;num_1 = HTj.parent;qsort(code, start, sizeof(char), cmp);*(code+start) = 0;HCi = code;*CL = (double)number/(double)n;void print(HafumanTree HT, HafumanCode HC, int n, double H, double CL)for( int i = 0; i n; i+)printf(n%c的编码是: ,HTi.ZiMu);puts(HCi);printf(n 信源熵是：%f.,H);printf(n 编码效率为：%f%.,(H/CL)*100);int main(void)HafumanTree string = NULL;HafumanCode code_string = NULL;double CL = 0.0;double H = 0.0;int length = 0;length = input(string, &H);creatHafumanTree(string, length);creatHafumanCode(string, code_string,length, &CL);print(string, code_string, length, H, CL);printf(nn本次试验成功!n);free(string);free(code_string);return 0;3.信源熵计算调试程序#include#include #include #includeint check(char* s);void initial(void);struct Shujulong in