信息论与编码课程设计..
吉林建筑大学电气与电子信息工程学院信息理论与编码课程设计报告设计题目：哈夫曼编码的分析与实现专业班级：电子信息工程101学生姓名：学 号:指导教师：吕卅王超设计时间：2013.11.18—2013.11.29教师评语：成绩评阅教师日期信息论与编码课程设计 ..一、设计的作用、目的《信息论与编码》 是一门理论与实践密切结合的课程 ,课程设计是其实 践性教学环节之一，同时也是对课堂所学理论知识的巩固和补充其主要 目的是加深对理论知识的理解， 掌握查阅有关资料的技能， 提高实践技能， 培养独立分析问题、解决问题与实际应用的能力通过完成具体编码算法的程序设计和调试工作，提高编程能力，深刻 理解信源编码、信道编译码的基本思想和目的，掌握编码的基本原理与编 码过程，增强逻辑思维能力，培养和提高自学能力以与综合运用所学理论 知识去分析解决实际问题的能力，逐步熟悉开展科学实践的程序和方法二、设计任务与要求通过课程设计各环节的实践，应使学生达到如下要求：1. 理解无失真信源编码的理论基础，掌握无失真信源编码的基本方法；2. 掌握哈夫曼编码 / 费诺编码方法的基本步骤与优缺点；3. 深刻理解信道编码的基本思想与目的，理解线性分组码的基本原 理与编码过程；4. 能够使用 MATLAB 或其他语言进行编程， 编写的函数要有通用性。
三、设计内容一个有8个符号的信源X，各个符号出现的概率为：X x1, x2, x3, x4, x5, x6 x7 x8P(X) 0.4 0.18 0.1 0.1 0.07 0.06 0.05 0.04编码方法：先将信源符号按其出现的概率大小依次排列，并取概率最 小的字母分别配以 0 和 1 两个码元(先 0 后 1或者先 1 后 0，以后赋值固定），再将这两个概率相加作为一个新字母的概率，与未分配的二进制符 号的字母重新排队并不断重复这一过程，直到最后两个符号配以 0 和 1 为止最后从最后一级开始，向前返回得到各个信源符号所对应的码元序 列，即为对应的码字哈夫曼编码方式得到的码并非唯一的在对信源缩减时，两个概率最 小的符号合并后的概率与其他信源符号的概率相同时，这两者在缩减中的 排序将会导致不同码字，但不同的排序将会影响码字的长度，一般讲合并 的概率放在上面，这样可获得较小的码方差四、设计原理4.1 哈夫曼编码步骤（1）将信源消息符号按照其出现的概率大小依次排列为p1 p2 pn（2）取两个概率最小的字母分别配以 0 和 1 两个码元， 并将这两个概 率相加作为一个新的概率，与未分配的二进制符号的字母重新排队。
3）对重新排列后的两个最小符号重复步骤（ 2）的过程 4）不断重复上述过程，知道最后两个符号配以 0 和 1 为止 5）从最后一级开始， 向前返回得到的各个信源符号所对应的码元序 列，即为相应的码字4.2 哈夫曼编码特点哈夫曼编码是用概率匹配的方法进行信源匹配方法进行信源它的特 点是：（1 ）哈夫曼的编码方法保证了概率大的符号对应于短码， 概率小的符 号对应于长码，充分应用了短码2 ）缩减信源的最后两个码字总是最后一位不同， 从而保证了哈夫曼 编码是即时码3 ）哈夫曼编码所形成的码字不是唯一的， 但编码效率是唯一的， 在 对最小的两个速率符号赋值时可以规定大的为“ 1”，小得为“ 0 ”，如果两 个符号的出现概率相等时，排列时无论哪个在前都可以，所以哈夫曼所构 造的码字不是唯一的，对于同一个信息源，无论上述的顺序如何排列，他 的平均码长是不会改变的，所以编码效率是唯一的4 ）只有当信息源各符号出现的概率很不平均的时候， 哈夫曼编码的 效果才明显5 ）哈夫曼编码必须精确的统计出原始文件中每个符号出现频率， 如果没有这些精确的统计将达不到预期效果哈夫曼编码通常要经过两遍操 作 ，第一遍进行统计，第二遍产生编码，所以编码速度相对慢。
另外实 现电路复杂，各种长度的编码的编译过程也是比较复杂的，因此解压缩的 过程也比较慢6 ）哈夫曼编码只能用整数来表示单个符号， 而不能用小数， 这很大 程度上限制了压缩效果哈夫曼所有位都是合在一起的，如果改动其中一 位就可以使其数据变得面目全非五、设计步骤5.1 以框图形式画出哈夫曼编码过程（哈夫曼编码要求构建哈夫曼树） 表 1 哈夫曼编码哈夫曼树:给定n个实数w1 , w2 , , wn (n 2),求一个具有 n个结点的二叉数，使其带权路径长度最小所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度(若根结点为 0层，叶结点到根结点的路径长度为叶结点的层数)树的带权路径长度为WPL=(W1*L1+W2*L2+W3*L3+...+Wn*Ln) ，N 个权值 Wi(i=1,2,...n)构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为 Li(i=1,2,...n)可以证明哈夫曼树的 WPL是最小的1) 根据与n个权值{w1,w2 --wn}对应的n个结点构成具有n棵二 叉树的森林F={T1,T2 n},其中第i棵二叉树Ti(1 i n)都只有一个权值为wi的根结点，其左、右子树均为空。
2) 在森林F中选出两棵根结点的权值最小的树作为一棵新树的左、 右子树，且置新树的根结点的权值为其左、右子树上根结点权值之和3) 从F中删除构成新树的那两棵，同时把新树加入 F中4) 重复第(2)和第(3 )步，直到F中只含有一棵为止，此树便为Huffman 树图1哈夫曼树5.2计算平均码长、编码效率、冗余度平均码长为：K==0.4 X1+0.18 X3+0.1 X3+0.1 X4+0.07 X4+0.06 X4+0.05 X5+0.04 X5=2.61 (码元 / 符号)信源熵为：nH(X) p(xi)log p(xi) i 1log0.04)=2.55bit/ 符号 信息传输速率为：2 55R== 2.55 =0.977bit/ 码元 2.61编码效率为:2.552.61=0.977冗余度为:=1- =1-0.977=0.023六、哈夫曼编码的实现6.1软件介绍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 )VisualC++6.0由许多组件组成，包括编辑器、调试器以与程序向导 AppWizard 、 类向导Class Wizard 等幵发工具 这些组件通过一个名为 DeveloperStudio的组件集成为和谐的幵发环境Microsoft的主力软件产品Visual C++是一个功能强大的可视化软件幵发工具Visual C++6.0 以拥有“语法高亮"，自动编译功能以与高级除错功 能而著称比如，它允许用户进行远程调试，单步执行等还有允许用户 在调试期间重新编译被修改的代码，而不必重新启动正在调试的程序其 编译与创建预编译头文件 （stdafx.h） 、最小重建功能与累加连结 （link） 著称 这些特征明显缩短程序编辑、编译与连结的时间花费，在大型软件计划上 尤其显著1） Developer Studio 这是一个集成开发环境，我们日常工作的99% 都是在它上面完成的，再加上它的标题赫然写着“ VisMuaicl rosoftC++ ”，所以很多人理所当然的认为，那就是 Visual C++ 了。
其实不然，虽然 Developer Studio 提供了一个很好的编辑器和很多 Wizard ，但实际 上它没有任何编译和链接程序的功能，真正完成这些工作的幕后英雄后面 会介绍我们也知道， Developer Studio 并不是专门用于 VC 的，它也同 样用于 VB ，VJ，VID 等 Visual Studio 家族的其他同胞兄弟所以不要把 Developer Studio 当成 Visual C++ ， 它充其量只是 Visual C++ 的一个 壳子而已这一点请切记！（2）MFC从理论上来讲， 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 3）Platform SDK这才是 Visual C++ 和整个 Visual Studio 的精华和灵魂， 虽然我们很少能直接接触到它大致说来， Platform SDK 是以 Microsoft C/C++ 编 译器为核心（不是 Visual C++ ，看清楚了），配合 MASM ，辅以其他一 些工具和文档资料上面说到 Developer Studio 没有编译程序的功能， 那么这项工作是由谁来完成的呢？是 CL,是NMAKE ,和其他许许多多命令行程序，这些我们看不到的程序才是构成 Visual Studio 的基石6.2 编程//** 哈夫曼编码 **#include
2） 缩减信源的最后两个码字总是最后一位不同， 从而保证了哈夫曼 编码是即时码3） 每次缩减信源的最长两个码字有相同的码长这三个特点保证了所得的哈夫曼码一定是最佳码因此哈夫曼是一种 应用广泛而有效的数据压缩技术利用哈夫曼编码进行通信可以大大提高 信道利用率，加快信息传输速度，降低传输成本数据压缩的过程称为编 码，解压的过程称为译码进行信息传递时，发送端通过一个编码系统对 待传数据（明文）预先编码，而接受端将传来的数据（密文）进行译码 要求数据这样一个简单的哈夫曼编码译码器在进行哈夫曼编码时，为了得到码方差最小的码，应使合并的信源符 号位于缩减信源序列尽可能高的七、体会与建议在这次课程设计中，通过对程序的编写，调试和运行，使我更好的掌 握了哈夫曼树等数据结构方面的基本知识和各类基本程序问题的解决方 法，熟悉了各种调用的数据类型，在调试和运行过程中，加深我对程序运 行的环境了解和熟悉的程度，同时也提高了我对程序调试分析的能力和对信息论与编码课程设计 ..错误纠正的能力这次信息论与编码的程序设计，对于我来说是一个挑战我对数据结 构的学习在程序的设计中也有所体现课程设计是培养学生综合运用所学 知识，发现问题、提出问题、分析问题和解决问题的过程，锻炼学生的逻 辑思维能力和实践能力，是对学生实际工作能力的具体训练和考察过程。
在整个课程程序中，我们充分应用和调用各个程序模块，从而部分实现了 此次程序设计的所应该有的功能就是我在课程设计是比较成功的方面， 而在这个过程中，让我感觉收获最大的就是我们都能利用这次课程设计学 到很多我们在课本上没有的知识，充分的发挥了我们的主动性，使我们学 会了自主学习，和独立解决问题的能力很多程序在结构上是独立的，但是本此设计的程序功能不是零散的， 它有一个连接是的程序是一个整体，达到这种统一体十分重要，因为这个 输出连接是贯穿始终的通过翻阅相关书籍，在网上查询资料学习有关哈夫曼编码的实现过 程，我实 在是获益匪浅，更加深刻的感觉到哈夫曼编码能够大大提高通信的效率， 对于我们通信工程专业来说，学好这门科学是非常重要的，在以后的图像 处理和压缩方面这门学科能给我们很大的帮助同时，学习这门科学也是 艰辛的，因为它比较难懂，这不仅需要我们发挥我们的聪明才智，还需要 我们在不断的实践中领悟 这次的课程设计，让我体会到了作为一个编 程人员的艰辛，一个算法到具体实现，再到应用层面的开发是需要有一个 较长的路要走的，不是一朝一夕就可以实现的，而且在编好程序后，编程信息论与编码课程设计人员还要花很多时间去完善， 过程是心酸的， 外人很难能够真正明白。
后我要更加努力的学习专业知识，提高自我的能力！这次的程序软件基本上运行成功，可以运用简单的数字告诉程序的操 作者下一步该如何进行，使得程序规模相对较小，即功能还不很全面，应 用也不很普遍原来数据结构可以涉与很多知识，而不是枯燥无聊的简单 的代码部分而已，利用数据结构方面的知识，我们可以设计出更完善的软 件总而言之，这次数据结构课程设计让我们感触很深，使我们每个人都 了解到学习不应该只局限于课本，因为课本上告诉我们的只是很有限的一 部分，只是理论上的死知识，所涉与的范围也是狭窄的我们若想在有限 的范围内学习到无限的知识，就要我们自己懂得争取，懂得自学，懂得充 分利用身边的任何资源在我们的程序中有一部分查找许多该方面的资料，我竭力将所获得的 信息变成自己的资源我动手上机操作的同时，在了解和看懂的基础上对 新学的知识进行改进和创新，但是在我们的程序软件中还有很多的不足， 需要加以更新 通过这次课程设计， 我们都意识到了自己动手实践的弱势， 特别是在编程方面，于是我们知道了计算机的实践操作是很重要的，只有 通过上机编程才能充分的了解自己的不足通过这次的课程设计，我们深刻意识到自己在学习中的弱点，同时也 找到了克服这些弱点的方法，这是在此活动中得到的一笔很大的财富。
在 以后的时间中，我们应该利用更多的时间去上机实验，多编写程序，相信 不久后我们的编程能力都会有很大的提高，能设计出更多的更有创新的软信息论与编码课程设计件同时也感谢老师给我们这次机会，发现自身存在的缺点与不足，从而在以后的大学生活中更好的提升和完善自我八、参考文献[1] 曹雪虹， 张宗橙 .信息论与编码 （第二版） .北京： 清华大学出版社 .2009[2] 吕锋，王虹，刘皓春，苏扬 .信息论与编码 .北京：人民邮电出版社 .2004[3] 樊昌信，曹丽娜 .通信原理（第六版） .北京：国防工业出版社 .2006[4] 王慧琴 .数字图像处理 .北京：北京邮电大学出版社 .2007[5] 孙丽华 . 信息论与纠错编码 .电子工业出版社 .2005[6] 刘宏 .C++ 程序设计教程 .武汉：武汉大学出版社， 2005[7] 杨永国，张冬明.Visual C++6.0 实用教程.北京：清华大学出版社，2007[8] 严蔚敏，吴伟民 .数据结构 .北京：清华大学出版社， 1997。
