信息论基础实验.doc

霍夫曼编码
实验目的
本实验运用MATLAB编程实现对不同长度、不同概率分布的消息进行霍夫曼编码。
实验步骤
霍夫曼编码的具体方法如下:
输入各个给定消息的概率;
将消息按降序排列,取最后两个值之和,将其中一个编码为1,另一个编码为0,而所加概率之和当作一个新消息替代原来两个消息;
继续降序排列消息列,去最后两个概率值之和,同样一个编码1,另一个为0;
将该二元数字序列反向排列就是最佳的二元非续长代码。
现将编码实例图如下图反应:
A
B
C
D
E
F






0
1

0
1

1
0

1
0

0
1
1
其中,红色框内是概率。
跟据图中编码结果:
信息名
A
B
C
D
E
F
编码
11
01
00
101
1000
1001
针对霍夫曼编码方法,实际设计程序时进行如下调整:
Step 1. 输入各消息对应的概率(即分布列),进行数据的预处理,包括降序排列,获取消息的个数,初始化所要用到的累加概率。
Step 2. 计算累加概率,即将降序排列的分布列逐个累加,具体关系如下表:
表-1
分布列
p(1)
p(2)
p(3)
…
p(n-1)
p(n)
累加概率
0
p(1)
p(1)+p(2)
…
p(1)+…+ p(n-2)
p(1)+…+ p(n-1)
Step 3. 计算码长,并将分布列中的概率转化为二进制的数列。
Step 4. 调整码长,将得到的二进制数列截取适当的位数以构成最终的编码。
Step 5. 找出降序排列后的数组与输入数组的对应关系,调整编码结果的顺序,以匹配输入时的概率顺序
Step 6. 显示最终的编码结果
实验程序
clc,clear
%
% 用户在此处输入各消息对应的分布列,输入的顺序与概率个数随意。
array=[ ];
input_tmp=array;
input_tmp=sort(input_tmp,2,'descend'); % 降序排列
len=length(input_tmp); % 获取概率(消息)的个数
p_add=zeros(1,len); % 初始化数组,用来保存累加概率
%
i=1;
while i<=len
j=1;
while j<=i-1
p_add(1,i)=p_add(1,i)+input_tmp(1,j);
j=j+1;
end
i=i+1;
end
% ,但还需截取位数再调整。
code_len=ceil(-log2(input_tmp)); % 求码长
c=cell(1,len); % 定义用来保存初步结果的元胞数组,临时变量。
% 将小数转换为二进制
i=1;
while i<=len
N=code_len(i);
count=0;
tnum=p_add(i);
record=zeros(1,N);
while(N)
count=count+1; %