常见无失真信源编码算法及Matlab实现比较

毕业论文基本要求

1．毕业论文的撰写应结合专业学习，选取具有创新价值和实践意义的论题。

2．论文篇幅一般为8000字以上，最多不超过15000字。 3．论文应观点明确，中心突出，论据充分，数据可靠，层次分明，逻辑清楚，文字流畅，结构严谨。

4．论文字体规范按《本科生毕业论文写作规范》和“论文样板”执行。

5．论文应书写工整，标点正确，用用微机打印后，装订成册。

本科毕业论文（设计）诚信声明

本人郑重声明：所呈交的本科毕业论文（设计），是本人在指导老师的指导下，独立进行研究工作所取得的成果，成果不存在知识产权争议，除文中已经注明引用的内容外，本论文不含任何其他个人或集体已经发表或撰写过的作品成果。对本文的研究做出重要贡献的个人和集体均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。

学生签名：

时间： 年 月 日

关于论文（设计）使用授权的说明

本人完全了解关于收集、保存、使用学位论文的规定，即： 1.按照学校要求提交学位论文的印刷本和电子版本；

2.学校有权保存学位论文的印刷本和电子版，并提供目录检索与阅览服务，在校园网上提供服务；

3.学校可以采用影印、缩印、数字化或其它复制手段保存论文； 本人同意上述规定。

学生签名：

时间：年月日

摘要

随着科学技术的发展，人类已经进入高速发展的信息时代。无论是在经济、政治、生活还是军事领域，信息的重要性已经不言而喻，有关信息的理论越来越受到重视。信息论与编码是信息、通讯、电子工程类专业的基础，对于理论研究和工程运用均有重要的指导作用。而无失真信源编码理论是信息论的理论基础，主要运用在离散信源或数字信号的研究，如文本、表格及工程图纸等信源，对其进行无失真地数据压缩，且完全能够无失真地可逆恢复。

本文首先在于讲述无失真信源编码的运用领域，研究无失真信源编码的意义。紧接着详细介绍了无失真信源编码中常见的三种编码方法及其Matlab实现过程，并将此三种方法进行对比。最后对此三种方法进行归纳总结，并举例说明其在日常生活中的运用。

在信息化、网络化、高科技化的特殊时代环境背景下，无失真信源编码的发展迎来了新的机遇与挑战，其应用领域越来越广，越来越普及，由此推进了编码方法的进一步深入研究。

[关键字]：Shanon编码；Fano编码；Huffman编码

I

Abstract

With the development of science and technology, people have entered into a rapidly developing information age. It goes without saying that information is very important nomatter in the fields of economy, politics, life or military.people pay more and more attention to the theories of information.Informationtheories and coding is not only the cornerstone of the major of information,communication and electronic engineering, but also play an vital role in guiding theoretical research and engineering application.

The undistorted source of coding theory is the theoretical foundation of the information theory. which is mainly applied to the studies of discrete source and digital information. For example, compressing information source including text, sheet and engineering drawing Can be compressed without any distortion, and then recover the other way round. we will present the application of the undistorted source of coding and study its significance in the beginning of this paper. And then introduce three methods of the undistorted source of coding as well as its MARLAB realization process. Besides, Acomparision of these three methods will be discussed. In the end of the paper, make a generalization of these methods and illustrate their applications in our daily life.

In this era of informationzation, networking and high-technicalization, the development of the undistorted source of coding is facing new opportunities and challenges.Its application areas arebecoming more widely and in the meanwhile it is becoming more popular, which has boosted the further study of encoding methods.

[KeyWords]: Shannon Coding;FanoCoding;Huffman Coding

II

本科毕业论文——常见无失真信源编码算法与Matlab实现比较

目 录

摘 要????????????????????????I Abstract??????????????????????II

1.绪论??????????????????????????1 1.1无失真信源编码技术发展历程??????????????1 1.2无失真信源编码技术的应用领域?????????????2 2.常见无失真信源编码及其MATLAB实现比较?????????3 2.1编码的定义??????????????????????3 2.2 MATLAB简介??????????????????????3 2.3常用编码方法?????????????????????4 2.3.1香农编码方法????????????????????4 2.3.2费诺编码方法????????????????????7 2.3.3 哈夫曼编码方法??????????????????9 3.无失真信源编码技术的未来发展趋势???????????11 3.1 我国的HDTV研究???????????????????11 3.2会议电视???????????????????????12 3.3可视电话???????????????????????13 4.总结?????????????????????????14

