基于MATLAB的霍夫曼编码仿真

1、目录0 前言21 信源编码的基本概念2 1.1 通信系统的模块仿真2 1.2 信息的度量与编码3 1.3 无失真编码算法42 信源最佳化63 霍夫曼编码特点及应用64 编码规则7 4.1 二元霍夫曼编码规则7 4.2 多元霍夫曼编码规则8 4.3 扩展信源霍夫曼编码85 MATLAB性能仿真8 5.1 二元霍夫曼编码仿真9 5.2 三元霍夫曼编码仿真11 5.3 扩展信源编码仿真136 结论15参考文献16基于MATLAB的霍夫曼编码仿真李长江（河南大学物民生学院，河南 开封，）摘 要： 通信的数字化是它能与计算机技术和数字信号处理技术相结合的基础，而实现通信数字化的前提是信源能提供的各种用于

2、传递的消息，例如语音、图像、数据、文字等都必须以数字化形式表示。而信源编码是数字通信系统中的重要组成部分，他是保证信号有效传输的一种重要方式。霍夫曼编码依据字符出现的概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，其优越的性能被广泛使用在数字通信系统中。霍夫曼编码已经成为数据压缩的灵魂算法。本文介绍了无失真编码算法的构造，霍夫曼编码的规则和特点，同时分析了对信源进行优化的方法，最后通过MATLAB仿真来讨论比较二元霍夫曼编码、三元霍夫曼编码以及信源扩展编码的效率，来实现霍夫曼码的优化构造。关键词： Matlab，霍夫曼编码，仿真,二元霍夫曼编码，三元霍夫曼编码，扩展信源编码Huffm

3、an Codes And Matlab SimulationLi changjiang(School of min sheng, Henan University, Henan Kaifeng , 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 provid

4、e 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

5、 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

6、 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 bas

7、ed 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)变换，将原始信号转换为时间离散和取值离散的数字信号。模拟信号数字化之后一般会导致传输信号的带宽明显增加，这样

8、就会占用更多的信道资源，使得传输效率降低，或者无法实现实时传输。为了提高传输效率，一方面需要采用压缩编码技术，在保证一定信号质量的前提下，尽可能地去除信号中的冗余信息，从而减少信号速率和传输所用带宽。另一方面，即使是原本就以数字形式存在的数据和文字信息，也同样存在一个需要通过压缩编码降低信息冗余提高传输效率的问题。由于这些处理都是针对信源发送信息所进行的，因此一般将其称为信源编码。信源编码的基本目的是提高码字序列中码元的平均信息量，那么，一切旨在减少剩余度而对信源输出符号序列所施行的变换或处理，都可以在这种意义下归入信源编码的范畴，例如过滤、预测、域变换和数据压缩等。作为现代数据无损压缩的灵魂

9、算法，霍夫曼编码正广泛应用于各种图像、音频、视频及各种多媒体信息的压缩环境中。1 信源编码的基本概念1.1 通信系统的模块仿真信道译码信宿信源译码信道信道编码信源编码信源 噪声1.2 信息的度量与编码信息是指消息中包含的有效内容，度量信息量的原则首先是能度量任何消息并与消息的种类无关，其次度量方法应该与消息的重要程度无关，最后消息中所含信息量和消息内容的不确定性有关。信息熵的输出可以用随机过程来描述。对于一个离散无记忆平稳随机过程，其信息量（熵）定义为： 其中X表示信源取值集合，p(x)是信源取值x的概率。 MATLAB信源编译码方法 大多数信源（比如语音、图像）最开始都是模拟信号，为了将信源

10、输出数字化，信源必须量化为确定数目的级数。量化方案可划分为标量量化和矢量量化两种。在标量量化中每个信源输出都分别被量化，标量量化可进一步分为均匀量化和非均匀量化。在均匀量化中量化区域是等长的；在非均匀量化中量化区域可以是不等长的。矢量量化是对信源输出组合进行整体量化。 在标量量化中，随机标量X的定义域被划分成N个互不重叠的区域Ri，1 iN , Ri被称为量化间隔，且在每个区域内选择一个点作量化级数。这样落在区域Ri内的随机变量的所有值都被量化为第i个量化级数，用来表示，这就意味着： 易见，这类量化引入了失真，其均方误差为： 其中f(x)是信源随机变量的概率密度函数。信号量化噪声比(SQNR)

