信息论基础课程报告.docx-资料库

discern_-11907653-16359647596460086193.docx.pdf-第1页.png

第1页 / 共7页

discern_-11907653-16359647596460086193.docx.pdf-第2页.png

第2页 / 共7页

discern_-11907653-16359647596460086193.docx.pdf-第3页.png

第3页 / 共7页

discern_-11907653-16359647596460086193.docx.pdf-第4页.png

第4页 / 共7页

discern_-11907653-16359647596460086193.docx.pdf-第5页.png

第5页 / 共7页

discern_-11907653-16359647596460086193.docx.pdf-第6页.png

第6页 / 共7页

discern_-11907653-16359647596460086193.docx.pdf-第7页.png

第7页 / 共7页

《信息论基础》课程报告 ——霍夫曼编码的编程实现 1 试验目的（1）掌握霍夫曼编码的构造过程。（2）掌握霍夫曼编码中平均码长和编码效率的定义及计算。（3）利用 C++编程实现霍夫曼编码的构造及对平均码长和编码效率的计算。 2 霍夫曼（Huffman）码原理 2.1 二元霍夫曼码 1952 年霍夫曼提出了一种构造最佳码的方法称为霍夫曼码。霍夫曼适用于多元独立信源，对于多元独立信源来说它是最佳码。它充分利用了信源概率分布的特性进行编码，是一种最佳的逐个符号的编码方法。二元霍夫曼码的编码步骤为：（1）将 q 个信源符号按概率分布P()的大小，以递减次序排列起来，设 1≥2≥3≥…≥ （2）用 0 和 1 码符号分别分配给概率最小的两个信源符号，并将这两个概率最小的信源符号合并成一个新符号，并用这两个最小概率之和作为新符号的概率，从而得到只包含 q-1 个符号的新信源，称为 S 信源的缩减信源1。（3）把缩减信源1的符号仍按概率大小以递减次序排列，再将其最后两个 q-2 个符号的缩减信源2。（4）依次进行下去，直至缩减信源最后只剩两个符号为止。将这最后两个符号分别用 0 和 1 码符号表示。最后这两个符号的概率之和必为 1。然后从最后概率最小的符号合并成一个新符号，并分别用 0 和 1 码符号表示，这样又形成了一级缩减信源开始，依编码路径由后往前返回，就得出各信源符号所对应的码符号序列，即得对应的码字。从霍夫曼码的编码过程中不难得到，霍夫曼编码方法得到的码一定是即时码，因为这种编码方法不会使任一码字的前缀为码字。

霍夫曼编码方法得到的码并非是唯一的。首先因为，每次对缩减信源最后两个概率最小的符号，用 0 和 1 码是可以任意的，所以可以得到不同的码。由于每次都是概率最小的两个符号缩减一次成新别。其次，若当缩减信源中缩减合并后的符号的概率与其他信源符号概率相同时，从编码方法上来说，它们概率次序的排列哪个放在上面是没有什么区别的，但得符号，所以没有任何中间节点为码字，则所得到的不同的码仍都是即时码。但它们只是码字具体形式不同，而其码长不变，平均码长也不变，所以没有本质差到的码是不同的霍夫曼编码。对于这两种不同的码，它们的码长各不同，然而平均码长是相同的。对应于长码，即>，有≤，而且短码得到充分利用。（1）霍夫曼码的编码方法保证了概率大的符号对应于短码，概率小的符号（2）每次缩减信源的最后两个码字总是最后一位码元不同，前面各位码元二元霍夫曼码具有以下三个特点：相同（二元编码情况）。（3）每次缩减信源的最长两个码字有相同的码长。这三个特点保证了所得的霍夫曼码一定是最佳码。 2.2 r 元霍夫曼码等码元表示，为了使短码得到充分利用，使平均码长为最短，必须使最后一步的二元霍夫曼码的编码方法同样可以推广到 r 元编码中来。不同的只是每次把缩减信源有 r 个信源符号。因此对于 r 元编码，信源 S 的符号个数 q 必须满足 r 个符号（概率最小的）合并成一个新的信源符号，并分别用 0，1，…，r−1 式中，θ表示缩减的次数，r−1 为每次缩减所减少的信源符号个数。对于二元可见对于二元码，q 等于任意正整数时，总能找到一个θ满足上式。而对于 r 元码，q 为任意正整数时不一定能找到一个θ使式（2.1）满足。若 q 不满足式（2.1） q= r−1θ+r （2.1） q=θ+2 时，不妨虚设 t 个信源符号，并使它们的概率为零。此时，使 q+t 能满足式（2.1）。码（r=2），信源符号个数 q 必须满足（2.2）

