1、 信息理论与编码信息理论与编码 课程论文课程论文 题目：题目： 霍夫曼码研究与设计霍夫曼码研究与设计 学生姓名：学生姓名： 学学 号：号： 系系 别：别： 专专 业：业： 通信工程通信工程 任课教师：任课教师： 20132013 年年 6 6 月月 19 19 日日 目目 录录 摘 要 . 1 1 论文课题描述 1 2 霍夫曼设计原理 2 3 设计过程 3 3.1 软件介绍 . 3 3.1.1 Visual C+ 6.0 简介. 3 3.1.2 主要部分 3 3.2 设计内容 . 4 4 编码程序及其分析 . 6 总 结 14 参考文献.15 第 1 页 共 15 页 摘摘 要要 哈夫曼编码的
2、应用很广泛， 利用哈夫曼树求得的用于通信的二进制编码称为 哈夫曼编码。树中从根到每个叶子都有一条路径，对路径上的各分支约定：指向 左子树的分支表示“0”码， 指向右子树的分支表示“1”码， 取每条路径上的“0”或“1” 的序列作为和各个对应的字符的编码，这就是哈夫曼编码。 哈夫曼编码(Huffman Coding)是一种编码方式， 也是可变字长编码(VLC)的一 种。这种方法完全依据字符出现的概率来构造异字头的平均长度最短的码字，有 时称之为最佳编码，一般就叫作哈夫曼编码。对于 M 进制哈弗曼编码，为了提 高编码效率，就要使长码的符号数量尽量少、概率尽量小，所以应使合并的信源 符号位于缩减信源
3、序列尽可能高的位置上，以减少再次合并的次数，充分利用短 码。 本文将采用三进制哈夫曼编码作为例子来诠释 M 进制哈夫曼编码。 在三进制哈夫曼编码中，得出码字、平均码长和编码效率，构造哈夫曼树， 沿着根节点到叶节点从左到右依次为 0、1、2，保证平均码长最小。在本文中采 用 Visual C+6.0 进行编程，此程序中具有输入字符集大小和权值大小，构造哈 夫曼树，并对用户输入的字符串进行编码等功能。 关键词关键词：哈弗曼编码；信源；哈夫曼树；Visual C+6.0； 1 论文课题描述论文课题描述 哈夫曼(Huffman)编码是一种常用的压缩编码方法， 是 Huffman 于 1952 年为 压
4、缩文本文件建立的。它的基本原理是频繁使用的数据用较短的代码代替，较少 使用的数据用较长的代码代替，每个数据的代码各不相同。 第 2 页 共 15 页 哈夫曼压缩是个无损的压缩算法，一般用来压缩文本和程序文件。哈 夫曼压缩属于可变代码长度算法一族。意思是个体符号用一个特定长度的 位序列替代。因此，在文件中出现频率高的符号，使用短的位序列，而那 些很少出现的符号，则用较长的位序列。 哈夫曼编码是哈夫曼树的一个应用，是一种最优的前缀技术，然而其 存在的不足却制约了它的直接应用。 首先， 其解码时间为 O(lavg)， 其中 lavg 为码字的平均长度；其次，更为重要的是，解码器需要知道哈夫曼编码树
5、的结构，因而编码器必须为解码器保存或传输哈夫曼编码树。对于小量数 据的压缩而言，这是很大的开销。因而，应用哈夫曼编码的关键是如何降 低哈夫曼编码树的存储空间。目前流行的很多压缩方法都是用了该技术， 如 GZIB、ZLIB、PNC 等。 2 霍夫曼设计原理霍夫曼设计原理 对于多进制哈夫曼编码， 为了提高编码效率， 就要是长码的符号数量尽量少、 概率尽量小，所以信源符号数量最好满足 n=(m-1)*k+r,其中 m 为进制数，k 为缩 减的次数。 设计步骤如下： 1将信源符号按概率从大到小的顺序排列，令 p(x1) p(x2) p(xn) 2给两个概率最小的信源符号 p(xn-1)和 p(xn)各
6、分配一个码位“0”和“1”，将这两 个信源符号合并成一个新符号，并用这两个最小的概率之和作为新符号的概率， 或者在新添加一个信源符号，令其概率为 0，则个分配一个码位“0”、“1”和“2”， 将其合并，结果得到一个只包含(n1)个信源符号的新信源。称为信源的第一次 缩减信源，用 S1 表示。 3将缩减信源 S1 的符号仍按概率从大到小顺序排列，此后每次合并 3 个信源符 号，得到只含(n3)个符号的缩减信源 S2。 4重复上述步骤，直至最后，此时所剩符号的概率之和必为 1。然后从最后一级 缩减信源开始，依编码路径向前返回，就得到各信源符号所对应的码字。 第 3 页 共 15 页 3 设计过程设计过程 3.13.1 软件介绍软件介绍 3.1.1 Visual C+ 6.03.1.1 Visual C+ 6.0 简介简介 Visual C+ 6.0， 简称 VC 或者 VC6.0， 是微软推出的一款 C+编译器， 将“高 级语
