霍夫曼编码
《信息论与编码》课程实验报告
姓 名 学 号
单 位
专 业
2014 年 12 月 4 日
实验一
一、实验目的
1、理解信源编码的意义；
2、掌握霍夫曼编码的方法及计算机实现；
二、实验原理
通信的根本问题是如何将信源输出的信息在接收端的信宿精确或近似的复制出来。为了有效地复制信号，就通过对信源进行编码，使通信系统与信源的统计特性相匹配。
霍夫曼编码就是利用变长信源编码定理，将等长分组的信源符号，根据其概率分布采用不等长编码。概率大的分组，使用短的码字编码；概率小的分组，使用长的码字编码。霍夫曼编码把信源按概率大小顺序排列，并设法按逆次序分配码字的长度。在分配码字的长度时，首先将出现概率最小的两个符号相加，合成一个概率；第二步把这个合成的概率看成是一个新组合符号的概率，重复上述做法，直到最后只剩下两个符号的概率为止。完成以上概率相加顺序排列后，再反过来逐步向前进行编码。每一步有两个分支，各赋予一个二进制码，可以对概率大的编为0码，概率小的编为1码。反之亦然。
霍夫曼编码的具体步骤归纳如下：
1. 统计n个信源消息符号，得到n个不同概率的信息符号。
2. 将这n个信源信息符号按其概率大小依次排序：
p(x1) ≥ p(x2)≥ …≥ p(xn)
3. 取两个概率最小的信息符号分别配以0和1两个码元，并将这 霍夫曼编码
两个概率相加作为一个新的信息符号的概率，和未分配的信息符号构成新的信息符号序列。
4. 将剩余的信息符号，按概率大小重新进行排序。
5. 重复步骤3，将排序后的最后两个小概论相加，相加和与其他概率再排序。
6. 如此反复重复n-2次，最后只剩下两个概率。
7. 从最后一级开始，向前返回得到各个信源符号所对应的码元序列，即相应的码字，构成霍夫曼编码字。编码结束。
例：设有8个字符{A,B,C,D,E,F,G,H}，其概率为
{0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11}，设其权值为{5,29,7,8,14,23,3,11}，则据此构造出的霍夫曼树为：
霍夫曼编码产生最佳整数前缀码，即没有一个码字是另一个码字的前缀，因此霍夫曼编码是唯一码。
编码之后，霍夫曼编码的平均码长为：
n
=∑p(xi)Ki i=1
霍夫曼编码的效率为：
η=
三、实验步骤
信源熵H(x)= 平均码长
四、运行结果
五、实验分析
（1）在霍夫曼编码的过程中，对输入的信源符号按概率有大到小的顺序重新排列，应使合并后的新符号尽可能排在靠前的位置，这样可使合并后的新符号重复编码次数减少，使短码得到充分利用。
（2）霍夫曼编码效率相当高，对编码器的要求也简单得多。
（3）霍夫曼编码保证了信源概率大的符号对应于短码，概率小的符号对应于长码，每次缩减信源的最后两个码字总是最后一位码元不同，前面的各位码元都相同，每次缩减信源的最长两个码字有相同的码长。
（4）霍夫曼的编法并不一定是唯一的。
六、实验总结 此次设计用C语言实现霍夫曼对信源无失真编码，对自己来讲确实是一大挑战。知道实验题目之后，原以为用计算机实现是很简单的事情，于是没有多想便开始编码。可是真正开始时，才发现要想将脑袋里所想的转化为计算机程序语言，着实不易。
于是，我求助于数据结构知识，通过查阅资料，了解了如何用特定的数据结构来构造一棵霍夫曼树，如何基于这样的树进行霍夫曼编码。
在编出程序后，我还根据信息论与编码的知识计算了平均码长、编码效率和码方差，使得自己可以更加直接地体会到霍夫曼编码的相关性质和优越性，深化了对霍夫曼编码的理解。
这次设计编程的思路，编辑，调试等让我明白编程时理论联系实际的重要性，也更加明白了计算机在现代科学技术中的重要地位。正如钱学森先生所说：到了二十一世纪，科技人才懂得如何用计算机来解决问题是十分重要的。我再接下来的学习中还会继续提高自己的编程实践能力，争取更大进步。