哈夫曼编码及Matlab实现
- 格式：doc
- 大小：51.50 KB
- 文档页数：5
哈夫曼编码及Matlab实现
哈夫曼编码是一种所得码字是异前置的变长码，其平均码长最短，被称为最佳变长码，也称为哈夫曼编码。
其具体编码方法如下：
（1）将信源信息（符号）按概率大小排队；
（2）从最小概率的两个消息开始编码，并给予一定的编码规则，如小概率的下支路编为1（或0），大概率的上支路变为0（或1），若两者概率相等，仍是下支路为1上支路为0；
（3）将已经编码的两个消息对应概率合并，并重新按概率大小排队，重复步骤（2）；
（4）重复步骤（3），直至合并概率归一为止；
（5）变成的变长码是按后出先编方式，即从概率归一的树根沿编码路线逆行至对应的消息。
实验内容：
给定离散信源：
01.010.015.017.018.019.020.07654321uuuuuuupU
对其进行哈夫曼编码，其理论结果如下：
消息 （U） 概率 (p)
编码 （C）
1u 0.20
0.20
0.26
0.35
0.39
0.61
1.0
0.19
0.20
0.26
0.35
0.39
0.18
0.19
0.20
0.26
0.17
0.18
0.19
0.15
0.17
0.11 10
2u 0.19 11
3u 0.18 000
4u 0.17 001 5u 0.15 010
6u 0.10 0110
7u 0.01 0111
哈夫曼编码Matlab代码：
p=[0.2,0.19,0.18,0.17,0.15,0.1,0.01];
p=sort(p,'descend');%降序排列
H=sum(-p.*log2(p));%求得信息熵
n=length(p);%离散信源长度
q=p;
m=zeros(n-1,n);
for i=1:n-1%对第一行进行编码
[q,l]=sort(q);
m(i,:)=[l(1:n-i+1),zeros(1,i-1)];
q=[q(1)+q(2),q(3:n),1];
end
for i=1:n-1
c(i,:)=blanks(n*n);
end
c(n-1,n)='1';
c(n-1,2*n)='0';
for i=2:n-1
c(n-i,1:n-1)=c(n-i+1,n*(find(m(n-i+1,:)==1))...
-(n-2):n*(find(m(n-i+1,:)==1)));
c(n-i,n)='1';%在支路的第一个元素最后补1
c(n-i,n+1:2*n-1)=c(n-i,1:n-1);
c(n-i,2*n)='0';%在支路的第一个元素最后补0 for j=1:i-1
c(n-i,(j+1)*n+1:(j+2)*n)=c(n-i+1,...
n*(find(m(n-i+1,:)==j+1)-1)+1:n*find(m(n-i+1,:)==j+1));%分配码字
end
end
for i=1:n
h(i,1:n)=c(1,n*(find(m(1,:)==i)-1)+1:find(m(1,:)==i)*n);
ll(i)=length(find(abs(h(i,:))~=32));%计算每一个哈夫曼编码的长度
end
L=sum(p.*ll);%求得平均码长
t=H/L;%求得编码效率运行结果：
该结果与理论结果相符，满足实验要求。
