基于MATLAB的霍夫曼编码仿真
目录
0 前言.......................................................................................... 错误！未定义书签。 1 信源编码的基本概念.............................................................. 错误！未定义书签。
1.1 通信系统的模块仿真....................................................... 错误！未定义书签。
1.2 信息的度量与编码........................................................... 错误！未定义书签。
1.3 无失真编码算法............................................................... 错误！未定义书签。
2 信源最佳化................................................................................................................ 6 3 霍夫曼编码特点及应用.......................................................... 错误！未定义书签。
4 编码规则.................................................................................................................... 7
4.1 二元霍夫曼编码规则......................................................................................... 7
4.2 多元霍夫曼编码规则......................................................................................... 8
4.3 扩展信源霍夫曼编码......................................................................................... 8
5 MATLAB性能仿真 ................................................................................................... 8
5.1 二元霍夫曼编码仿真......................................................................................... 9
5.2 三元霍夫曼编码仿真....................................................................................... 11
5.3 扩展信源编码仿真........................................................................................... 13 6 结论.......................................................................................... 错误！未定义书签。 参考文献...................................................................................... 错误！未定义书签。
基于MATLAB的霍夫曼编码仿真
李长江
（河南大学物民生学院，河南 开封，475004）
摘 要：
通信的数字化是它能与计算机技术和数字信号处理技术相结合的基础，而实现通信数字
化的前提是信源能提供的各种用于传递的消息，例如语音、图像、数据、文字等都必须以数字化形式表示。而信源编码是数字通信系统中的重要组成部分，他是保证信号有效传输的一种重要方式。霍夫曼编码依据字符出现的概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，其优越的性能被广泛使用在数字通信系统中。霍夫曼编码已经成为数据压缩的灵魂算法。本文介绍了无失真编码算法的构造，霍夫曼编码的规则和特点，同时分析了对信源进行优化的方法，最后通过MATLAB仿真来讨论比较二元霍夫曼编码、三元霍夫曼编码以及信源扩展编码的效率，来实现霍夫曼码的优化构造。
关键词：
Matlab，霍夫曼编码，仿真,二元霍夫曼编码，三元霍夫曼编码，扩展信源编码
Huffman Codes And Matlab Simulation
Li changjiang
(School of min sheng, Henan University, Henan Kaifeng 475004, China)
Abstract:
Digital communication is the basis which can combine computer technology
and digital signal processing technology.But the premise for digital communication is that the source can provide a variety of message for transmission.For example voice,images,data,text.And the messages can be expressed in digital form.Source coding is the important part in the digital communication system.It is also a way to ensure the effectiveness of the transmission in this system.Huffman coding based on the probability to construct a character different prefix length of the shortest average code word .Sometimes it is called the optimal coding. Huffman code is widely used in the digital communication system by the ascendant performance .Huffman coding has become data compression soul algorithm.This article describes the construction of lossless coding algorithm .It also introduces the rules and the characteristics of Huffman coding.It also analyzes the method of source optimization.Finally,we discuss
the comparison of binary Huffman coding,ternary Huffman coding and extended source coding based on MATLAB.We are thus to achieve optimal Huffman code constructed.
Key words:
MATLAB； huffman code； binary Huffman coding; ternary Huffman
coding ; extended source coding
0 前言 在通信的数字化过程中，对于时间连续和取值连续的原始语音和图像等模拟
信号来说，如果要以数字方式进行传输，在发送端必须首先进行模/数(A/D)变换，将原始信号转换为时间离散和取值离散的数字信号。
模拟信号数字化之后一般会导致传输信号的带宽明显增加，这样就会占用更
多的信道资源，使得传输效率降低，或者无法实现实时传输。为了提高传输效率，一方面需要采用压缩编码技术，在保证一定信号质量的前提下，尽可能地去除信号中的冗余信息，从而减少信号速率和传输所用带宽。另一方面，即使是原本就以数字形式存在的数据和文字信息，也同样存在一个需要通过压缩编码降低信息冗余提高传输效率的问题。由于这些处理都是针对信源发送信息所进行的，因此一般将其称为信源编码。
信源编码的基本目的是提高码字序列中码元的平均信息量，那么，一切旨在
减少剩余度而对信源输出符号序列所施行的变换或处理，都可以在这种意义下归入信源编码的范畴，例如过滤、预测、域变换和数据压缩等。作为现代数据无损压缩的灵魂算法，霍夫曼编码正广泛应用于各种图像、音频、视频及各种多媒体信息的压缩环境中。
1 信源编码的基本概念
1.1 通信系统的模块仿真
噪声
1.2 信息的度量与编码
信息是指消息中包含的有效内容，度量信息量的原则首先是能度量任何消息
并与消息的种类无关，其次度量方法应该与消息的重要程度无关，最后消息中所含信息量和消息内容的不确定性有关。
信息熵的输出可以用随机过程来描述。对于一个离散无记忆平稳随机过程，
其信息量（熵）定义为：
H(X)px()lopgx(
xX
其中X表示信源取值集合，p(x)是信源取值x的概率。 MATLAB信源编译码方法
大多数信源（比如语音、图像）最开始都是模拟信号，为了将信源输出数字
化，信源必须量化为确定数目的级数。量化方案可划分为标量量化和矢量量化两种。在标量量化中每个信源输出都分别被量化，标量量化可进一步分为均匀量化和非均匀量化。在均匀量化中量化区域是等长的；在非均匀量化中量化区域可以是不等长的。矢量量化是对信源输出组合进行整体量化。
在标量量化中，随机标量X的定义域被划分成N个互不重叠的区域Ri，
1≤ i≤
这就意味着：
xRiQ(x)xi
易见，这类量化引入了失真，其均方误差为：
Nxi来表示，
i1Ri
其中f(x)是信源随机变量的概率密度函数。信号量化噪声比(SQNR)为： D(xxi)2fx(x)dx
E[X2]SQNR10log10D
信源编码是数字通信中的重要环节，它的主要目的是减少冗余，提高编码效
率。信源编码可分为两类：无失真编码和有失真编码。无失真编码只对信源冗余度进行压缩，不会改变信源的熵，又称冗余度压缩编码，它能保证码元序列经译码后能无失真的恢复成信源符号序列，如霍夫曼编码，香农编码。有失真编码在允许的失真范围内把编码后的信息率压缩到最小，有失真信源编码的失真范围受限，所以又称为限失真信源编码。
信源编码就是把信源符号序列变换到码符号序列的一种映射。若要实现无失
真编码，那么这种映射必须是一一对应的、可逆的。一般来说，人们总希望把信源所有的信息毫无保留的传递到接受端，即实现无失真传输，所以首先要对信源实现无失真编码。
信源编码有以下三种主要方法：
（1）匹配编码
根据信源符号的概率不同，编码的码长不同,这样使平均码长最短。将要讲到的霍夫曼编码就是概率匹配编码。
（2）变换编码
先对信号进行变换，从一种信号空间变换为另一种信号空间，然后针对变换后的信号进行编码。一般是把分布在时空域的信号（如时域的语音信号和平面空间的图像信号）映射到变换域（如频域的频谱信号和其他正交矢量空间域），原来相关性很强的原始信号经过变换后，得到的变换域系数相互独立，并且能量集中在少数低序系数上，这样只需对少量的变换域的系数进行编码，达到数据压缩的目的。常用的变换编码有DFT、沃尔什变换、小波变换等。
(3)识别编码
识别编码主要用于印刷或打字机等有标准形状的文字、符号和数据的编码，比如中文文字和语音的识别。
后两种信源编码均为有失真的信源编码。
最原始的信源编码就是莫尔斯电码，另外还有ASCII码和电报码都是信源编码。但现代通信应用中常见的信源编码方式有：霍夫曼编码、算术编码、L-Z编码，这三种都是无损编码。而霍夫曼编码作为变长码满足变长信源编码定理。该编码定理是香农信息论中非常重要的一个定理，它指出，要做到无失真的信源编码，信源每个符号所需要的平均码元数就是信源的熵值，如果小于这个值，则唯一可译码不存在，可见，熵是无失真信源编码的极限值。定理还指出，通过对扩展信源进行编码，当N趋向于无穷时，平均码长可以趋进该极限值。还可以证明，如果我们不确切知道信源的概率分布，我们用估计的概率分布去进行编码时，平均码长会加长，但是如果估计的偏差不大的话，平均码长也不会增加太多。
1.3 无失真编码算法
编码器：编码器可以看作这样一个系统，它的输入端为原始信源S，其符号集为S,而信道所能传输的符号集为X，编码器的功能是用符号集X中的元素，将原始信源的符号Si变换为相应的码字符号Wi,编码器输出端得符号集为C。
C
奇异码与非奇异码
若一种分组码中所有码字都不相等，则称分组码为非奇异码，否则为奇异码。 唯一可译码与非唯一可译码
任意有限长码元序列，如果只能唯一分割成一个个码字便称为唯一可译码。 唯一可译码得物理意义是指不仅要求不同的码字表示不同的信源符号，而且还要求对由信源符号构成的符号序列进行编码时，在接受端仍能正确译码而不发生混淆。唯一可译码首先是非奇异码且任意有限长的码字序列不会雷同。
即时码与非即时码
无需考虑后续的码符号就可以从码符号序列中译出码字，这样的唯一可译码
称为即时码
变长码及变长编码定理
信源符号数、码符号数、码字长度之间满足什么条件才可以构成即时码和唯一可译码呢？Kraft不等式和McMillan不等式回答了这个问题。这两个不等式在形式上是完全一样的。
设信源符号集为Ss1,s2,...,sq，码符号集为Xx1,x2,...,xr，对信源进行
编码，得到的码为Cw1,w2,...,wq，码长分别为l1,l2,...,lq。即时码存在的充要
条件是：
ri1qli1
这称为Kraft不等式。
由上式可知，给定r和q，只要允许码字长度可以足够长，则码长总可以满足Kraft不等式而得到即时码，Kraft不等式指出了即时码的码长必须满足的条件。后来McMillan证明对于唯一可译码得码长也必须满足此不等式。在码长的选择上唯一可译码并不比即时码有更宽松的条件。对于唯一可译码，该不等式又称为McMillan不等式。
唯一可译码存在的充要条件是：
ri1qli1
其中r为码符号个数，li为码字长度，q为信源符号个数
无失真变长信源编码定理
NNH(S)，并且编码器的码元S离散无记忆信源S的N次扩展信源，其熵为
符号集为A：a,a,...,a对信源S12qN进行编码，总可以找到一种编码方法，构成
s唯一可译码，使信源S中每个符号i所需要的平均码长满足
一个横放的码树。其次，其编码的平均码长最小，霍夫曼编码采用概率匹配的方法来决定各码字的码长，概率大的符号对应于短码，概率小的符号对应于长码。最后，霍夫曼编码的码字并不唯一，每次对概率最小的两个符号求概率之和形成缩减信源时，就构造出两个树枝，由于对两个树枝附码元时是任意的，所以码字不唯一。另外在霍夫曼编码过程中，对缩减信源符号按概率由大到小的顺序排列时应使合并后的新符号尽可能的排在靠前的位置，这样可使合并后的新符号重新编码次数减少，使短码得到充分利用。
在实际应用中，首先每个信源符号所对应的码长不同，一般情况下，信源符号以匀速输出，信道也是匀速传输的。通过霍夫曼编码后，会造成编码输出的信息速率不是常量，因而不能直接由信道来传送。为了适应信道，必须增加缓冲寄存器，将编码输出暂存在缓冲器中，然后再匀速向信道输出。但当缓冲器容量有限时，会出现缓冲器溢出或取空的现象。所以一般变长码只适用于有限长的信息传输，或者在输出一批消息后能暂停一下。
其次，差错扩散的问题。变长码得一个的差错可能造成译码错误，并且还会造成同步错误，结果后面一系列码字也会译错。 最后，霍夫曼码的编译码需要用查表的方法来进行。在信息传输过程中必须先存储与传输这一霍夫曼编码表。这会影响信息的传输效率，特别是当N增大时，所需存储的码表也增大，使得设备复杂化，且查表搜索的开销增大。我们还须根据信源的统计特性，事先建立霍夫曼编码表，因此这种方法只适用于已知其统计特性的信源。
尽管如此，霍夫曼方法还是一种有效的无失真信源编码方法，它便于硬件实现和计算机上的软件实现，适用于文件传真、语音处理和图像处理的数据压缩。
在新世纪，广播电视数字化兴起，有线电视、卫星电视和地面无线广播电视的数字化都发展很快，有线数字电视的另一个发展趋势是利用IP技术的IPTV，数字电视地面无线广播技术新的应用领域是手机电视。我国数字电视地面无线广播系统技术研究较早，提出了多种方案，其中采用伪随机序列（PN）的时域同步频域处理技术等构成了基础性发明专利，所实现的性能优于按照ITU已有的三项国际标准实现的系统。不仅在信道处理技术上而且在信源编码技术上我国也有可喜的创新，我国发布了AVS音视频编码标准，它的压缩效率与国际标准MPEG4/AVC相当，但复杂度低，AVS的部分技术已被吸纳进相应的国际标准。
4 编码规则
4.1 二元霍夫曼编码规则
（1）将信源符号按概率从大到小的顺序排列。
（2）给两个概率最小的信源符号各分配一个码位“0”和“1”，将两个信源符号合并成一个新符号，并用这两个最小的概率之和作为新符号的概率，结果得到一个只包含（n-1）个信源符号的新信源。称为信源的第一次缩减信源，用s1表示。
（3）将缩减信源s1的符号仍按概率从大到小顺序排列，重复步骤二，得到只含（n-2）个符号的缩减信源s2。
（4）重复上述步骤，直至缩减信源只剩两个符号为止，此时所剩两个符号的概率之和必为1，然后从最后一级缩减信源开始，依编码路径向前返回，就得到各信源符号所对应的码字。
4.2 多元霍夫曼编码规则
由二进制霍夫曼编码的方法很容易推广到r进制的情况，只是编码的过程中构成缩减信源时，每次都是将r个概率最小的信源符号合并，然后分别用码符号 0,1，...,(r-1)表示。
为了充分利用短码，使霍夫曼码的平均码长最短，必须使最后一个缩减信源恰好有r个信源符号，因此对于r元霍夫曼码，信源S符号个数q必须满足
q(r1)r
其中表示信源缩减次数。如果不满足上式，则可以在最后增补一些概率为零的信源符号，因此上式又可以写成
qi(r1)r
i为增加的信源符号数，并且是满足上式的最小正整数或0。这样处理后得到的r元霍夫曼码可充分利用短码，一定是紧致码。
4.3 扩展信源霍夫曼编码
对离散无记忆信源的N次扩展信源进行编码便得到N次扩展码。
采用霍夫曼编码法能够使码的平均长度最短，信息的冗余量最小。然而这种编码方法所形成的码字很不规整，这样不利于硬件的译码。在很多处理机中，我们采用一种新的折中的方法，称为扩展编码法。这种方法是由定长编码与霍夫曼编码法相结合形成的。有等长扩展法和不等长扩展编码方法，为了便于实现分级译码，我们一般采用等长扩展编码法，当然，也可以根据具体需要采用每次扩展位数不等的不等长扩展法。
5 MATLAB性能仿真
Problem 1:
对信源S编码，其中
p(s1)0.4,p(s2)0.2,p(s3)0.2,p(s4)0.1,p(s5)0.1;
现对该离散无记忆平稳信源进行霍夫曼编码。
对应霍夫曼编码求熵仿真如下:
function h=entropy(p)
%H=ENTROPY(P) returns the entropy function of
%the probability vector p.
p=[0.4,0.2,0.2,0.1,0.1],
if length(find(p
error('Not a prob. vector, negative component(s)')
end
if abs(sum(p)-1)>10e-10,
error('Not a prob. vector, components do not add up to 1')
end
h=sum(-p.*log2(p));
程序运行结果显示：
p =
0.4000 0.2000 0.2000 0.1000 0.1000
ans =
2.1219
5.1 二元霍夫曼编码仿真
(1) 对problem 1进行二元霍夫曼编码程序如下:
function [h,l]=huffmancode(P)
P=input('输入概率:');
n=length(P);
for i=1:n-1
for j=i+1:n
if P(i)
p=P(i);
P(i)=P(j);
P(j)=p;
end
end
end
disp('概率分布');
Q=P;
m=zeros(n-1,n);
for i=1:n-1
[Q,b]=sort(Q);%sort函数是对Q进行升序排列，返回值l显示排序后位置的变动信息
m(i,:)=[b(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);%blanks是空格函数 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';
c(n-i,n+1:2*n-1)=c(n-i,1:n-1); c(n-i,2*n)='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);%平均码长 h1=-log2(P);%自信息量 H=P*(h1');%熵 H
disp('二元霍夫曼编码平均码长') l
disp('编码效率') G=H/l
disp('二元霍夫曼编码') (2）运行结果为：
输入概率:[0.4,0.2,0.2,0.1,0.1] 概率分布 H =
2.1219
二元霍夫曼编码平均码长 l =
2.2000 编码效率
G =
0.9645
二元霍夫曼编码 ans = 1 000 01 0011 0010
5.2 三元霍夫曼编码仿真
(1)对problem 1进行三元霍夫曼编码程序如下: function [h,l]=huffman(p);
%HUFFMAN Huffman code generator
% [h,l]=huffman(p), Huffman code generator % returns h the Huffman code matrix, and l the % average codeword length for a source with % probability vector p. S=input('输入概率:'); n=length(S); for i=1:n-1
for j=i+1:n
if S(i)
disp('概率分布'); S p=S;
N=length(p); r=3;
q=[p(1:N),zeros(1,ceil((N-r)/(r-1))*(r-1)+r-N)];
n=length(q);
A=(n-r)/(r-1)+1; m=zeros(A,n); for i=1:A
[q,l]=sort(q);
m(i,:)=[l(1:n-2*(i-1)),zeros(1,2*(i-1))];
q=[sum(q(1:r)),q(r+1:n),ones(1,r-1)]; end
for i=1:A
c(i,:)=blanks(n*n); end
c(A,n)='0'; c(A,2*n)='1'; c(A,3*n)='2'; for i=1:(A-1)
c(A-i,1:n-1)=c(A-i+1,n*(find(m(A-i+1,:)==1))... -(n-2):n*(find(m(A-i+1,:)==1))); c(A-i,n)='0';
c(A-i,n+1:2*n-1)=c(A-i,1:n-1); c(A-i,2*n)='1';
c(A-i,2*n+1:3*n-1)=c(A-i,1:n-1); c(A-i,3*n)='2';
for j=1:2*i
c(A-i,(j+2)*n+1:(j+3)*n)=c(A-i+1,n*(find(m(A-i+1,:)... ==j+1)-1)+1:n*find(m(A-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
H=-sum(p.*log2(p)); l=sum(p.*ll); H
disp('三元霍夫曼编码平均码长') l
disp('编码效率') G=H/(l*log2(r))
disp('三元霍夫曼编码') (2)运行结果为：
输入概率:[0.4,0.2,0.2,0.1,0.1] H =
2.1219
三元霍夫曼编码平均码长 l =
1.4000 编码效率 G =
0.9563
三元霍夫曼编码 ans = 2 12 0 10 11
5.3 扩展信源编码仿真
(1)对problem 1进行扩展后霍夫曼编码程序如下:
function [h,l]=huffman(p);
%HUFFMAN Huffman code generator
% [h,l]=huffman(p), Huffman code generator % returns h the Huffman code matrix, and l the % average codeword length for a source with % probability vector p. disp('概率分布为')
a=[0.4,0.2,0.2,0.1,0.1], H=sum(-a.*log2(a));
A = 0.16; B = 0.08; C = 0.08; D = 0.04; E = 0.04; F = 0.08; G = 0.04; Z = 0.04; I = 0.02; J = 0.02; K = 0.08; L = 0.04; M = 0.04; N = 0.02; O = 0.02; P = 0.04; Q = 0.02; R = 0.02; S = 0.01; T = 0.01; U = 0.04; V = 0.02; W = 0.02; X = 0.01; Y = 0.01;
p = [A B C D E F G Z I J K L M N O P Q R S T U V W X Y]; 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)='0'; c(n-1,2*n)='1';
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)='0';
c(n-i,n+1:2*n-1)=c(n-i,1:n-1); c(n-i,2*n)='1'; 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); l1(i)=length(find(abs(h(i,:))~=32)); end
l=sum(p.*l1); disp('信源熵') H
disp('扩展信源平均码长') l
disp('扩展信源编码效率') G=2*H/l
disp('扩展信源编码') （2）运行结果为： a =
0.4000 0.2000 0.2000 0.1000 0.1000 信源熵 H = 2.1219 扩展信源平均码长 l = 4.3200 扩展信源编码效率 G = 0.9824 扩展信源编码 ans =
00 1111 1100 10001 10110 1101 10111 10100 100110 100111 010 10101 01110 100100 100101 01111 111010 111011 1000010 1000011 0110 111000 111001 1000000 1000001
6 结论
通过以上编码仿真得到的结果我们可以对性能做如下总结，
通过对信源编码的分析与仿真，我们对通信系统模块发送端有了一定的认识，可以在发送端利用各种编码方式进行压缩处理，并增进了对霍夫曼编码的理解，更重要的是学会了使用matlab作为学习工具对我们的通信系统进行设计和仿真等操作，这对我们以后的学习和工作有着重要意义。
参考文献
[1] Bernard Sklar,徐平平，宋铁成，等．数字通信基础与应用[M]．北京：电子工
业出版社，2000．465-521
[2] 樊昌信.通信原理(第6版).北京：国防工业出版社，2007.349-360 [3] 吴伟陵．信息处理与编码[M]．北京：人民邮电出版社，2000．269-283 [4] 邓华等．MATLAB通信仿真及应用实例[M]．北京：人民邮电出版社，
2003．202-211，279-382
[5] 周炯槃，庞沁华，续大我，吴伟陵，杨鸿文—通信原理[M]．北京：北京邮电大学 出版社，2005．419-434
[6] 邵佳，董辰辉.MATLAB/Simulink通信系统建模与仿真实例精讲[M]．北京：电子工业出版社，2009.301-311
[7] 李子臣.信息论与编码[M]．北京：中国矿业大学出版社，2006.262-285 [8] 张贤达，通信信号处理 北京：国防工业出版社 2000
[9] 徐明远，邵玉斌.MATLAB仿真在通信与电子中的应用.西安：西安电子科技大学出版社 2005.6-1
[10] 李霞.电子与通信专业英语.电子工业出版社，2005