哈弗曼编码报告.doc

哈弗曼编码报告.doc河南师范大学
实验课程名称：信息论编码
主教老师：刘艳芳
实验项目名称：哈弗曼编码
学院：计算机与信息工程学院
专业：网络工程
学生姓名：陈微
学号：1208324070
一、实验目的
理解信源编码的意义
熟悉MATLAB程序设计
掌握哈夫曼编码的方法及计算机实现
对给定信源进行香农编码，并计算编码效率
二、实验原理
编码方法：
（1）将q个信源符号按概率大小递减排列p（sj > ph?） > • •• > p（s‘J ；
C2）用“0, 1”码符号分别代表概率最小的两个信源符号，并将这两个概 率最小的信源符号合并成一个，从而得到只包含q-1个符号的新信源，称为缩减 信源S］；
C3）把缩减信源,的符号仍按概率大小递减次序排列，再将其最后两个概 率最小的信源符号分别用“0”和“1”码符号表示，并且合并成一个符号，这样 又形成了 q-2个信源符号的缩减信源S］；
（4）依次继续下去，直至信源最后只剩下两个信源符号为止，将这最后两 个信源符号分别用二元码符号“0”和“1”表示；
C5）然后从最后一级缩减信源开始，进行回溯，就得到各信源符号所对应 的码符号序列，即相应的码字。
注意：可先生成编码表











0


0
0

2
2
2
编码表每列为缩减信源概率： 第一列为输入n个信源概率；
第二列为第一次缩减后t=n-l个概率；第（n, 2）元素放置合并元素在本列中位 置；
如果输入n个概率，则需要缩减n-l次后，剩下t=2两个概率；
所以编码表可以定义为n行n-l列。
编码表生成后，从最后一列开始编码。
首先最后一列两个元素分别编码为0和1;
对其中某j列，其前t-2个元素编码为J+1列非合并概率移植过来。（问题，如何 知道j+1列中非合并元素的位置？）
第t-1元素和第t个元素为j+1列合并概率编码分别加0和加E （合并概率的 位置已经在本列最后一个元素中标出）
三、 实验设备
一台计算机、编程软件MATLAB7. 0. 1
四、 实验内容与步骤
对如下信源进行哈夫曼编码，并计算编码效率。
X % a2 a3 们 a5
P \ ~ ［OA
（1） 计算该信源的信源爛，并对信源概率进行排序。
（2） 首先将出现概率最小的两个符号的概率相加合成一个概率，把这个合 成概率与其他的概率进行组合，得到一个新的概率组合，重复上述做法，直到 只剩下两个概率为止。之后再反过来逐步向前进行编码，每一次有两个分支 各赋予一个二进制码。对大 的概率赋“1”，小的概率赋“0”。
（3） 从最后一级开始，向前返回得到各个信源符号所对应的码元序列，即 相应的码字。
（4） 计算码字的平均码长得出最后的编码效率。
五、 实验数据（源代码）
p=[0. 2 0. 1 0. 2 0. 1 ]; n=length(p);
pl=fliplr(sort(p));
M二zeros (n, n~l);
M(:,l)二 pl;
m二M(n, 1) +M(nT, 1);
pl (nT)二m;
pl(n)-0;
pl=fl