Huffman编码和译码的MATLAB实现.doc

Huffman编码及译码的MATLAB实现 沈逸峰 （上海师范大学 信息与机电工程学院，上海 200333） 摘要：本论文首先介绍了Huffman编码的原理以及与其它编码相比它的优势随在，随后基于Huffman编码的原理，利用MATLAB编译出26个英文字母加空格的Huffman码表以及相应的编码和译码程序。 关键词：Huffman，MATLAB Implement of Huffman code and decode in Matlab Shen Yi-feng (School of Information and Engineering.Shanghai Normal University.Shanghai.200333) Abstract:This article has mainly introduced the theory of Huffman Code and the advantage of this code.Then, we use MATLAB to find the code table for the English alphabet and space based on Huffman Code theory. Finally, we design the code and decode program for these alphabet and space based on the same theory. Key words:Huffman, MATLAB 1.引言 Huffman编码属于信源编码，由于信源符号之间存在分布不均匀和相关性，致使信源存在冗余度。因此信源编码的主要任务就是减少冗余，从而提高编码的效率。信源编码的关键是信息论中的两个基本定理[1]：无失真编码定理和限失真编码定理，其中，无失真编码定理可看成是可逆编码的基础，即当信源符号变换为代码后，可从代码无失真地恢复原信号，本文所研究的Huffman编码即是一种基于无失真编码定理的最佳无失真信源编码 2.Huffman编码简介及其优势 Huffman 是一种可变字长编码Huffman于1952年，完全出现概率，最佳编码，经常应用于数据压缩例如，在英文中，p的出现概率很高，而u出现概率利用哈夫曼Huffman编码对进行压缩时，p很有可能用1位(bit)来表示，而z则可能25个位来表示。如果用普通的方法时，每个英文字母均占用一个字节。二者相比，Huffman大幅度提高压缩的 3.Huffman编码原理的实现 实现Huffman编码原理的步骤如下： 首先将信源符号集中的符号按概率大小从大到小排列。 用0和1表示概率最小的两个符号。可用0表示概率小的符 号，也可用1表示概率小的符号，但整个编码需保持一致。 将这两个概率最小的符号合并成一个符号，合并符号概率为 最小概率之和，将合并后的符号与其余符号组成一个N-1的新信源符号集，称之为缩减符号集。 对缩减符号集用步骤1,2操作 以此类推，直到只剩两个符号，将0和1分别赋予它们。 根据以上步骤，得到0,1赋值，画出Huffman码树，并从最 后一个合并符号回朔得到Huffmaan编码。 下面给出一个具体实例来说明Huffman编码的实现过程。 4.举例说明 已知有四个符号的符号集，它们的概率如下： 对这四个符号进行Huffman编码。 根据Huffman编码的原理，我们首先对这四个符号集按概率大小从大到小排列，即a1,a2,a3,a4。然后，我们再根据编码原理的第二步，把概率最小的a4用符号1来表示，把概率第二小的a3用符号0来表示，并把a4,a3合并成a34，a34的概率为两者概率之和。这里要注意的是，既然我们把a4和a3合并成一个新符号a34，那么最后编码的时候a4,a3一定要是等码长的，否则我们就不能将这两个符号合并。组成的新信源符号集由a1,a2,a34三个符号组成，它们所对应的概率分别是0.5,0.3和0.2，因此将概率最小的a34用符号1来表示，把概率第二小的a2用符号0来表示，并把a34,a2合并成a234，a234的概率为两者概率之和。注意虽然最后我们只要对a1,a2,a3,a4四个符号进行Huffman编码，但在编码的过程中a34和a2的码长必须一致，否则就不能将两者合并。组成的新信源符号集由a1,a234两个符号组成，它们两者的概率相等，都是0.5，因此我们将a234用符号1来表示，a1用符号0来表示。接下来我们构造Huffman树如下图所示： a4 a34 a234 a1234 0 0 0 a3