信息论编码（课程设计）.doc

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