信息论作业Huffman编码VC++.doc

汕 头 大 学 工 学 院 三级项目报告 课程名称： 信息论与编码 课程设计题目： 离散信源无失真信源编码 指导教师： 唐雅娟 系 别： 电子工程系 专 业： 电子信息工程 学 号： 姓 名： 合 作 者 完成时间： 2012 年 4 月 1日至 4月 6 日 成绩： 评阅人：唐雅娟 一、内容与要求 目的 熟练掌握无失真信源编码的方法； 熟练掌握Huffman 编码的平均码长和编码效率的计算方法； 掌握 Huffman码的编程实现。 内容 设计一个离散信源无失真信源并进行Huffman编码； 利用C或者其他编程语言计算信源Huffman编码的平均码长和编码效率。 二、报告正文 基本原理 创建哈夫曼树算法如下： 存储结构：构造由信息元素与对应的权值组成的信息元素结构体来存储已给定的字母与其权重信息；构造由信息元素、权值、当前结点的父结点、左结点、右结点组成的哈夫曼树结点结构体来存储树结点的信息，还会很方便地帮助创建哈夫曼树；构造由信息元素与对应的哈夫曼编码结构体来存储哈夫曼编码信息；方便进行对数据的编码。 结构体数组处理：哈夫曼树没有度为 1 的结点，若一个哈夫曼树由 n 个叶子结点，则该哈夫曼树共有2n-1个结点。应用以上的原理，根据用户输入的信息元素的个数n开辟大小为2n-1的哈夫曼树数组来满足创建哈夫曼树的需要，并对此数组进行初始化，叶子结点的信息元素与权值即给定的的信息元素与权值；非叶子结点的信息元素与权值设置为空值；所有哈夫曼树结点的父结点、左结点、右结点设置为 0 。 选择权值最小与次小：在进行比较的过程中循环取出权值进行比较，设置两个s1，s2分别记录本次循环最小与次小的权值，进行下一次的比较选择。返回权值最小与次小的哈夫曼树结点信息。或可反之。 生成小树：应用3)中想法，在用户输入的信息元素中选择权值中最小与次小的元素分别赋值给右叶子结点与左叶子结点，并把这两个权值之和赋值给这两个结点的父结点，记录父结点位置。 生成哈夫曼树：再应用3) 4)把这些小树的父结点的权值进行比较选择，选择权值比较大的设置为新的右结点的权值，权值比较小的设置为左结点，把这两个权值的和赋值给新的父结点；以此重复进行，最终生成哈夫曼树。 算法流程图 下图为哈夫曼树的生成过程中的主要算法（如图1）： 下面是哈夫曼编码过程的大致过程（如图2）： 设计步骤 (1)把信源符号(i=1,2,…,m)出现的概率按由大到小或的顺序排列； (2)对两个概率最小的符号分别标“0”和“1”，然后把这两个概率相加作为一个新的辅助符号的概率； (3)将这个新的辅助符号与其他符号一起重新按概率大小顺序排列； (4)跳到第2步，直到出现概率相加为1为止； (5)用线将符号连接起来，得到一个码树，树的n个端点对应n个信源符号； (6)从最后一个概率为1的节点开始，沿着码树分别到达每个信源符号，将一路遇到的“0”和“1”顺序排列起来，就是对应端点的信源符号的码字。 程序验证 例5.8 选择0 信源符号 概率 码字 A 0.4 11 B 0.2 00 C 0.2 01 D 0.1 100 E 0.1 101 平均码长 2.2 编码效率 0.964534 选择1 信源符号 概率 码字 A 0.4 00 B 0.2 11 C 0.2 10 D 0.1 011 E 0.1 010 平均码长 2.2 编码效率 0.964534 结论：不管哈弗曼编码是哪一种，其平均码长以及编码效率都是一致的。 对比一 题5.13 选择0 信源符号 概率 码字 A 0.25 00 B 0.25 01 C 0.125 100 D 0.125 101 E 0.0625 1100 F 0.0625 1101 G 0.0625 1110 H 0.03125 11110 I 0.03125 11111 平均码长 2.8125 编码效率 1.00002 选择1 信源符号 概率 码字 A 0.25 11 B 0.25 10 C 0.125 011 D 0.125 010 E 0.0625 0011 F 0.0625 0010 G 0.0625 0001 H