参考文献??????????????????????15 致 谢???????????????????????16 附 录???????????????????????17

1

本科毕业论文——常见无失真信源编码算法与Matlab实现比较

图2.1香农编码的matlab实现过程

图2.2香农编码的matlab实现过程

7

本科毕业论文——常见无失真信源编码算法与Matlab实现比较

从上面的运行结果可以知道，香农编码的平均码长是2.64，编码效率是0.814，其编码符号概率大的信源符号用短码表示，概率小的是用长码表示，当概率越大时，包含的信息量越少，当概率越小时，包含的不确定性越大，即信息量越多，要无失真的表示信源符号所需要的二进制数位数就越多。将以上运行结果编制成表格2.1：

表2.1香农编码过程

信源消息符号xi x1 x2 x3 x4 x5 x6 符号概p(xi) 0.40 0.30 0.10 0.09 0.07 0.04 累加概Xi 0 0.40 0.70 0.80 0.89 0.96 码长Ki 2 2 4 4 4 5 码字 00 01 1011 1100 1110 11110 2.3.2费诺编码方法

费诺编码的基本原理是将信源符号以概率递减的次序排列进来，将排列好的信源符号划分为两大组，使第组的概率和近于相同,并各赋于一个二元码符号“0”和“1”。然后，将每一大组的信源符号再分成两组，使同一组的两个小组的概率和近于相同，并又分别赋予一个二元码符号。依次下去，直至每一个小组只剩下一个信源符号为止。这样，信源符号所对应的码符号序列则为编得的码字。译码原理，按照编码的二叉树从树根开始，按译码序列进行逐个的向其叶子结点走，直到找到相应的信源符号为止。之后再把指示标记回调到树根，按照同样的方式进行下一序列的译码到序列结束。如果整个译码序列能够完整的译出则返回成功，否则则返回译码失败。费诺编码属于概率匹配编码，但他不是最佳的编码方法，其编码过程有如下几个步骤：

（1）同样，假定一组信源X，其出现的概率分别为

P(x1)=0.40,P(x2)=0.30,P(x3)=0.10，P(x4)=0.09,P(x5)=0.07,P(x6)=0.04,即是信源A=[0.40,0.30,0.10,0.09,0.07,0.04]，利用函数fliplr(sort(A))将信源消息符号按其出现的概率大小依次按照降序排列，即：

p(x1) ≥p(x2) ≥?≥p(xn) (2.5)

8

本科毕业论文——常见无失真信源编码算法与Matlab实现比较

（2）将依次排列的信源符号按概率值分为两大组，使两个组的概率之和近于相同，并对各组赋予一个二进制码元“0”和“1”，得到矩阵B，则B中每一列表示一组信源。

（3）将矩阵B每一大组的信源符号进一步再分成两组，使划分的两组的概率之和近于相同，并赋予两个组一个二进制符号“0”和“1”。

（4）如此重复，直至每个组只剩下一个信源符号为止。 （5）信源符号所对应的码字END即为费诺码。 该费诺码的平均码长:

7K??p(xi)Ki?2.74码元/符号 i?1(2.6)

信息传输速率:

R?H(X)2.61?=0.953比特/码元 (2.7) 2.74K

图2.3 费诺编码的matlab实现过程

9

本科毕业论文——常见无失真信源编码算法与Matlab实现比较

从上面的运行结果可以知道，费诺编码的平均码长是2.2，比香农编码的码长要小，消息传输速率较大，编码效率较高。将以上运行结果编制成表格2.2：

表2.2 费诺编码过程 消息符号xi x1 x2 x3 x4 x5 x6 各个消息概率p(xi) 0.40 0.30 0.10 0.09 0.07 0.04 1 第一次分组 第二次分组 0 1 第三次分组 0 1 第四次分组 0 1 0 1 码字 码长Ki 0 10 1100 1101 1110 1111 1 2 4 4 4 4 2.3.3哈夫曼编码方法