11、为： 信源编码是数字通信中的重要环节，它的主要目的是减少冗余，提高编码效率。信源编码可分为两类：无失真编码和有失真编码。无失真编码只对信源冗余度进行压缩，不会改变信源的熵，又称冗余度压缩编码，它能保证码元序列经译码后能无失真的恢复成信源符号序列，如霍夫曼编码，香农编码。有失真编码在允许的失真范围内把编码后的信息率压缩到最小，有失真信源编码的失真范围受限，所以又称为限失真信源编码。信源编码就是把信源符号序列变换到码符号序列的一种映射。若要实现无失真编码，那么这种映射必须是一一对应的、可逆的。一般来说，人们总希望把信源所有的信息毫无保留的传递到接受端，即实现无失真传输，所以首先要对信源实现无失真编

12、码。信源编码有以下三种主要方法： （1）匹配编码根据信源符号的概率不同，编码的码长不同,这样使平均码长最短。将要讲到的霍夫曼编码就是概率匹配编码。 （2）变换编码先对信号进行变换，从一种信号空间变换为另一种信号空间，然后针对变换后的信号进行编码。一般是把分布在时空域的信号（如时域的语音信号和平面空间的图像信号）映射到变换域（如频域的频谱信号和其他正交矢量空间域），原来相关性很强的原始信号经过变换后，得到的变换域系数相互独立，并且能量集中在少数低序系数上，这样只需对少量的变换域的系数进行编码，达到数据压缩的目的。常用的变换编码有DFT、沃尔什变换、小波变换等。 (3)识别编码识别编码主要用于印刷

13、或打字机等有标准形状的文字、符号和数据的编码，比如中文文字和语音的识别。后两种信源编码均为有失真的信源编码。最原始的信源编码就是莫尔斯电码，另外还有ASCII码和电报码都是信源编码。但现代通信应用中常见的信源编码方式有：霍夫曼编码、算术编码、L-Z编码，这三种都是无损编码。而霍夫曼编码作为变长码满足变长信源编码定理。该编码定理是香农信息论中非常重要的一个定理，它指出，要做到无失真的信源编码，信源每个符号所需要的平均码元数就是信源的熵值，如果小于这个值，则唯一可译码不存在，可见，熵是无失真信源编码的极限值。定理还指出，通过对扩展信源进行编码，当N趋向于无穷时，平均码长可以趋进该极限值。还可以证明

14、，如果我们不确切知道信源的概率分布，我们用估计的概率分布去进行编码时，平均码长会加长，但是如果估计的偏差不大的话，平均码长也不会增加太多。1.3 无失真编码算法编码器：编码器可以看作这样一个系统，它的输入端为原始信源S，其符号集为S,而信道所能传输的符号集为X，编码器的功能是用符号集X中的元素，将原始信源的符号Si变换为相应的码字符号Wi,编码器输出端得符号集为C。 编码器 S CX 奇异码与非奇异码若一种分组码中所有码字都不相等，则称分组码为非奇异码，否则为奇异码。唯一可译码与非唯一可译码任意有限长码元序列，如果只能唯一分割成一个个码字便称为唯一可译码。唯一可译码得物理意义是指不仅要求不同的

15、码字表示不同的信源符号，而且还要求对由信源符号构成的符号序列进行编码时，在接受端仍能正确译码而不发生混淆。唯一可译码首先是非奇异码且任意有限长的码字序列不会雷同。即时码与非即时码无需考虑后续的码符号就可以从码符号序列中译出码字，这样的唯一可译码称为即时码变长码及变长编码定理信源符号数、码符号数、码字长度之间满足什么条件才可以构成即时码和唯一可译码呢？Kraft不等式和McMillan不等式回答了这个问题。这两个不等式在形式上是完全一样的。设信源符号集为，码符号集为，对信源进行编码，得到的码为，码长分别为。即时码存在的充要条件是： 这称为Kraft不等式。由上式可知，给定r和q，只要允许码字长度

16、可以足够长，则码长总可以满足Kraft不等式而得到即时码，Kraft不等式指出了即时码的码长必须满足的条件。后来McMillan证明对于唯一可译码得码长也必须满足此不等式。在码长的选择上唯一可译码并不比即时码有更宽松的条件。对于唯一可译码，该不等式又称为McMillan不等式。唯一可译码存在的充要条件是： 其中r为码符号个数，为码字长度，q为信源符号个数无失真变长信源编码定理离散无记忆信源S的N次扩展信源，其熵为，并且编码器的码元符号集为A：对信源进行编码，总可以找到一种编码方法，构成唯一可译码，使信源S中每个符号所需要的平均码长满足当时则有，式中，其中是扩展信源的信源符号所对应的码字长度，因

