基于M语言的数字通信系统仿真 —— 采用Huffman码技术.doc

信电学院 设计说明书 （2013/2014学年第二学期） 课程名称： 通信系统仿真二级项目 题 目： 基于M语言的数字通信系统仿真 —— 采用Huffman码技术 专业班级： 通信工程12-01 学生姓名： 李冕、 董文浩、 李朋 刘凤东 刘伟 学 号： 120310128、120310124、120310125 120310126、120310127 指导教师 ： 李志华、任丹萍、张龙 设计周数 ： 1周 设计成绩 ： 2014年6月26日 1、设计目的和意义 1.1 目的 （1）理解huffman信源编码的理论基础，掌握huffman信源编码的基本方法； （2）根据Huffman编码算法，得到码树和Huffman码； （3）编写M函数，以信源产生的概率向量为变量，返回Huffman编码法的编码结果，返回信源熵和编码的码字长度及计算huffman编码效率。 （4）运用matlab应用软件实现huffman编码，熟悉matlab软件的使用，了解哈弗曼编码的基本基本原理。哈夫曼编码可以无失真的信源编码，无损压缩文件，便于文件传输以及恢复。 1.2、项目的内容及要求 1.2.1基于M语言的数字通信系统仿真—采用Huffman码技术 （1）建立通信系统数学模型； （2）利用M语言建立通信系统仿真模型； （3）对通信系统进行时间流上的仿真，得要仿真结果，计算香浓码编码效率； （4）将仿真结果与理论结果进行比较、分析； 2、实验原理 2.1 课题描述 Huffman编码的基本原理及算法 (1) 把信源符号集中的所有符号按概率从大到小排列。 (2) 取概率最小的两个符号作为两片叶子合并（缩减）到一个节点。 (3) 视此节点为新符号，其概率等于被合并（缩减）的两个概率之和，参与概率排队。 (4) 重复(2)(3)两步骤，直至全部符号都被合并（缩减）到根。 (5) 从根出发，对各分枝标记0和1。从根到叶的路径就给出了各个码字的编码和码长。 2.1.2 例如：哈夫曼编码应用举例 哈夫曼树被广泛的应用在各种技术中，其中最典型的就是在编码技术上的应用。利用哈夫曼树，我们可以得到平均长度最短的编码。这里我们以计算机操作码的优化问题为例来分析说明。 研究操作码的优化问题主要是为了缩短指令字的长度，减少程序的总长度以及增加指令所能表示的操作信息和地址信息。要对操作码进行优化，就要知道每种操作指令在程序中的使用频率。设有7种不同的符号，其使用频率如下表所示： 符号 使用（pi） I1 0.40 I2 0.30 I3 0.15 I4 0.05 I5 0.04 I6 0.03 I7 0.03 0、13位（23＝8）3×n。 图1 构造哈夫曼树示例 对于该二叉树，我们可以规定向左的分支标记为1，向右的分支标记为0。这样，从根结点开始，沿线到达各频度指令对应的叶结点，所经过的分支代码序列就构成了相应频度指令的哈夫曼编码，如下图所示： 符号 编码 I1 0 I2 10 I3 110 I4 11100 I5 11101 I6 11110 I7 11111 3×1000＝3000。1×400＋2×300＋3×150＋5×（50＋40＋30＋30）＝2200。 2.3 huffman编码具体实现 2.3.1原理： 1 在上面程序运行结果正确的情况下，输入的概率矩阵p,对p进行排序，并用矩阵L记录p排序之前各元素的顺序，然后将排序后的概率数组p的前两项，即概率最小的两个数加和，得到新的一组概率序列，重复以上过程，最后得到一个记录概率加和过程的矩阵p以及每次排序之前概率顺序的矩阵a。 2 新生成一个n-1行n列，并且每个元素含有n个字符的空白矩阵，然后进行huffman编码： 将c矩阵的第n-1行的第一和第二个元素分别令为0和1（表示在编码时，根 节点之下的概率较小的元素后补0，概率较大的元素后补1，后面的编码都遵守这个原则） 然后对n-i-1的第一、二个元素进行编码，首先在矩阵a中第n-i行找到值为1所在的位置，然后在c矩阵中第n-i行中找到对应位置的编码（该编码即为第n-i-1行第一、二个元素的根节