基于MATLAB的霍夫曼编码仿真

目录0前言............................................................................................错误!未定义书签。1信源编码的基本概念................................................................错误!未定义书签。1.1通信系统的模块仿真.........................................................错误!未定义书签。1.2信息的度量与编码.............................................................错误!未定义书签。1.3无失真编码算法.................................................................错误!未定义书签。2信源最佳化................................................................................................................63霍夫曼编码特点及应用............................................................错误!未定义书签。4编码规则....................................................................................................................74.1二元霍夫曼编码规则.........................................................................................74.2多元霍夫曼编码规则.........................................................................................84.3扩展信源霍夫曼编码.........................................................................................85MATLAB性能仿真...................................................................................................85.1二元霍夫曼编码仿真.........................................................................................95.2三元霍夫曼编码仿真.......................................................................................115.3扩展信源编码仿真...........................................................................................136结论............................................................................................错误!未定义书签。参考文献........................................................................................错误!未定义书签。河南大学民生学院本科毕业论文1基于MATLAB的霍夫曼编码仿真李长江（河南大学物民生学院，河南开封，475004）摘要：通信的数字化是它能与计算机技术和数字信号处理技术相结合的基础，而实现通信数字化的前提是信源能提供的各种用于传递的消息，例如语音、图像、数据、文字等都必须以数字化形式表示。而信源编码是数字通信系统中的重要组成部分，他是保证信号有效传输的一种重要方式。霍夫曼编码依据字符出现的概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，其优越的性能被广泛使用在数字通信系统中。霍夫曼编码已经成为数据压缩的灵魂算法。本文介绍了无失真编码算法的构造，霍夫曼编码的规则和特点，同时分析了对信源进行优化的方法，最后通过MATLAB仿真来讨论比较二元霍夫曼编码、三元霍夫曼编码以及信源扩展编码的效率，来实现霍夫曼码的优化构造。关键词：Matlab，霍夫曼编码，仿真,二元霍夫曼编码，三元霍夫曼编码，扩展信源编码HuffmanCodesAndMatlabSimulationLichangjiang(Schoolofminsheng,HenanUniversity,HenanKaifeng475004,China)Abstract:Digitalcommunicationisthebasiswhichcancombinecomputertechnologyanddigitalsignalprocessingtechnology.Butthepremisefordigitalcommunicationisthatthesourcecanprovideavarietyofmessagefortransmission.Forexamplevoice,images,data,text.Andthemessagescanbeexpressedindigitalform.Sourcecodingistheimportantpartinthedigitalcommunicationsystem.Itisalsoawaytoensuretheeffectivenessofthetransmissioninthissystem.Huffmancodingbasedontheprobabilitytoconstructacharacterdifferentprefixlengthoftheshortestaveragecodeword.Sometimesitiscalledtheoptimalcoding.Huffmancodeiswidelyusedinthedigitalcommunicationsystembytheascendantperformance.Huffmancodinghasbecomedatacompressionsoulalgorithm.Thisarticledescribestheconstructionoflosslesscodingalgorithm.ItalsointroducestherulesandthecharacteristicsofHuffmancoding.Italsoanalyzesthemethodofsourceoptimization.Finally,wediscuss河南大学民生学院本科毕业论文2thecomparisonofbinaryHuffmancoding,ternaryHuffmancodingandextendedsourcecodingbasedonMATLAB.WearethustoachieveoptimalHuffmancodeconstructed.Keywords:MATLAB；huffmancode；binaryHuffmancoding;ternaryHuffmancoding;extendedsourcecoding0前言在通信的数字化过程中，对于时间连续和取值连续的原始语音和图像等模拟信号来说，如果要以数字方式进行传输，在发送端必须首先进行模/数(A/D)变换，将原始信号转换为时间离散和取值离散的数字信号。模拟信号数字化之后一般会导致传输信号的带宽明显增加，这样就会占用更多的信道资源，使得传输效率降低，或者无法实现实时传输。为了提高传输效率，一方面需要采用压缩编码技术，在保证一定信号质量的前提下，尽可能地去除信号中的冗余信息，从而减少信号速率和传输所用带宽。另一方面，即使是原本就以数字形式存在的数据和文字信息，也同样存在一个需要通过压缩编码降低信息冗余提高传输效率的问题。由于这些处理都是针对信源发送信息所进行的，因此一般将其称为信源编码。信源编码的基本目的是提高码字序列中码元的平均信息量，那么，一切旨在减少剩余度而对信源输出符号序列所施行的变换或处理，都可以在这种意义下归入信源编码的范畴，例如过滤、预测、域变换和数据压缩等。作为现代数据无损压缩的灵魂算法，霍夫曼编码正广泛应用于各种图像、音频、视频及各种多媒体信息的压缩环境中。1信源编码的基本概念1.1通信系统的模块仿真噪声信源信源编码信道编码信道信道译码信源译码信宿河南大学民生学院本科毕业论文31.2信息的度量与编码信息是指消息中包含的有效内容，度量信息量的原则首先是能度量任何消息并与消息的种类无关，其次度量方法应该与消息的重要程度无关，最后消息中所含信息量和消息内容的不确定性有关。信息熵的输出可以用随机过程来描述。对于一个离散无记忆平稳随机过程，其信息量（熵）定义为：()()log()xXHXpxpx其中X表示信源取值集合，p(x)是信源取值x的概率。MATLAB信源编译码方法大多数信源（比如语音、图像）最开始都是模拟信号，为了将信源输出数字化，信源必须量化为确定数目的级数。量化方案可划分为标量量化和矢量量化两种。在标量量化中每个信源输出都分别被量化，标量量化可进一步分为均匀量化和非均匀量化。在均匀量化中量化区域是等长的；在非均匀量化中量化区域可以是不等长的。矢量量化是对信源输出组合进行整体量化。在标量量化中，随机标量X的定义域被划分成N个互不重叠的区域Ri，1≤i≤N,Ri被称为量化间隔，且在每个区域内选择一个点作量化级数。这样落在区域Ri内的随机变量的所有值都被量化为第i个量化级数，用ix来表示，这就意味着：()iixRQxx易见，这类量化引入了失真，其均方误差为：21()()iNixiRDxxfxdx其中f(x)是信源随机变量的概率密度函数。信号量化噪声比(SQNR)为：210[]10logEXSQNRD信源编码是数字通信中的重要环节，它的主要目的是减少冗余，提高编码效率。信源编码可分为两类：无失真编码和有失真编码。无失真编码只对信源冗余度进行压缩，不会改变信源的熵，又称冗余度压缩编码，它能保证码元序列经译码后能无失真的恢复成信源符号序列，如霍夫曼编码，香农编码。有失真编码在允许的失真范围内把编码后的信息率压缩到最小，有失真信源编码的失真范围受限，所以又称为限失真信源编码。信源编码就是把信源符号序列变换到码符号序列的一种映射。若要实现无失真编码，那么这种映射必须是一一对应的、可逆的。一般来说，人们总希望把信源所有的信息毫无保留的传递到接受端，即实现无失真传输，所以首先要对信源实现无失真编码。信源编码有以下三种主要方法：河南大学民生学院本科毕业论文4（1）匹配编码根据信源符号的概率不同，编码的码长不同,这样使平均码长最短。将要讲到的霍夫曼编码就是概率匹配编码。（2）变换编码先对信号进行变换，从一种信号空间变换为另一种信号空间，然后针对变换后的信号进行编码。一般是把分布在时空域的信号（如时域的语音信号和平面空间的图像信号）映射到变换域（如频域的频谱信号和其他正交矢量空间域），原来相关性很强的原始信号经过变换后，得到的变换域系数相互独立，并且能量集中在少数低序系数上，这样只需对少量的变换域的系数进行编码，达到数据压缩的目的。常用的变换编码有DFT、沃尔什变换、小波变换等。(3