编写matlab函数实现huffman编码的算法

编写Matlab函数实现哈夫曼编码的算法一、设计目的和意义在通信的数字化过程中，对于连续的原始语音图像等模拟信号，如果要以数字化的方式进行传输，在发送端必须进行模/数（A/D）转换，将原始信号转变为离散的数字信号。模拟信号在数字化之后一般会导致传输信道带宽明显增加，这样就会占用更多的信道资源，传输效率也会随之较低，有时甚至无法实现实时传输。为了提高传输效率，一方面需要采用压缩编码技术，在保证一定信号质量的前提下，尽可能地去除信号中的冗余信息，从而减少信号速率和传输所用带宽。另一方面，即使是原本就以数字形式存在的数据和文字信息，也同样存在一个需要通过压缩编码降低信息冗余提高传输效率的问题。由于这些处理都是针对信源发送信息所进行的，因此一般将其称为信源编码。信源编码的基本目的是提高码字序列中码元的平均信息量，那么，一切旨在减少剩余度而对信源输出符号序列所施行的变换或处理，都可以在这种意义下归入信源编码的范畴，例如过滤、预测、域变换和数据压缩等。作为现代数据无损压缩的灵魂算法，霍夫曼编码广泛应用于各种图像、音频、视频及各种多媒体信息的压缩环境中。本次课程设计的意义在于使我们对我们使用matlab工具来实现通信系统的模拟设计，同时也使我们明白信源在调制前做编码的重要性。二、设计原理2.1通信系统的组成通信就是由一地向另一地传送信息，通信系统的仿真模块如下面框图2-1所示。通信系统组成框图图2-12.2信息的度量与编码信息是指消息中包含的有效内容，度量信息量的原则首先是能度量任何消息并与消息的种类无关，其次度量方法应该与消息的重要程度无关，最后消息中所含信息量和消息内容的不确定性有关。信息熵的输出可以用随机过程来描述。对于一个离散无记忆平稳随机过程，其信息量（熵）定义为：)(log)()(xpxpXHXx(1)其中X表示信源取值集合，p(x)是信源取值x的概率。2.3MATLAB信源编译码方法在自然界中，大多数信源最开始都是模拟信号，为了使信源数字化输出，信源必须量化为确定数目的级数。有两种量化方案，即标量量化和矢量量化。在标量量化中每个心愿输出都分别被量化，标量量化又可以分为均匀量化和非均匀量化。矢量量化是对信源输出组合进行整体量化。在标量量化中，随机标量X的定义域被划分成N个互不重叠的区域iR，Ni1,iR被称为量化间隔，且在每个区域内选择一个点作量化级数。这样落在区域内的随机变量的所有值都被量化为第i个量化级数，用iX来表示，这就意味着：iixxRx)((2)显而易见，这类量化引入了失真，其均方误差为：dxxfxxdxNiRii)()(12(3)其中f(x)是信源随机变量的概率密度函数。信号量化噪声比(SQNR)为：dXESQNR][log10210(4)信源编码的主要目的是减少冗余，提高编码效率。信源编码可分为两类：无失真编码和有失真编码。无失真编码只对信源冗余度进行压缩，不会改变信源的熵，又称冗余度压缩编码，它可以保证码元序列经译码后能无失真的恢复成信源符号序列，如huffman编码，香农编码。有失真编码在允许的失真范围内把编码后的信息率压缩到最小，有失真信源编码的失真范围受限，所以又称为限失真信源编码。信源编码就是把信源符号序列变换到码符号序列的一种映射。若要实现无失真编码，那么这种映射必须是一一对应的、可逆的。一般来说，人们总希望把信源所有的信息毫无保留的传递到接受端，即实现无失真传输，所以首先要对信源实现无失真编码。信源编码有以下三种主要方法：（1）匹配编码根据信源符号的概率不同，编码的码长不同,这样使平均码长最短。将要讲到的霍夫曼编码就是概率匹配编码。（2）变换编码先对信号进行变换，从一种信号空间变换为另一种信号空间，然后针对变换后的信号进行编码。一般是把分布在时空域的信号（如时域的语音信号和平面空间的图像信号）映射到变换域（如频域的频谱信号和其他正交矢量空间域），原来相关性很强的原始信号经过变换后，得到的变换域系数相互独立，并且能量集中在少数低序系数上，这样只需对少量的变换域的系数进行编码，达到数据压缩的目的。常用的变换编码有DFT、沃尔什变换、小波变换等。(3)识别编码识别编码主要用于印刷或打字机等有标准形状的文字、符号和数据的编码，比如中文文字和语音的识别。变换编码和识别均为有失真的信源编码。最原始的信源编码就是莫尔斯电码，另外还有ASCII码和电报码都是信源编码。但现代通信应用中常见的信源编码方式有：霍夫曼编码、算术编码、L-Z编码，这三种都是无损编码。而霍夫曼编码作为变长码满足变长信源编码定理。该编码定理是香农信息论中非常重要的一个定理，它指出，要做到无失真的信源编码，信源每个符号所需要的平均码元数就是信源的熵值，如果小于这个值，则唯一可译码不存在，可见，熵是无失真信源编码的极限值。定理还指出，通过对扩展信源进行编码，当N趋向于无穷时，平均码长可以趋进该极限值。还可以证明，如果我们不确切知道信源的概率分布，我们用估计的概率分布去进行编码时，平均码长会加长，但是如果估计的偏差不大的话，平均码长也不会增加太多。2.4无失真编码算法2.4.1无失真信源编码定理设单符号、离散、无记忆信源的熵为H(S)，若用二进制码对其做变字长、非续长编码，一定可以找到一种编码方式，其平均码长满足：1)()(SHmSH(5)不等式左边表明，信源的熵是作无失真二进制变字长编码平均码长的下限。如果用符号等于其信息量得码长)(kkalbpm(6)编码，则可以使平均码长达到其下限——熵)()()()(111SHalbpapmapmkkkkKKk(7)所以，这种变字长的统计编码又称熵编码。2.4.2变长码及变长编码定理信源符号数、码符号数、码字长度之间满足什么条件才可以构成即时码和唯一可译码呢？Kraft不等式和McMillan不等式回答了这个问题。这两个不等式在形式上是完全一样的。设信源符号集为},...,,{21qsssS，码符号集为},...,,{21rxxxX，对信源进行编码，得到的码为},...,,{21q，码长分别为qlll,...,,21。即时码存在的充要条件是：11qilir(8)这称为Kraft不等式。由上式可知，给定r和q，只要允许码字长度可以足够长，则码长总可以满足Kraft不等式而得到即时码，Kraft不等式指出了即时码的码长必须满足的条件。后来McMillan证明对于唯一可译码得码长也必须满足此不等式。在码长的选择上唯一可译码并不比即时码有更宽松的条件。对于唯一可译码，该不等式又称为McMillan不等式。唯一可译码存在的充要条件是：11qilir(9)其中r为码符号个数，为码字长度，q为信源符号个数无失真变长信源编码定理离散无记忆信源S的N次扩展信源NS，其熵为)(NSH，并且编码器的码元符号集为},...,,{:21qaaaA对信源NS进行编码，总可以找到一种编码方法，构成唯一可译码，使信源S中每个符号iS所需要的平均码长满足NrSHNLrSHN1)log()()log()((10)当N时则有)(SHNLrN，λ式中iqiiNNSPL1)(，其中i是扩展信源的信源符号iS所对应的码字长度，因此是扩展信源中每个符号的平均码长，而NLN是信源S中单个信源符号所需的平均码长。这里要注意NLN与NL的区别：它们都是单个信源符号所需的码符号的平均数，但是NLNV的含义是，为了得到这个平均值，不是对单个信源符号进行编码，而是对N个信源符号序列进行编码，然后对N求平均。该定理指出，要做到无失真信源编码，每个信源符号平均所需最少的r元码元数就是信源的熵值。若编码的平均码长小于信源的熵值，则唯一可译码不存在，在译码或反变换时必然要带来失真或差错，同时定理还指出，通过对扩展信源进行变长编码，当N时，平均码长L可达到这个极限值。可见，信源的信息熵H(S)是无失真信源编码码长的极限值，也可认为信源熵是表示每个信源符号平均所需最少的码元符号数。2.5信源最佳化通信系统的传输效率就是指给定信道的信道容量利用率，它表示信道的实际传信率与信道容量的比值，可以写成：CR(11)可见要提高传输效率，基本任务就是要改造信源，使其熵值最大化，此时η趋于1，而这个过程就是信源最佳化得过程。信源熵H(X)最大化实质上就是寻求一种最佳的概率分布。根据熵函数的性质，在离散信源情况下，当各个符号间彼此独立而出现的概率相等时，信源熵达到最大值。因此，一般的熵值最大化应当包括两个步骤：1、符号独立化，解除符号间的相关性；2、各符号概率均匀化。为了衡量各种编码是否已达到极限情况，我们定义变长码的编码效率。设对信源S进行无失真编码所得到的平均码长为L,则)(SHLr,定义LsHr)((12)为编码效率，1。我们可以采用声码器技术，模式识别技术，变换编码技术以及相关编码技术等近几年来发展起来的效率较好的压缩信源方法来解除关联、压缩信源和提高传输效率。经过解除相关性之后，如果再使各符号的概率均匀化，就能进一步改造有剩余信源的输出，去掉冗余度，提高熵速率，使传输率接近信道容量进而使传输效率接近1。如香农-范诺编码，霍夫曼编码。这列编码的基本思想就是使各符号的概率均匀化，即出现概率大的符号编成短码，出现概率较小的符号编成长码，只是由于具体方法不同，得到的效果也不同。2.7二元霍夫曼编码规则（1）将信源符号依出现概率递减顺序排序。（2）给两个概率最小的信源符号各分配一个码位“0”和“1”，将两个信源符号合并成一个新符号，并用这两个最小的概率之和作为新符号的概率，结果得到一个只包含（n-1）个信源符号的新信源。称为信源的第一次缩减信源，用s1表示。（3）将缩减信源s1的符号仍按概率从大到小顺序排列，重复步骤二，得到只含（n-2）个符号的缩减信源s2。（4）重复上述步骤，直至缩减信源只剩两个符号为止，此时所剩两个符号的概率之和必为1，然后从最后一级缩减信源开始，依编码路径向前返回，就得到各信源符号所对应的码字。2.8多元霍夫曼编码规则由二进制霍夫曼编码的方法很容易推广到r进制的情况，只是编码的过程中构成缩减信源时，每次都是将r个概率最小的信源符号合并，然后分别用码符号0,1，...,(r-1)表示。为了充分利用短码，使霍夫曼码的平均码长最短，必须使最后一个缩减信源恰好有r个信源符号，因此对于r元霍夫曼码，信源S符号个数q必须满足rrq)1((13)其中表示信源缩减次数。如果不满足上式，则可以在最后增补一些概率为零的信源符号，因此上式又可以写成rriq)1((14)i为增加的信源符号数，并且是满足上式的最小正整数或0。这样处理后得到的r元霍夫曼码可充分利用短码，一定是紧致码。4.3扩展信源霍夫曼编码对离散无记忆信源的N次扩展信源进行编码便得到N次扩展码。采用霍夫曼编码法能够使码的平均长度最短，信息的冗余量最小。然而这种编码方法所形成的码字很不规整，这样不利于硬件的译码。在很多处理机中，我们采用一种新的折中的方法，称为扩展编码法。这种方法是由定长编码与霍夫曼编码法相结合形成的。有等长扩展法和不等长扩展编码方法，为了便于实现分级译码，我们一般采用等长扩展编码法，当然，也可以根据具体需要采用每次扩展位数不等的不等长扩展法。三、详细设计步骤3.1二元huffman编码树的计算由huffman的编码规则，建立的编码树如下图所示，二元huffman编码树图3-1由上图的编码树，我们可以清楚的得出个码元对应的编码：d0:0000,d1:0001,d2:001,d3:010,d4:011,d5:110,d6:111,d7:1010.180.220.60.090.30.40.060.030.090.10.120.30.140.1600000001111111d0d1d2d3d4d5d6d73.2信源熵的计算3.2.1信源熵计算程序的流程图信源熵计算流程图图3-23.2.2信源熵计算程序设计对信源S编码，现对该离散无记忆平稳信源进行霍夫曼编码。