哈夫曼编码(Huffman Coding)是一种编码方式，哈夫曼编码是可变字长编码(VLC)的一种。Huffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长 度最短的码字，有时称之为最佳编码，一般就叫作Huffman编码。

以哈夫曼树─即最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。 在计算机信息处理中，“哈夫曼编码”是一种一致性编码法（又称“熵编码法”），用于数据的无损耗压缩。这一术语是指使用一张特殊的编码表将源字符（例如某文件中的一个符号）进行编码。这张编码表的特殊之处在于，它是根据每一个源字符出现的估算概率而建立起来的（出现概率高的字符使用较短的编码，反之出现概率低的则使用较长的编码，这便使编码之后的字符串的平均期望长度降低，从而达到无损压缩数据的目的）。这种方法是由David.A.Huffman发展起来的。 例如，在英文中，e的出现概率很高，而z的出现概率则最低。当利用哈夫曼编码对一篇英文进行压缩时，e极有可能用一个位(bit)来表示，而z则可能花去25个位（不是26）。用普通的表示方法时，每个英文字母均占用一个字节（byte），即8个位。二者相比，e使用了一般编码的1/8的长度，z则使用了3倍多。倘若我们能实现对于英文中各个字母出现概率的较准确的估算，就可以大幅度提高无损压缩的比例。

（1）假定一组信源X，其出现的概率分别为

P(x1)=0.40,P(x2)=0.30,P(x3)=0.10，P(x4)=0.09,P(x5)=0.07,P(x6)=0.04,即

10

本科毕业论文——常见无失真信源编码算法与Matlab实现比较

是A=[0.40,0.30,0.10,0.09,0.07,0.04]，利用函数A=fliplr(sort(A))将信源消息符号按其出现的概率大小依次按照降序排列，即：

P(x1) ≥p(x2) ≥?≥p(xn) (2.8)

（2）将出现概率最小的两个符号概率相加合成一个新概率。

（3）将合成概率看成一个新组合符号概率，将新组合符号和其余符号一起重新按概率大小排序，再将最小概率的两个符号组成一个新的组合符号概率，计算出其出现概率。重复上述做法，直到最后只剩下两个符号概率，且这两个概率相加等于1为止。

（4）将上面得到的各符号用线连接起来，得到一个前缀码的码树。树的端点对应N个信源。每个节点的两个分支用二进制码的两个码元符号“0”、“1”分别表示。从根节点开始沿着相反的路径，经过一个或者几个节点到达端点，将一路上遇到的二进制码元各符号顺序连接起来，这就是这个端点对应的信源符号的Huffman码的码字。

图2.4 哈夫曼编码的matlab实现过程

11

本科毕业论文——常见无失真信源编码算法与Matlab实现比较

从上面的运行结果可以知道，哈夫曼编码的平均码长是2.2，编码效率是0.9768，由此可见, 哈夫曼码的平均码长最小，消息传输速率最大,编码效率最高。

表 2.3哈夫曼编码过程

信源符号xi x1 x2 x3 x4 x5 x6 概率p(xi) 0.40 0.30 0.10 0.09 0.07 0.04 编码过程 码字Wi 10 11 000 001 010 0110 码字Ki 2 2 3 3 3 4

0.40 0.40 0.40 0.40 0.60 0 1.0 0.30 0.30 0.30 0.30 0.40 1 0.10 0.11 0.19 0.30 0.09 0.10 0.11 0.07 0.09 0.04 但哈夫曼编码方法得到的码并非是唯一的。因为每次对信源缩减时，赋予信源最后两个概率小的符号，用0和1是可以任意的，所以可以得到不同的哈夫曼码，但不会影响码字的长度。对信源进行缩减时, 两个概率小的符号合并后的概率与其他信源符号的概率相同时，这两者在缩减信源中进行概率排序，其位置放置次序是可以任意的，故会得到不同的哈夫曼码。此时将影响码字的长度，一般将合并的概率放在上面，这样可以获得较小的码方差。

3.无失真信源编码技术的未来发展趋势

随着信息技术的发展，现代社会对静止图象和视频序列图象的压缩编码技术应用越来越广泛，从娱乐性的通信设备到专业的通信设备，从廉价的简单的电子产品到昂贵的复杂的专业设备，应用的例子不胜枚举，如VCD、DVD、可视电话、视频会议、IP的视频服务、数字图书馆、高清晰电视、数码照相机、数字图象监控、网络摄象机、电视演播室设备等，都运用到了无失真信源编码技术。正因为如此，在这方面的专业人才一直都可以受到重用。

