赫夫曼编码（二进制与三进制编码）信息论与编码实验报告

《赫夫曼编码（二进制与三进制编码）信息论与编码实验报告》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、信息论与编码实验报告实验课程名称：赫夫曼编码（二进制与三进制编码）专业信息与计算科学班级信息与计算科学1班学生姓名李林钟学号　2013326601049指导老师王老师18一、实验目的利用赫夫曼编码进行通信可以大大提高通信利用率，缩短信息传输时间，降低传输成本。赫夫曼编码是信源编码中最基本的编码方法。l理解赫夫曼编码，无论是二进制赫夫曼编码，还是m进制赫夫曼编码，都要理解其编码原理和编码步骤。l回顾无失真信源编码定理，理解无失真编码的基本原理和常用编码方法。。l掌握二进制赫夫曼编码和m进制赫夫曼编码的基本步骤，能计算其平均码长，编码效率等。l应用二进制赫夫曼编码或m进制赫夫曼编码处理简单的实

2、际信源编码问题。二、实验环境与设备1、操作系统与编程软件：windows操作系统，cfree5.0，VisualC++6.0。2、编程语言：C语言以及C++语言三、实验内容1.二进制赫夫曼编码原理及步骤：（1）信源编码的计算设有N个码元组成的离散、无记忆符号集，其中每个符号由一个二进制码字表示，信源符号个数n、信源的概率分布P={p(si)},i=1,…..,n。且各符号xi的以li个码元编码，在变长字编码时每个符号的平均码长为；信源熵为：；唯一可译码的充要条件：；其中m为码符号个数，n为信源符号个数，Ki为各码字长度。（2）二元霍夫曼编码规则（1）将信源符号依出现概率递减顺序排序。（2）

3、给两个概率最小的信源符号各分配一个码位“0”和“1”，将两个信源符号合并成一个新符号，并用这两个最小的概率之和作为新符号的概率，结果得到一个只包含（n-1）个信源符号的新信源。称为信源的第一次缩减信源，用s1表示。（3）将缩减信源s1的符号仍按概率从大到小顺序排列，重复步骤(2)，得到只含（n-2）个符号的缩减信源s2。（4）重复上述步骤，直至缩减信源只剩两个符号为止，此时所剩两个符号的概率之和必为1，然后从最后一级缩减信源开始，依编码路径向前返回，就得到各信源符号所对应的码字。18(3).算法基本步骤描述得到信源序列输出得出信源序列个数得出信源序列的概率输出计算信源符号熵输出信源符号的赫

4、弗曼编码平均码长输出输出编码效率输出码方差(4).编码及注解（见附页1）(5).验证截图:182.三进制编码：(1).三进制赫弗曼编码原理：对于多进制赫夫曼编码，为了提高编码效率，就要是长码的符号数量尽量少、概率尽量小，所以信源符号数量最好满足n=(m-1)*k+r,其中m为进制数，k为缩减的次数。设计步骤如下：[1]将信源符号按概率从大到小的顺序排列，令p(x1)≥p(x2)≥…≥p(xn)[2]给两个概率最小的信源符号p(xn-1)和p(xn)各分配一个码位“0”和“1”，将这两个信源符号合并成一个新符号，并用这两个最小的概率之和作为新符号的概率，或者在新添加一个信源符号，令其概率为0

5、，则个分配一个码位“0”、“1”和“2”，将其合并，结果得到一个只包含(n－1)个信源符号的新信源。称为信源的第一次缩减信源，用S1表示。[3]将缩减信源S1的符号仍按概率从大到小顺序排列，此后每次合并3个信源符号，得到只含(n－3)个符号的缩减信源S2。[4]重复上述步骤，直至最后，此时所剩符号的概率之和必为1。然后从最后一级缩减信源开始，依编码路径向前返回，就得到各信源符号所对应的码字。(2).编码及注解（见附页2）(3).例题：对如下单符号离散无记忆信源编三进制赫夫曼码。这里：m=3，n=8令k=3，m+k(m－1)=9，则s=9－n=9－8=1所以第一次取m－s=2个符号进行编码。

6、由计算可得：平均码长为：（3.1）信息率为：（3.2）18编码效率为：（3.3）(4).验证结果截图：18四.实验总结：用C语言实现二进制赫夫曼编码对信源无失真编码。由于课本知识点的不太理解，一点都不知道编码的过程，后来通过阅读<<信息论与编码>>课本、网上查阅资料，最后才对本次设计有了一定的理解，详细理解了赫夫曼的具体编码过程。经过理解，发现这种编码其实挺简单的，最重要的是怎样用程序把他实现，这对我们的编程能力也是一次考验。设计要求中要求计算信源熵，这又考察了现代通信原理的知识。以C++语言实现三进制赫夫曼编码来诠释多进制赫夫曼编码，其实不论是几进制的赫夫曼编码，只要掌握了编码的原理，是

7、非常简单的。通过这次课程设计，我又重新的将信息论编码与设计的教材翻看了一遍，在网上也搜到了不少相关的知识，知识有提升不少。在这次课程设计中，最让人难懂的就是C++的编程，让我找了不少相关的书籍，上网查阅了不少的程序，对以前学过的编程又进一步巩固和提高了。在编程中，要涉及到编制赫夫曼树，平均码长，编码效率，信息率，信源熵。通过同学，网上查阅资料，终于得到解决，虽然仍有一些问题，但是大体上自己能编程出来，是对自己的考验。而且