17、此是扩展信源中每个符号的平均码长，而是信源S中单个信源符号所需的平均码长。这里要注意与的区别：它们都是单个信源符号所需的码符号的平均数，但是的含义是，为了得到这个平均值，不是对单个信源符号进行编码，而是对N个信源符号序列进行编码，然后对N求平均。该定理指出，要做到无失真信源编码，每个信源符号平均所需最少的r元码元数就是信源的熵值。若编码的平均码长小于信源的熵值，则唯一可译码不存在，在译码或反变换时必然要带来失真或差错，同时定理还指出，通过对扩展信源进行变长编码，当时，平均码长可达到这个极限值。可见，信源的信息熵H(S)是无失真信源编码码长的极限值，也可认为信源熵是表示每个信源符号平均所需最少的

18、码元符号数。2 信源最佳化通信系统的传输效率就是指给定信道的信道容量利用率，它表示信道的实际传信率与信道容量的比值，可以写成： =R/C可见要提高传输效率，基本任务就是要改造信源，使其熵值最大化，此时趋于1，而这个过程就是信源最佳化得过程。信源熵H(X)最大化实质上就是寻求一种最佳的概率分布。根据熵函数的性质，在离散信源情况下，当各个符号间彼此独立而出现的概率相等时，信源熵达到最大值。因此，一般的熵值最大化应当包括两个步骤：1、符号独立化，解除符号间的相关性；2、各符号概率均匀化。为了衡量各种编码是否已达到极限情况，我们定义变长码的编码效率。设对信源S进行无失真编码所得到的平均码长为,则,定义

19、 为编码效率，我们可以采用声码器技术，模式识别技术，变换编码技术以及相关编码技术等近几年来发展起来的效率较好的压缩信源方法来解除关联、压缩信源和提高传输效率。经过解除相关性之后，如果再使各符号的概率均匀化，就能进一步改造有剩余信源的输出，去掉冗余度，提高熵速率，使传输率接近信道容量进而使传输效率接近1。如香农-范诺编码，霍夫曼编码。这列编码的基本思想就是使各符号的概率均匀化，即出现概率大的符号编成短码，出现概率较小的符号编成长码，只是由于具体方法不同，得到的效果也不同。3 霍夫曼编码特点及应用霍夫曼编码是真正意义上的最佳编码。首先编码是非续长码，霍夫曼编码实际上构造了一个码树，码树从最上面的端

20、点开始构造，直到树根结束，最后得到一个横放的码树。其次，其编码的平均码长最小，霍夫曼编码采用概率匹配的方法来决定各码字的码长，概率大的符号对应于短码，概率小的符号对应于长码。最后，霍夫曼编码的码字并不唯一，每次对概率最小的两个符号求概率之和形成缩减信源时，就构造出两个树枝，由于对两个树枝附码元时是任意的，所以码字不唯一。另外在霍夫曼编码过程中，对缩减信源符号按概率由大到小的顺序排列时应使合并后的新符号尽可能的排在靠前的位置，这样可使合并后的新符号重新编码次数减少，使短码得到充分利用。 在实际应用中，首先每个信源符号所对应的码长不同，一般情况下，信源符号以匀速输出，信道也是匀速传输的。通过霍夫曼

21、编码后，会造成编码输出的信息速率不是常量，因而不能直接由信道来传送。为了适应信道，必须增加缓冲寄存器，将编码输出暂存在缓冲器中，然后再匀速向信道输出。但当缓冲器容量有限时，会出现缓冲器溢出或取空的现象。所以一般变长码只适用于有限长的信息传输，或者在输出一批消息后能暂停一下。其次，差错扩散的问题。变长码得一个的差错可能造成译码错误，并且还会造成同步错误，结果后面一系列码字也会译错。最后，霍夫曼码的编译码需要用查表的方法来进行。在信息传输过程中必须先存储与传输这一霍夫曼编码表。这会影响信息的传输效率，特别是当N增大时，所需存储的码表也增大，使得设备复杂化，且查表搜索的开销增大。我们还须根据信源的统

22、计特性，事先建立霍夫曼编码表，因此这种方法只适用于已知其统计特性的信源。尽管如此，霍夫曼方法还是一种有效的无失真信源编码方法，它便于硬件实现和计算机上的软件实现，适用于文件传真、语音处理和图像处理的数据压缩。在新世纪，广播电视数字化兴起，有线电视、卫星电视和地面无线广播电视的数字化都发展很快，有线数字电视的另一个发展趋势是利用IP技术的IPTV，数字电视地面无线广播技术新的应用领域是手机电视。我国数字电视地面无线广播系统技术研究较早，提出了多种方案，其中采用伪随机序列（PN）的时域同步频域处理技术等构成了基础性发明专利，所实现的性能优于按照ITU已有的三项国际标准实现的系统。不仅在信道处理技术

