哈夫曼编码及Matlab实现

更新时间:2023-10-25 18:50:01 阅读量: 综合文库 文档下载

说明:文章内容仅供预览,部分内容可能不全。下载后的文档,内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的,是否完整无缺。

哈夫曼编码及Matlab实现

哈夫曼编码是一种所得码字是异前置的变长码,其平均码长最短,被称为最佳变长码,也称为哈夫曼编码。 其具体编码方法如下:

(1)将信源信息(符号)按概率大小排队;

(2)从最小概率的两个消息开始编码,并给予一定的编码规则,如小概率的下支路编为1(或0),大概率的上支路变为0(或1),若两者概率相等,仍是下支路为1上支路为0;

(3)将已经编码的两个消息对应概率合并,并重新按概率大小排队,重复步骤(2);

(4)重复步骤(3),直至合并概率归一为止;

(5)变成的变长码是按后出先编方式,即从概率归一的树根沿编码路线逆行至对应的消息。

实验内容:

给定离散信源:

u2u3u4u5u6u7??U??u1??p??0.200.190.180.170.150.100.01? ????对其进行哈夫曼编码,其理论结果如下: 消息 (U) 概率 (p) 0.20 0.19 0.18 0.17 0.15 0.10 0.01

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 编码 (C) 10 11 000 001 010 0110 0111 u1 u2 u3 u4 u5 u6 u7 哈夫曼编码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;%求得编码效率运行结果:

该结果与理论结果相符,满足实验要求。

本文来源:https://www.bwwdw.com/article/8h02.html

微信扫码分享

《哈夫曼编码及Matlab实现.doc》
将本文的Word文档下载到电脑,方便收藏和打印
推荐度:
点击下载文档
下载全文
范文搜索
下载文档
Top