霍夫曼信源编码实验报告.docx
PAGE
PAGE 7
实验1：霍夫曼信源编码综合设计【实验目的】通过本专题设计，掌握霍夫曼编码的原理和实现方法，并熟悉利用C语言进行程序设计，对典型的文本数据和图像数据进行霍夫曼编解码。
【预备知识】1、熵的概念，霍夫曼编码原则2、数据结构和算法设计3、C(或C++)编程语言
【实验环境】设备：计算机一台软件：C程序编译器
【设计要求】根据霍夫曼编码原则，利用C语言设计并实现霍夫曼编码和解码程序，要求能够对给出的典型文本数据和图像数据进行霍夫曼编解码，并计算相应的熵和压缩比。
【实验原理】Huffman编码属于熵编码的方法之一，是根据信源符号出现概率的分布特性而进行的压缩编码。Huffman编码的主要思想是：出现概率大的符号用长的码字表示；反之，出现概率小的符号用短的码字表示。Huffman编码过程描述：1. 初始化: 将信源符号按出现频率进行递增顺序排列，输入集合L;2. 重复如下操作直至L中只有1个节点:(a) 从L中取得两个具有最低频率的节点，为它们创建一个父节点； (b) 将它们的频率和赋给父结点，并将其插入L;3. 进行编码 ： 从根节点开始，左子节点赋予1，右节点赋予0，直到叶子节点。
【基本定义】熵和平均编码符号长度熵是信息量的度量方法，它表示某一事件出现的概率越小，则该事件包含的信息就越多。根据Shannon理论，信源S的熵定义为,其中是符号在S中出现的概率；表示包含在中的信息量，也就是编码所需要的位数假设符号编码后长度为li (i=1,…,n)，则平均编码符号长度L为：压缩比设原始字符串的总长度为Lorig位,编码后的总长度为Lcoded位，则压缩比R为 R = (Lorig - Lcoded)/ Lorig
【例子】有一幅40个象素组成的灰度图像，灰度共有5级，分别用符号A、B、C、D和E表示，40个象素中出现灰度A的象素数有15个，出现灰度B的象素数有7个，出现灰度C的象素数有7个等等，如表1所示。如果用3个位表示5个等级的灰度值，也就是每个象素用3位表示，编码这幅图像总共需要120位。表1 符号在图像中出现的数目符 号ABCDE出现的次数157765根据Shannon理论，这幅图像的熵为H(S) = (15/40)?(40/15)+(7/40)?(40/7)+???+(5/40)?(40/5)=2.196平均编码符号长度L为(15/40)*1+(7/40)*3+(7/40)*3+(6/40)*3+(5/40)*3 ＝ 2.25根据霍夫曼编码原则可以得到如下的霍夫曼编码表。表2 霍夫曼编码举例符号出现的次数log2(1/pi)分配的代码所需 位数A15(0.375)1.4150115B7(0.175)2.514501121C7(0.175)2.514501021D6(0.150)2.736900118E5(0.125)3.000000015因而，这副图采用霍夫曼编码的压缩比R为1.3333:1(120:90)。霍夫曼码的码长虽然是可变的，但却不需要另外附加同步代码。例如，码串中的第1位为0，那末肯定是符号A，因为表示其他符号的代码没有一个是以0开始的，因此下一位就表示下一个符号代码的第1位。同样，如果出现“110”，那么它就代表符号D。如果事先编写出一本解释各种代码意义的“词典”，即码簿，那么就可以根据码簿一个码一个码地依次进行译码。
【实验步骤】(16学时)根据提供的示例Huffman编译码器源程序，利用VC++6.0进行编译生成可执行文件，阅读并运行程序。用Microsoft Office Vision分别画出Huffman编码和译码程序流程图，写出用到的主要数据结构并加以说明。在Huffman编码器合适位置加入4个函数：calcProbability，calcEntropy，calcAvgSymbolLength，calcCompressionRatio，分别计算信源各符号出现的概率、信源的熵、平均编码符号长度以及压缩比。(自定义函数的参数)分析霍夫曼编译码码的计算复杂度，定量说明Huffman编码和译码哪种操作更耗时？设计中遇到的问题，怎样解决问题的。在设计过程中的心得体会。
思考题：霍夫曼编码是否具有唯一性？个人对霍夫曼编码方式的不足之处的思考以及怎么样在进行压缩时避免这些问题。分析霍夫曼编码对文本数据以及图象数据的编码效率，观察与对应信源概率分布的关系。参考静止图像压缩编码国际标准JPEG，为了提高对图像编码的效率，通常要在霍夫曼编码之前进行什么操作？。
【实验结果】