这样得到的 r 元霍夫曼码一定是紧致码。 3 试验过程基于实验目的，实验按以下步骤完成：（1）结合教材和习题，复习并理解霍夫曼码的编码方法，包括其构造过程和平均码长、编码效率的计算方法。（2）根据霍夫曼码的码树（Huffuman 树）特征，运用二叉树的数据结构设计程序。（3）利用 C++编写相关程序（本试验只实现二元霍夫曼码的编程）。（4）利用测试数据对程序进行测试，并对结果进行分析讨论。 4 数据测试 4.1 教材 P274 例 8.1 【题目】离散无记忆信源 S=[ s1，s2，s3，s4，s5]，它的一种霍夫曼码如表 4.1 所示。表 4.1 一种霍夫曼码【理论计算】它的平均码长为： 5 =0.4∗1+0.2∗2+0.2∗3+0.1∗4+0.1∗4 ==1 =2.2（二元码元/信源符号）信息熵：

Hs =0.4log10.4+2∗0.2log10.2+2∗0.1log10.1≈2.12 编码效率： η=() ≈0.9645 【测试结果】由程序运行算得其平均码长和编码效率如下图：可以看到，它的平均码长=2.2，编码效率η=96.4513%，均与理论计算图 4.1 运行结果值一致。【结果分析】程序运行无差错，已成功完成霍夫曼码的编码。 4.2 教材 P306 习题 8.11 【题目】有两个信源 X 和 Y 如下： () = 1,0.20,2,0.19,3,0.18,4,0.17,5,0.15,6,0.10,70.01 () = 1,0.49,2,0.14,3,0.14,4,0.07,5,0.07,6,0.04,7,0.02,8,0.02,90.01 分别用霍夫曼码编成二元变长唯一可译码，并计算其编码效率。【理论计算】（1）信源 X 信源 X 的一种霍夫曼码如表 4.2 所示。表 4.2 信源 X 的一种霍夫曼码

它的平均码长为：编码效率： 7 = ==1 2.72（二元码元/信源符号） η=() ≈95.9% （2）信源 Y 信源 Y 的一种霍夫曼码如表 4.3 所示。表 4.3 信源 Y 的一种霍夫曼码它的平均码长为：编码效率： 9 = ==1 2.33（二元码元/信源符号） η=() ≈99.3%

【测试结果】由程序运行算得信源 X、信源 Y 平均码长和编码效率分别如图 4.2、图 4.3 所示：图 4.2 信源 X 运行结果图 4.3 信源 Y 运行结果可以看到，信源 X、信源 Y 测试结果均与理论计算值一致。【结果分析】结合题中其他编码方法下编得的二元变长唯一可译码的编码效率，对霍夫曼码的编码方法、香农编码法和费诺编码方法进行比较（由于两外两个编码方法不是本次试验的研究重点，理论结果直接计算给出，不再冗余说明）：信源 X、信源 Y 采用香农编码法的平均码长分别为：=3.14（二元码元/ 信源符号），=2.89（二元码元/信源符号）；编码效率分别为：η≈81.3%， η≈80.1%。信源 X、信源 Y 采用费诺编码法的平均码长分别为：=2.74（二元码元/ 信源符号），=2.33（二元码元/信源符号）；编码效率分别为：η≈95.2%， η≈99.3%。从信源 X 和信源 Y 的三种不同编码方法可以看出：霍夫曼编码所得的平均

码长最短，编码效率最高；香农编码所得的平均码长最长，其编码效率最差；费诺码居中。霍夫曼码在编码时短码得到充分利用，而且一定是概率大的信源符号对应于短码，概率小的信源符号对应于长码。所以，其平均码长最短。 5 试验感想通过本次试验，实现了霍夫曼编码的构造，并实现了对其平均码长和编码效率的计算。此次试验的主要难点在于对霍夫曼码原理的理解与掌握，尤其是对其构造过程的理解，其主要思想是对于霍夫曼树的构造，在编程中运用二叉树的数据结构来构建实现。在此次试验过程中除了教材中的定义，通过查阅资料我也了解到，霍夫曼编码这种编码方式是可变字长编码(VLC)的一种。该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，其主要目的是根据使用频率来最大化节省字符（编码）的存储空间。通过试验验证了霍夫曼码其编码时短码得到充分利用，而且一定是概率大的信源符号对应于短码，概率小的信源符号对应于长码。所以，其平均码长相较于香农编码法和费诺编码法而言最短，相应地，编码效率也相对最高。由此，我对于二元霍夫曼码的三个特点也有了更为深刻的认识，经历试验后才切身得知霍夫曼码的编码方法对短码的充分利用，也实地证实了二元霍夫曼码是最佳二元码。由此也得出结论：霍夫曼方法是一种较具体和有效的无失真信源编码的方法。从此也不难理解，它便于硬件实现和计算机上软件实现，同时仍应用于文件传真，语音处理和图像处理的数据压缩中。在这次对霍夫曼码的研究中，我不仅对教材相关知识有了较为全面、深刻的认识，更使我的编程能力得到锻炼与提升，同时也提高了我对问题的分析能力。

资料库

信息论基础课程报告.docx

相关推荐

课程资源

热门标签

最新资料