重庆交通大学信息科学与工程学院
综合性设计性实验报告
专 业 班 级: 通信工程2012级1班
学 号: 631206040118
姓 名: 王松
实验所属课程: 信息论与编码
实验室(中心): 软件与通信实验中心
指 导 教 师 : 黄大荣
2015年4月
教师评阅意见: 签名: 年 月 日 实验成绩: 霍夫曼编码的matlab实现
一、实验目的和要求。
利用哈夫曼编码进行通信可以大大提高信道的利用率,缩短信息传输的时间,降低传输成本。
本实验用Matlab语言编程实现霍夫曼(Huffman)编码。
二、实验原理。
霍夫曼(Huffman)编码算法是满足前缀条件的平均二进制码长最短的编-源输出符号,而将较短的编码码字分配给较大概率的信源输出。算法是:在信源符号集合中,首先将两个最小概率的信源输出合并为新的输出,其概率是两个相应输出符号概率之和。这一过程重复下去,直到只剩下一个合并输出为止,这个最后的合并输出符号的概率为1。这样就得到了一张树图,从树根开始,将编码符号1 和0 分配在同一节点的任意两分支上,这一分配过程重复直到树叶。从树根到树叶途经支路上的编码最后就构成了一组异前置码,就是霍夫曼编码输出。 离散无记忆信源: 例如
U u1 u2 u3 u4 u5
P(U) = 0.4 0.2 0.2 0.1 0.1
码字Wi 信符si 概率 P(si) 第一次 编码过程 第二次 第三次 1 W1=0 W2=10 W3=111 W4=1101 W5=1100 S1 S2 S3 S4 S5 0.4 0.2 0.2 0.1 0.1 0.4 0.2 0.2 1 1 0.4 0.4 0.2 0 0.6 1 A(1) 0 0.4 0 0.2 0 通过上表的对信源缩减合并过程,从而完成了对信源的霍夫曼编码。
三、实验步骤
分为两步,首先是码树形成过程:对信源概率进行合并形成编码码树。然后是码树回溯过程:在码树上分配编码码字并最终得到霍夫曼编码。
1、码树形成过程:将信源概率按照从小到大顺序排序并建立相应的位置索引。然后按上述规则进行信源合并,再对信源进行排序并建立新的位置索引,直到合并结束。在这一过程中每一次都把排序后的信源概率存入矩阵G中,位置索引存入矩阵Index中。这样,由排序之后的概率矩阵 G以及索引矩阵Index就可以恢复原概率矩阵P了,从而保证了回溯过程能够进行下去。
2、码树回溯过程:在码树上分配编码码字并最终得到Huffman 编码。从索引矩阵M 的末行开始回溯。
(1) 在Index 的末行2元素位置填入0和1。
(2) 根据该行索引1 位置指示,将索引1 位置的编码(‘1’)填入上一行的第一、第二元素位置,并在它们之后分别添加‘0’和‘1’。
(3) 将索引不为‘1’的位置的编码值(‘0’)填入上一行的相应位置(第3 列)。
(4) 以Index的倒数第二行开始向上,重复步骤(1) ~ (3),直到计算至Index的首行为止。
四、程序代码:
%取得信源概率矩阵,并进行合法性判断 clear;
P=input('请输入信源概率向量P='); N=length(P);
for component=1:1:N