费诺编码的分析与实现.doc

吉林建筑大学电气与电子信息工程学院设计题目： 费诺编码的分析与实现 专业班级： 电子信息工程 111 学生姓名： 马 超 学 号： 10211115 指导教师： 吕卅 王超 设计时间： 2014.11.242014.12.5 教师评语：成绩 评阅教师 日期 第1章 概述1.1设计的作用、目的 信息论与编码是一门理论与实践密切结合的课程,通过理论课程学习如何计算信道容量，包括对信道的认识，以及传输速率的计算，计算最佳编码，编码效率等等。再通过课程设计加深对知识的认识，课程设计是其实践性教学环节之一，同时也是对课堂所学理论知识的巩固和补充。其主要目的是加深对理论知识的理解，掌握查阅有关资料的技能，提高实践技能，培养独立分析问题、解决问题及实际应用的能力。通过完成具体编码算法的程序设计和调试工作，提高对MATLAB等类似软件的认识程度，掌握MATLAB等类似软件的各种操作，提高编程能力，深刻理解信源编码、信道编译码的基本思想和目的，掌握编码的基本原理与编码过程，增强逻辑思维能力，培养和提高自学能力以及综合运用所学理论知识去分析解决实际问题的能力，逐步熟悉开展科学实践的程序和方法。1.2设计任务及要求 1. 理解无失真信源编码的理论基础，掌握无失真信源编码的基本方法； 2. 掌握费诺编码方法的基本步骤及优缺点； 3. 深刻理解信道编码的基本思想与目的，理解线性分组码的基本原理与编码 过程； 4. 能够使用MATLAB或其他语言进行编程，编写的函数要有通用性。1.3设计内容 一个有8个符号的信源X，各个符号出现的概率分别为： 运用MATLAB软件，编写适当的程序，对以上8个信源符号进行费诺编码， 得出二进制码字，计算平均码长、编码效率、冗余度，并总结费诺编码方法 的特点和应用。 第2章 费诺编码的分析与实现2.1设计原理1.编码原理 早期的数据压缩来自于人们对概率的了解。当对文字信息进行编码时，如果出现概率较高的字幕赋予较短的编码，为出现概率较低的字母赋予较长的编码，平均编码长度就能缩短不少。著名的Morse电码就是一个范例。信息论之父C.E.Shannon曾指出，任何信息都存在冗余，冗余大小与信息中每个符号出现概率（不确定性）有关。他所提出的无失真信源编码定理奠定了数据压缩的理论基础。数据压缩的目的就是要消除冗余，信息论是运用概率论与数理统计的方法研究信息、信源熵、通信系统、数据传输、密码学、数据压缩等问题的应用数学学科。从DVD到个人电脑，从卫星通信到文件，在我们今天的生活中，信息几乎在每个领域都扮演者重要角色。工程师克劳德香农于1948年奠定了信息论的基础，他指出了通信的极限。基于这一理论产生了数据压缩技术、纠错技术等各个应用技术，这些技术提高了数据传输和存储的效率。信息论将信息的传递作为一种统计现象来考虑，给出了估算通信信道容量的方法。信息传输和信息压缩是信息论研究中的两大领域。这两个方面又由信息传输定理、信源信道隔离定理相互联系。当然，信息论的重大应用远不止于此。DNA是一种信息存储物质，正事信息论帮助人们解开了生物基因组密码之谜。简单地说信息论包含了生命、宇宙乃至一切。信息论对现代社会的影响是多方面的。首先，在理论研究方面，信息论所处的地位已远远超出了香农当年所界定的“通信的数学理论”的范畴，得到了不断的扩充和发展，出现了语义信息、语法信息与语用信息等研究与信息的意义有关的学科，以及面向智能研究的全信息理论。如今，信息已成为与物质、能量并列的宇宙中的三个基本要素，世间万物的发展变化可归结为物质、能量和信息的传递和转化过程。另一方面，在科学和技术高度发展的今天，信息的概念也被渗透到许多不同的学科和领域，深入到了社会生活的各个方面，成为可与相对论和量子力学并驾齐驱的新一代边缘交叉学科的重要组成部分。特别是以信息论、控制论、和系统论为代表的“老三论”以及以普利高津的耗散结构理论，哈肯的协同学和托姆的突变论或艾根的超循环理论为代表的“新三论”的出现，标志着一代新的边缘交叉学科的兴起。它们的形成和发展对现代科学的研究具有重要的方法论上的指导意义。编码是信息从一种形式或格式转换为另一种形式的过程也称为计算机编程语言的代码简称编码。用预先规定的方法将文字、数字或其它对象编成数码，或将信息、数据转换成规定的电脉冲信号。编码在电子计算机、电视、遥控和通讯等方面广泛使用。在计算机硬件中，编码（coding）是指用代码来表示各组数据资料，使其成为可利用计算机进行处理和分析的信息。代码是用来表示事物的记号，它可以用数字、字母、特殊的符号或它们之间的组合来表示，将数据转换为代码或编码字符，并能译为原数据形式。是计算机书写指令的过程，程序设计中的一部分。在地图自动制图中，按一定规则用数字与字母表示地图内容的过程，通过编码，使计算机能识别地图的各地理要素。编码分为信源编码和信道编码，其中信源编码又分为无失真和限失真。由于这些定力都要求符号数很大，以便其值接近所规定的值，因而这些定力被称为极限定理。一般称无失真信源编码定力为第一极限定理；信道编码（包括离散和连续信道）称为第二极限定理；限失真信源编码定力称为第三极限定理。2.信源编码原理 由于信源符号之间存在分布不均匀和相关性，是的信源存在冗余度，信源编码的主要任务就是减少冗余，提高编码效率。具体说，就是针对仙缘输出符号序列的统计特性，寻找一定的方法把信源输出符号序列变换为最短码字序列的方法。信源编码的基本途径有两个：使序列中的各个符号尽可能的相互独立，及解除相关性；使编码中各个符号出现的概率尽可能地相等，即概率均匀化。信源编码的基础是信息论中的两个编码定理：无失真编码定理和限失真编码定理，前者是可逆编码的基础。可逆是指当信源符号转换成代码后，可从代码无失真的恢复原信源符号。当已知信源符号的概率特性时，可计算它的 符号熵，这边是每个信源符号所载有的信息量。编码定理不但证明了必定存在一种编码方法，可使代码的平均长度可任意接近但不低于符号熵，而且还阐明达到这木匾的途径，就是使概率与码长匹配。无失真编码或可逆编码只适用与离散信源。对于连续信源，编成代码后就无法无失真地恢复原来的连续值，因为后者的取值可有无限多个。此时只能根据率失真编码定理在失真受限制的情况下进行限失真编码。信源编码定理出现后，编码定理趋于合理化。关于离散信源编码，从无失真编码定理出发。若要所编的码是惟一可译码，不但要求编码时不同的信源符号变换成不同的码字，而且必须要求任意有限长的信源序列所对应的码符号序列各不相同，即要求码的任意有限长N次扩展码都是非奇异码。因为只有任意有限长的信源序列所对应的码符号序列各不相同，才能把该码符号序列惟一地分割成一个个对应的信源符号，从而实现惟一的译码。 3.费诺编码原理费诺编码就是通过使编码中各个句号出现的概率大致相等，实现概率均匀化，从而减少冗余度，提高编码效率。凡是能载荷一定的信息量，且码字的平均长度最短，可分离的变长码的码字集合称为最佳变长码。在编N进制码时首先将信源消息符号按其出现的额概率一次又小到大排列开来，并将排列好的心愿符号按概率值分N大组，使N组的概率之和近似相同，并对各组赋予一个N进制码元0、1.N-1。之后再针对每一个大组内的心愿符号做如上处理，即再分为概率相同的N组，赋予N进制码元。如此重复，直到每组只剩下一个心愿符号为止。此时每个信源符号所对应的码字即为费诺码。针对同一个心愿，费诺码比香农码平均码长小，消息出书速率大，编码效率高。费诺编码是一种信源编码，它编码后的费诺码要比香农码的平均码长小，消息传输速率大，编码效率高。但它属于概率匹配编码它不是最佳的编码方法。4.费诺编码特点 费诺编码是一种信源编码，它编码后的费诺码要比香农码的平均码长小，消息传输速率大，编码效率高。但它属于概率匹配编码它不是最佳的编码方法。 费诺编码属于概率匹配编码，具有如下特点： （1）概率大，则分解次数少；概率小则分解次数多，这符合最佳编码原则。 （2）码字集合是唯一的。 （3）分解之后先得码字后得码长。2.2设计步骤1.费诺码编码步骤 （1）将信源消息符号按其出现的概率大小依次排列：p1p2pn 。 （2）将依次排列的信源符号按概率值分为两大组，使两个组的概率之和近似 相同，并对各组赋予一个二进制码元“0”和“1”。 （3）将每一大组的信源符号再分成两组，使划分后的两个组的概率之和近似 相同，并对各组赋予一个二进制符号“0”和“1”。 （4）如此重复，直至每个组只剩下一个信源符号为止。 （5）信源符号所对应的码子即为费诺码。 2.费诺码编码过程如表1所示。 表1 费诺码编码过程消息符号各个消息概率p(xi)第一次分组第二次分组第三次分组第四次分组第五次分组二元码字码长x10.2500002x20.21012x30.21001003x40.111013x50.1101103x60.081011104x70.0510111105x80.0211111153.计算平均码长、信源熵、编码效率及冗余度。 平均码长： 2.77 码元/符号信源熵： 2.71 bit/符号编码效率： 0.98冗余度： 1-0.980.02第3章 费诺编码的MATLAB实现3.1 MATLAB MATLAB是美国MathWorks公司出品的商业数学软件，用于算法开发、数据可视化、数据分析以及数值计算的高级技术计算语言和交互式环境，主要包括MATLAB和Simulink两大部分。 MATLAB是matrix&laboratory两个词的组合，意为矩阵工厂（矩阵实验室）。是由美国mathworks公司发布的主要面对科学计算、可视化以及交互式程序设计的高科技计算环境。它将数值分析、矩阵计算、科学数据可视化以及非线性动态系统的建模和仿真等诸多强大功能集成在一个易于使用的视窗环境中，为科学研究、工程设计以及必须进行有效数值计算的众多科学领域提供了一种全面的解决方案，并在很大程度上摆脱了传统非交互式程序设计语言（如C、Fortran）的编辑模式，代表了当今国际科学计算软件的先进水平。 MATLAB和Mathematica、Maple并称为三大数学软件。它在数学类科技应用软件中在数值计算方面首屈一指。MATLAB可以进行矩阵运算、绘制函数和数据、实现算法、创建用户界面、连接其他编程语言的程序等，主要应用于工程计算、控制设计、信号处理与通讯、图像处理、信号检测、金融建模设计与分析等领域。MATLAB的基本数据单位是矩阵，它的指令表达式与数学、工程中常用的形式十分相似，故用MATLAB来解算问题要比用C，FORTRAN等语言完成相同的事情简捷得多，并且MATLAB也吸收了像Maple等软件的优点，使MATLAB成为一个强大的数学软件。在新的版本中也加入了对C，FORTRAN，C+，JAVA的支持。 MATLAB是一个高级的矩阵/阵列语言，它包含控制语句、函数、数据结构、输入和输出和面向对象编程特点。用户可以在命令窗口中将输入语句与执行命令同步，也可以先编写好一个较大的复杂的应用程序（M文件）后再一起运行。新版本的MATLAB语言是基于最为流行的C+语言基础上的，因此语法特征与C+语言极为相似，而且更加简单，更加符合科技人员对数学表达式的书写格式。使之更利于非计算机专业的科技人员使用。而且这种语言可移植性好、可拓展性极强，这也是MATLAB能够深入到科学研究及工程计算各个领域的重要原因。优势特点：高效的数值计算及符号计算功能，使用户从繁杂的数学运算分析中解脱；具有完备的图形处理功能，实现计算结果和编程的可视化；友好的用户界面及接近数学表达式的自然化语言，使学者易于学习和掌握；功能丰富的应用工具箱，为用户提供了大量方便实用的处理工具。 MATLAB是美一款商业数学软件，用于算法开发、数据可视化、数据分析以及数值计算的高级技术计算语言和交互式环境，主要包括MATLAB和Simulink两大部分。它将数值分析、矩阵计算、科学数据可视化以及非线性动态系统的建模和仿真等诸多强大功能集成在一个易于使用的视窗环境中，代表了当今国际科学计算软件的先进水平。MATLAB和Mathematica、Maple并称为三大数学软件。它在数学类科技应用软件中在数值计算方面首屈一指。MATLAB可以进行矩阵运算、绘制函数和数据、实现算法、创建用户界面、连MATLAB开发工作界面接其他编程语言的程序等，主要应用于工程计算、控制设计、信号处理与通讯、图像处理、信号检测、金融建模设计与分析等领域。MATLAB具有用法简单、灵活、程式结构性强、延展性好等优点，已经逐渐成为科技计算、视图交互系统和程序中的首选语言工具。特别是它在线性代数、数理统计、自动控制、数字信号处理、动态系统仿真等方面表现突出，已经成为科研工作人员和工程技术人员进行科学研究和生产实践的有利武器。MATLAB具有以下六个特点：（1）编程效率高 用MATLAB编写程序犹如在演算纸上排列出公式与求解问题，MATLAB语言也可通俗地称为演算纸式的科学算法语言。由于它编写简单，所以编程效率高，易学易懂。（2）用户使用方便 MATLAB语言把编辑、编译、连接和执行融为一体，其调试程序手段丰富，调试速度快，需要学习时间少。它能在同一画面上进行灵活操作快速排除输入程序中的书写错误、语法错误以至语意错误，从而加快了用户编写、修改和调试程序的速度，可以说在编程和调试过程中它是一种比VB还要简单的语言。（3）扩充能力强 高版本的MATLAB语言有丰富的库函数，在进行复杂的数学运算时可以直接调用，而且MATLAB的库函数同用户文件在形成上一样，所以用户文件也可作为MATLAB的库函数来调用。因而，用户可以根据自己的需要方便地建立和扩充新的库函数，以便提高MATLAB使用效率和扩充它的功能。（4）语句简单，内涵丰富 MATLAB语言中最基本最重要的成分是函数，其一般形式为(a，6，c)=fun（d，e，f，），即一个函数由函数名，输入变量d，e，f，和输出变量a，b，c.组成，同一函数名F，不同数目的输入变量（包括无输入变量）及不同数目的输出变量，代表着不同的含义。这不仅使MATLAB的库函数功能更丰富，而大大减少了需要的磁盘空间，使MATLAB编写的M文件简单、短小而高效。（5）高效方便的矩阵和数组运算 MATLAB语言像Basic、Fortran和C语言一样规定了矩阵的一系列运算符，它不需定义数组的维数，并给出矩阵函数、特殊矩阵专门的库函数，使之在求解诸如信号处理、建模、系统识别、控制、优化等领域的问题时，显得大为简捷、高效、方便，这是其它高级语言所不能比拟的。（6）方便的绘图功能 MATLAB受到控制界广泛接受的一个重要原因是因为它提供了方便的绘图功能。MATLAB的绘图是十分方便的，它有一系列绘图函数（命令），使用时只需调用不同的绘图函数（命令），在图上标出图题、XY轴标注，格绘制也只需调用相应的命令，简单易行。另外，在调用绘图函数时调整自变量可绘出不变颜色的点、线、复线或多重线。例图如图1所示。图1 matlab画图实例3.2 MATLAB编程1.M文件的建立用MATLAB语言编写的程序，称为M文件。M文件可以根据调用方式的不同分为两类：命令文件（Script File）和函数文件（Function File）。MATLAB编程时首先建立两个M文件，M文件存放于MATLAB默认文件夹中，供主函数调用，特别注意的是，M文件必须存放在软件默认文件夹，否则主程序会无法调用，而导致程序运行不成功。M文件f1、f2的建立界面分别如图2、3所示。图2 f1.m文件图3 f2.m文件2.主程序建立M函数文件是一个特殊的M文件，其常见格式如下：funcdon返问变量列表包括函数名(输入变量列表)注释说明语句段函数体语。需要说明的是，这里输入变量的个数以及输出变量的个数是由MATLAB本身提供的两个保留变量nargin和nargout来给出的，它们分别是Numberoffunctioninputarguments和Numberoffunctionoutputarguments的缩写形式。输入变量要用逗号隔开，输出变量多于1个时，要用方括号括起来。用户可以借助于help命令显示其中的注释说明语句段。通过这样的方法就可以建立函数文件或者称M函数，其调用方法与一放的MATLAB函数的调用方法相同。函数文件相当于对MATLAB进行了二次开发。其作用与其他高级语言子函数的作用基本相同，都是为了实现特定目的而由用户自己编写的子函数。需要说明的是，调用函数时所用的输入输出变量名并不要求与编写函数文件时所用的输入输出变量名相同。打开Command Window并在其中输入主程序，主程序输入过程如图4所示。图4 程序输入界面3.3 运行结果及分析1.程序运行界面如图5、图6所示。图5 程序运行界面图6 符号个数输入界面2.符号概率的输入 需要说明的是，输入8个符号概率的时候要按从大到小的顺序输入，否则程序无法运行，符号概率输入界面如图7所示。图7 符号概率输入界面3.程序计算所得的码字如图8所示。 图8 程序计算所得的码字4.程序计算的平均码长、信源熵、编码效率及冗余度如图9所示。 图9 程序计算结果第4章 总结通过这次课程设计，我更深入的了解了费诺编码的构造原理。费诺编码的重点在于分组，然后在分组的基础上编码，由编码的原理可以看出，费诺编码应该用递归的办法，递归是比较难的知识点，但是是比较实用的知识。费诺编码首先是把消息符号按概率从大到小的顺序进行排序，然后再按照每组概率和近似相等的办法分成两组，然后依次给组分配码字，然后继续对各个组进行分组，直到不能再分为止。费诺编码方法得到的码子不唯一，费诺码比较适合于对分组概率相等或相近的信源编码，费诺码也可以编M进制码，但M越大，信源的符号数越多，可能的编码方式就越多，编码过程就越复杂，有时短码未必能得到充分利用。一般情况下，当信源符号个数越多，编码效率就越低，信源符号相等或越接近，编码效率也就越高。费诺码对信源的统计特性没有特殊要求，编码效率比较高，对编码设备的要求也比较简单，因此综合性能优于香农码和哈弗曼码。费诺编码在具体实用时，设备较复杂。在编码器中需要增加缓冲寄存器，因为每个信源符号所对应的码符号长度不一，负责会造成输入和输出不能保持平衡。 通过本次课程设计，我进一步的对费诺编码有了一个深刻的认识，对于信息论的认识也进入了一个新的台阶。课程设计过程中，通过编程，我的程序编写能力有了一定的提高，尤其使我对字符串、排序、递归算法等有了更深的了解。同时，编程的过程中也使我认识到了许多自己编程中的不足，对函数的参数传递、数组指针、指针的传递等没有很好的掌握。在学习如何将理论知识传换成实际应用的同时。我也对调试技巧有了更好的掌握，分析问题的能力也有很大提高。本次课程设计进一步使用了MATLAB这个软件工具，也让我更加熟悉了在MATLAB中的编程的语法和结构。认识到了软件工具在通信科研仿真方面的重要作用和方便性。在设计的过程中，我也体会到学习任何知识，仅从理论上去求知，而不去实践、探索是不够的。经过本次实验，充分学习了费诺编码理论及其重点内容，掌握了费诺编码原理的同时也锻炼了编程水平，为以后的学习中出现的可能问题做好了准备，锻炼了自己的动手能力和设计能力，掌握了一种科技工具，丰富了自己的学习生活。通过课程设计我们可以学习到在书本上学不到的知识，可以了解在课堂上理解不了的概念，课程设计是一个学者从理论走向实践必不可少的过程，所以我觉的各位老师应该多给我们这样的机会，让我们真正的可以从书本过渡到实践，让我们可以真正的成为一个可以为国家作出杰出贡献的栋梁之才。通过对信息论的学习，我们发现信息论其实是门理论性很强的学科，它涉及到众多学科。对于整个信息论的理论体系的认识也有了一个清晰的思路：首先介绍到的是信息的定义及其本质，再而学习到了各类信源的熵，信道及信道容量，主要研究的是离散信源和连续信源。最后是无失真信源编码，其中包含等长信源编码和变长信源编码；主要研究的变长信源编码。这就差不多构成信息论的整个基本理论结构。在此我也要感谢万老师的悉心教导，使 我更好的掌握了信息论的理论基础，为以后在通信领域以及其他方面的研究都奠定了坚实的基础。信息论发展到今天虽然已经做到比较全面，但仍旧存在一些不足，需要我们做更多的探讨，所以我会更加努力的学习，培养敢于创新，敢于挑战，为以后的生活和工作做好准备！在整个设计过程中我懂得了许多东西，在查找的过程中我们也知道了许多原来不知道的东西，对于源代码的修改以及成功利用也树立了对知识应用的信心，相信会对今后的学习工作和生活有非常大的帮助，并且提高了自己的动手实践操作能力，使自己充分体会到了在实验过程中的成功喜悦。在过程中所学到的东西是这次课程设计的最大收获和财富，使我终身受益。 这次课程设计的成功离不开老师们的指导和帮助，有不懂得问题向老师请教 的时候老师总是很细心认真的给我讲解，并介绍给我很多学习方法，给我介绍了很多学习资料，老师对我大力的支持，让我坚定了做好设计的决心和信心。在课程设计的过程中，老师对我们的严格要求，也让我感受到老师对知识的严谨态度，使我肃然起敬。在以后的日子里，我会学习老师们的精神和做事方法，努力提高自己，积累知识，不枉费老师们的悉心教导。附录 本次设计的完整程序%函数f1存放于f1.mfunction x=f1(i,j,p,r)global x;x=char(x);if(j=i)return;elseq=0;for t=i:j %对于区间i,j自上而下求累加概率值q=p(t)+q;y(t)=q; endfor t=i:j%把所有自上而下的累加概率值与该区间总概率值减该累加概率值之差取绝对值存在一数组v(t)=abs(y(t)-(q-y(t); endfor t=i:jif(v(t)=min(v) %求该数组中最小的一个值来确定分界点位置for k=i:t %赋值码字x(k,r)=0;endfor k=(t+1):jx(k,r)=1;endd=t;f1(i,d,p,r+1); %递归调用及相互调用f2(d+1,j,p,r+1);f1(d+1,j,p,r+1);f2(i,d,p,r+1);elseendend endreturn;%函数f2存放于f2.mfunction x=f2(i,j,p,r)global x;x=char(x);if(j=i)return;elseq=0;for t=i:j %对于区间i,j自上而下求累加概率值q=p(t)+q;y(t-i+1)=q; endfor t=1:j-(i-1)%把所有自上而下的累加概率值与该区间总概率值减该累加概率值之差取绝对值存在一数组v(t)=abs(y(t)-(q-y(t); endfor t=1:j-(i-1)if(v(t)=min(v) %求该数组中最小的一个值来确定分界点位置d=t+i-1;for k=i:d %赋值码字x(k,r)=0;endfor k=(d+1):jx(k,r)=1;end f2(d+1,j,