3.1 我国的HDTV研究

目前，编码技术在我国的数字高清晰度电视上的应用还处在实验和技术探索阶段，尚未制定有关HDTV（High Definition Television，即高清晰度电视）的国家标准，但从当前HDTV的发展趋势和我国已经进行的样机研究情况看来，我

12

本科毕业论文——常见无失真信源编码算法与Matlab实现比较

们的HDTV也将的全数字的，其视频编码方法也将是符合或基于MPEG-2的。MPEG是活动图像专家组(Moving Picture Experts Group)的缩写，于1988年成立，目前MPEG已颁布了三个活动图像及声音编码的正式国际标准，分别称为MPEG-1、MPEG-2和MPEG-4，而MPEG-7和MPEG-21都在研究中。我国研制的数字高清晰度电视，采用的图象输入格式为1920×1080，50帧/s或60帧/s可选，扫描方式为2：1隔行，码流符合MPEG-2MP@HL（MPEG-2MP@HL：一个视频编码标准，目前具有非常广阔的前景），总体方案是以IBMS422芯片为核心，将图象在水平方向分成六条，并行编码实现。视频解码器采用国外HDTV解码专用芯片组实现，集成度较高。有ST和LG两种方案：ST方案采用SGS-THOMSON的ST-TP3、STi7000、STi4600芯片组，LG方案采用LG Semicon的GDC21D301、GDC21D401、GDC21D701芯片组。ST方案的特点是：ST20软件结构合理，含控制和解复用功能，STi7000集成度高，硬件结构成熟。LG方案的特点是：芯片组各部分功能划分明确，简单，但外挂8位CPU，适应性、灵活性较差。

3.2会议电视

会议电视是指人与人之间可以以电视的形式在远程召开实时的、可以互相交流的可视会议，属于一种多媒体技术。之所以称为电视会议，是因为在这种通信方式中，参与通信的双方或多方，可以不受实际地理位置限制，实现面对面的交流，不仅能够听到对方的声音，看到对方是相貌、表情和动作等，还能够面对同一图纸，图片和文本等对象进行讨论，甚至合作设计，创作等。由于通信的参与者不需要实际集合到一起，这就节省了大量的时间、出差费用和精力，从而极大地提高工作效率。

早在70年代，会议电视的雏形已经出现，就是但是的模拟会议，不过当时的模拟会议仅限于两个地点之间，而现在的会议电视已经实现多个地点可以共同进行。由于会议电视的费用比较高，且要占用很宽的频带，所以没有得到很好的发展。直到80年代，随着数字图像压缩技术的发展，数字会议电视开始出现。相比会议电视，数字会议电视具有图像质量好、占用频带短等优势，于是会议电视就理所当然的被数字会议电视取代了。数字会议电视的发展较快，部分地区还

13

本科毕业论文——常见无失真信源编码算法与Matlab实现比较

形成了会议电视网，但是由于世界各地不同国家之间使用的标准不一样，国际会议电视的实现较有难度。

直到1992年，国际电报电话咨询委员会根据各国在会议电视方面的研究成果，定制了国际会议电视的统一标准，即是H.200系列建议。H.200系列建议里面规定了误码校正的标准、视频输入输出标准、编码压缩算法的标准以及其他一系列网上通信模式交换标准等。利用会议电视可以召开各种类型会议，包括远程工作会议、培训会议。在商务谈判、信息交流等方面也有广泛的运用。由于利用会议电视召开各类会议不受时间和空间限制，可以节省大量的人力、财力和物力，所以会议电视在我们日常工作中有着非常普遍的运用，很多中型、大型的全国性企业都运用电视会议来召开远程工作会议和业务知识培训。

会议电视不仅可以节省大量的人力、财力和物力，并且还在现场指挥调度、紧急救援、办公自动化等许多方面发挥作用，有着较好的发展前景。

3.3可视电话