23、上而且在信源编码技术上我国也有可喜的创新，我国发布了AVS音视频编码标准，它的压缩效率与国际标准MPEG4/AVC相当，但复杂度低，AVS的部分技术已被吸纳进相应的国际标准。4 编码规则4.1 二元霍夫曼编码规则 （1）将信源符号按概率从大到小的顺序排列。 （2）给两个概率最小的信源符号各分配一个码位“0”和“1”，将两个信源符号合并成一个新符号，并用这两个最小的概率之和作为新符号的概率，结果得到一个只包含（n-1）个信源符号的新信源。称为信源的第一次缩减信源，用s1表示。 （3）将缩减信源s1的符号仍按概率从大到小顺序排列，重复步骤二，得到只含（n-2）个符号的缩减信源s2。 （4）重复上述

24、步骤，直至缩减信源只剩两个符号为止，此时所剩两个符号的概率之和必为1，然后从最后一级缩减信源开始，依编码路径向前返回，就得到各信源符号所对应的码字。4.2 多元霍夫曼编码规则由二进制霍夫曼编码的方法很容易推广到r进制的情况，只是编码的过程中构成缩减信源时，每次都是将r个概率最小的信源符号合并，然后分别用码符号0,1，.,(r-1)表示。为了充分利用短码，使霍夫曼码的平均码长最短，必须使最后一个缩减信源恰好有r个信源符号，因此对于r元霍夫曼码，信源S符号个数q必须满足 其中表示信源缩减次数。如果不满足上式，则可以在最后增补一些概率为零的信源符号，因此上式又可以写成 为增加的信源符号数，并且是满足

25、上式的最小正整数或0。这样处理后得到的r元霍夫曼码可充分利用短码，一定是紧致码。4.3 扩展信源霍夫曼编码对离散无记忆信源的N次扩展信源进行编码便得到N次扩展码。采用霍夫曼编码法能够使码的平均长度最短，信息的冗余量最小。然而这种编码方法所形成的码字很不规整，这样不利于硬件的译码。在很多处理机中，我们采用一种新的折中的方法，称为扩展编码法。这种方法是由定长编码与霍夫曼编码法相结合形成的。有等长扩展法和不等长扩展编码方法，为了便于实现分级译码，我们一般采用等长扩展编码法，当然，也可以根据具体需要采用每次扩展位数不等的不等长扩展法。5 MATLAB性能仿真Problem 1:对信源S编码，其中现对该

26、离散无记忆平稳信源进行霍夫曼编码。对应霍夫曼编码求熵仿真如下: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(p10e-10,error(Not a prob. vector, components do not add up to 1)endh=sum(-p.*log2(p);程序运行结果显示：p = 0.4000 0.2000 0.2000 0.1000 0.1000ans = 2.

27、12195.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(j) p=P(i); P(i)=P(j); P(j)=p; end endenddisp(概率分布);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)+

28、Q(2),Q(3:n),1;endfor 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

29、,:)=j+1)-1)+1:n*find(m(n-i+1,:)=j+1); endendfor 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);%码长endl=sum(P.*ll);%平均码长h1=-log2(P);%自信息量H=P*(h1);%熵Hdisp(二元霍夫曼编码平均码长)ldisp(编码效率)G=H/ldisp(二元霍夫曼编码)(2） 运行结果为：输入概率:0.4,0.2,0.2,0.1,0.1概率分布H = 2.1219二元霍夫曼编码平均码长

30、l = 2.2000编码效率G = 0.9645二元霍夫曼编码ans = 1 000 01 0011 00105.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

31、p.S=input(输入概率:);n=length(S);for i=1:n-1 for j=i+1:n if S(i)=S(j) s=S(i); S(i)=S(j); S(j)=s; end endenddisp(概率分布);Sp=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

32、:n),ones(1,r-1);end for i=1:A c(i,:)=blanks(n*n);endc(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

33、+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); endendfor 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); endH=-sum(p.*log2(p);l=sum(p.*ll);Hdisp(三元霍夫曼编码平均码长)ldisp(编码效率)G=H/(l*log2(r)disp(三元霍夫曼编码)(2)运行结果为：输入概率:0.4,0.2,0.2,0.1,

34、0.1H = 2.1219三元霍夫曼编码平均码长l = 1.4000编码效率G = 0.9563三元霍夫曼编码ans = 2 12 0 10 115.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%

35、 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 =

36、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-1q,l=sort(q);m(i,:)=l(1:n-i+1),zeros(1,i-1);q=q(1)+q(2),q(3:n),1; endfor i=1:n-1c(i,:)=blanks(n*n);endc(n-1,n)=0;c(n-1,2*n)=1;for i=2:n-1c(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-1c(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);endendfor 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,:)=3