可视电话是指在通话过程中，利用电话线路实时传送通话人的语音和图像的一种通信方式。随着现代通信技术的发展和移动通信在全国范围内的普及，移动多媒体通信已经成为一种强烈的市场需求。可视电话就是移动多媒体的发展重心，这种多媒体业务实现了视频、音频和数据等多种媒体信息的综合处理，使得身处异地的两个人可以通过移动电话进行实时通信，通话双方不仅可以听到彼此的讲话，还可以看到对方，其发展收到人们的普遍关注。

可视电话在传输信道上的分类可以分为PSTN型、ISDN型和专网型等方式，PSTN每秒钟可以传输10—15帧画面，ISDN每秒钟可以传输15帧以上的画面。目前主要的电话产品类型主要有两种，其中一种就是我们平时在QQ中进行的视频聊天，它是以电脑为核心，再加上麦克风、摄像头以及扬声器等设备在内的可视电话；另一种是存在于家庭固定电话的可视电话，它的使用跟普通的家庭座机是一样的。现在的可视电话主要有三种标准，其一是H.320国际标准，其二是H.261视频编码标准，其三是H.263视频编码标准。

由于时代的需要和社会的不断发展，无失真信源编码技术的运用越来越广泛，其发展将会会直接影响到多媒体运营系统、宽带网络技术和多媒体系统通讯协议等方面的发展。自从人类进入了信息时代，信息压缩的需求越来越大，特别

14

本科毕业论文——常见无失真信源编码算法与Matlab实现比较

是视频数据，这为无失真信源编码技术的发展提出了新的要求和新的挑战。在未来的社会，无失真信源编码技术将会有更加广泛的运用，其发展空间还很大，发展前景也很广阔，其不断发展将会给我们的生活带来新的改变，我们也期待着其带来的更多便利。

4．总结

本文首先简单阐述了何为无失真信源编码技术，其次叙述了编码的定义方法，并对运行支持软件MATLAB做了简要的介绍，然后对无失真信源编码中常用的三种编码方法进行介绍，并通过MATLAB实现了其编码过程，主要研究了香农编码、费诺编码和哈夫曼编码这三种不同编码方法在实现编码过程中的异同，最后简要介绍了无失真信源编码在未来的发展趋势，并列举了其在日常生活中的应用。通过对比香农编码、费诺编码和哈夫曼编码的MATLAB运行过程，费诺编码的编码效率比香农编码高，而哈夫曼编码的编码效率比费诺编码高，由此得出结论是哈夫曼编码的平均码长最小，消息传输效率最大，编码效率最高。

15

本科毕业论文——常见无失真信源编码算法与Matlab实现比较

参考文献

[1] 曹雪虹，张宗橙.信息论与编码，清华大学出版社，2009 [2] 李亦农.信息论理论基础，北京邮电大学出版社,2005 [3] 谭浩强.C语言程序设计教程，高等教育出版社,2002

[4] 毛文娟.算术编码在图像压缩系统中的应用，信息技术,2005(10) [5] 曹雪虹.信息论与编码，北京邮电大学出版社,2003

[6] 谷学涛.基于DSP的音频解码系统的设计与算法研究武汉理工大学硕士学位论文,2006 [7]滕少华.Huffman算法及其应用，计算机与现代化,1994 [8]徐长梅.Huffman编码的一种实现方法,1997

[9]A.R.Calderbank,IngridDaubichies,WimSweldens.Wavelettransforms that map intergers to intergers.1996

[l0] 韩俊英. Huffman算法的分析与改进.兰州铁道学院学报,2003 [11] 曹志刚，钱亚生.现代通信原理.清华大学出版社，2009.9 [12] 余兆明，余智．数字电视原理．西安电子科技大学出版社，2009.2

[13] 张威. MATLAB基础与编程入门（第二版）.西安电子科技大学出版社，2008.1 芦亚亚.由行程编码改进的一种通用性压缩方法，浙江大学学报,2007 [14] 李龙.数字图像无损压缩，软件道刊,2007

[15] 杨述斌，李永全.数字信号处理实践教程.华中科技大学出版社，2007.1 王梓展.一种新型的无损视频压缩算法,2006

[16]D.A.Huffman.A method for construction of minimum redun- dancycodes,ProcIRE,1951. [17]F.Ghido.A efficient Algorithm for Lossless Compression of IEEE FloatAudio[C].In:DCC. 2004

[18] 吴国清等.一种科学数据无损压缩方法，计算机工程与应用,2006

[19]Aaron Trott,RobertMoorhead.Wavelets applied to lossless compression and progressive transmission of floating point data in 3D curvilinear gride[J].IEEE,1996

[20]P.Pancha and M.Zarki,”MPEG coding for variable bitrate video transmission,” IEEE Comm.Magazine ,pp.54-66,MAY 1994

[21] 芮国胜.一种实用的算术编码方案，高技术通讯,2000 [22] 程佩青，数字信号处理教程. 清华大学出版社，2010.5

16

本科毕业论文——常见无失真信源编码算法与Matlab实现比较

致 谢

在本文完成之际，谨向我的导师刘美春教授致以衷心的感谢，本论文是在他的精心指导和关怀下完成的，从论文的选题、方案设计，到论文的撰写和修改，都倾注了他的心血和汗水，在学习期间，他的言传身教将使我终生受益，他认真严谨的治学态度、豁达宽广的胸怀、平易近人的处事风格是我一生的楷模，值此提交论文之时，在此向刘美春导师表达衷心的感谢！

17

本科毕业论文——常见无失真信源编码算法与Matlab实现比较

附录

1.香农编码源程序

%求解给定信源符号概率的香农编码 clc; clear all;

X=[0.40,0.30,0.10,0.09,0.07,0.04] X=fliplr(sort(X));%降序排列 [m,n]=size(X); %计算累加概率 X1(1,n)=0; for j=1:n-1

X1(j+1)=X(j)+X1(j); end X1

%计算码长,取整 for k=1:n

L(k)=ceil(-log2(X(k))); end L

%将累加概率变换成二进制数 l=max(L); r=zeros(n,l); for i2=1:n for i3=1:n

r(i2,i3)=floor(X1(i2)*2); X1(i2)=X1(i2)*2-floor(X1(i2)*2); end end r

%取小数点后li位二进制码作为代码组 bin=zeros(n,l); for i4=1:6 for i5=1:6 if i5>L(i4)

18

本科毕业论文——常见无失真信源编码算法与Matlab实现比较

bin(i4,i5)=blanks(1);%创建空白串 else

if r(i4,i5)==0 bin(i4,i5)='0'; else

bin(i4,i5)='1'; end end end end

shangnon=char(bin) %计算平均码长 for l=1:6 L=sum(L.*X); end L

%计算编码效率 HX=sum(-X.*log2(X)); xiaolv=HX/L

2.费诺编码源程序

clc; clear;

A=[0.4,0.3,0.1,0.09,0.07,0.04]; A=fliplr(sort(A));%降序排列 [m,n]=size(A); for i=1:n

B(i,1)=A(i);%生成B的第1列 end

%生成B第2列的元素 a=sum(B(:,1))/2; for k=1:n-1

if abs(sum(B(1:k,1))-a)<=abs(sum(B(1:k+1,1))-a) break; end end

for i=1:n%生成B第2列的元素 if i<=k

B(i,2)=0;

19

本科毕业论文——常见无失真信源编码算法与Matlab实现比较

else

B(i,2)=1; end end

%生成第一次编码的结果 END=B(:,2)'; END=sym(END);

%生成第3列及以后几列的各元素 j=3;

while (j~=0) p=1;

while(p<=n) x=B(p,j-1); for q=p:n if x==-1 break; else

if B(q,j-1)==x y=1;

continue; else y=0; break; end end end if y==1 q=q+1; end

if q==p|q-p==1 B(p,j)=-1; else

if q-p==2 B(p,j)=0;

END(p)=[char(END(p)),'0']; B(q-1,j)=1;

END(q-1)=[char(END(q-1)),'1']; else

a=sum(B(p:q-1,1))/2; for k=p:q-2

if abs(sum(B(p:k,1))-a)<=abs(sum(B(p:k+1,1))-a); break; end end

20

本科毕业论文——常见无失真信源编码算法与Matlab实现比较

for i=p:q-1 if i<=k

B(i,j)=0;

END(i)=[char(END(i)),'0']; else

B(i,j)=1;

END(i)=[char(END(i)),'1']; end end end end p=q; end

C=B(:,j);

D=find(C==-1); [e,f]=size(D); if e==n j=0; else

j=j+1; end end B A END

for i=1:n

[u,v]=size(char(END(i))); L(i)=v; end

avlen=sum(L.*A)

3.哈夫曼编码源程序

p=input('请输入数据:') %提示输入界面[0.4,0.3,0.1,0.09,0.07,0.04] n=length(p); for i=1:n if p(i)<0

fprintf('\\n 提示：概率值不能小于0!\\n'); p=input('请重新输入数据:') end end

if abs(sum(p))>1

fprintf('\\n 哈弗曼码中概率总和不能大于1!\\n'); p=input('请重新输入数据:') end

21

本科毕业论文——常见无失真信源编码算法与Matlab实现比较

q=p;

a=zeros(n-1,n); %生成一个n-1 行n 列的数组 for i=1:n-1 [q,l]=sort(q)

a(i,:)=[l(1:n-i+1),zeros(1,i-1)] q=[q(1)+q(2),q(3:n),1]; end

for i=1:n-1

c(i,1:n*n)=blanks(n*n); end

c(n-1,n)='0'; c(n-1,2*n)='1'; for i=2:n-1

c(n-i,1:n-1)=c(n-i+1,n*(find(a(n-i+1,:)==1))-(n-2):n*(find(a(n-i+1,:)==1))) c(n-i,n)='0' %根据之前的规则，在分支的第一个元素最后补0 c(n-i,n+1:2*n-1)=c(n-i,1:n-1)

c(n-i,2*n)='1' %根据之前的规则，在分支的第一个元素最后补1 for j=1:i-1

c(n-i,(j+1)*n+1:(j+2)*n)=c(n-i+1,n*(find(a(n-i+1,:)==j+1)-1)+1:n*find(a(n-i+1,:)==j+1)) end

end %完成huffman 码字的分配 for i=1:n

h(i,1:n)=c(1,n*(find(a(1,:)==i)-1)+1:find(a(1,:)==i)*n)

ll(i)=length(find(abs(h(i,:))~=32)) %计算每一个huffman 编码的长度 end

l=sum(p.*ll); %计算平均码长 fprintf('\\n Huffman编码结果为:\\n'); h

fprintf('\\n 编码的平均码长为:\\n'); l

hh=sum(p.*(-log2(p))); %计算信源熵 fprintf('\\n 信源熵为:\\n'); hh

fprintf('\\n 编码效率为:\\n'); t=hh/l %计算编码效率

22

本科毕业论文——常见无失真信源编码算法与Matlab实现比较

q=p;

a=zeros(n-1,n); %生成一个n-1 行n 列的数组 for i=1:n-1 [q,l]=sort(q)

a(i,:)=[l(1:n-i+1),zeros(1,i-1)] q=[q(1)+q(2),q(3:n),1]; end

for i=1:n-1

c(i,1:n*n)=blanks(n*n); end

c(n-1,n)='0'; c(n-1,2*n)='1'; for i=2:n-1

c(n-i,1:n-1)=c(n-i+1,n*(find(a(n-i+1,:)==1))-(n-2):n*(find(a(n-i+1,:)==1))) c(n-i,n)='0' %根据之前的规则，在分支的第一个元素最后补0 c(n-i,n+1:2*n-1)=c(n-i,1:n-1)

c(n-i,2*n)='1' %根据之前的规则，在分支的第一个元素最后补1 for j=1:i-1

c(n-i,(j+1)*n+1:(j+2)*n)=c(n-i+1,n*(find(a(n-i+1,:)==j+1)-1)+1:n*find(a(n-i+1,:)==j+1)) end

end %完成huffman 码字的分配 for i=1:n

h(i,1:n)=c(1,n*(find(a(1,:)==i)-1)+1:find(a(1,:)==i)*n)

ll(i)=length(find(abs(h(i,:))~=32)) %计算每一个huffman 编码的长度 end

l=sum(p.*ll); %计算平均码长 fprintf('\\n Huffman编码结果为:\\n'); h

fprintf('\\n 编码的平均码长为:\\n'); l

hh=sum(p.*(-log2(p))); %计算信源熵 fprintf('\\n 信源熵为:\\n'); hh

fprintf('\\n 编码效率为:\\n'); t=hh/l %计算编码效率

22

本文来源：https://www.bwwdw.com/article/pg18.html