河南大学民生学院本科毕业论文
（3）将缩减信源s1的符号仍按概率从大到小顺序排列，重复步骤二，得到只含（n-2）个符号的缩减信源s2。
（4）重复上述步骤，直至缩减信源只剩两个符号为止，此时所剩两个符号的概率之和必为1，然后从最后一级缩减信源开始，依编码路径向前返回，就得到各信源符号所对应的码字。
4.2 多元霍夫曼编码规则
由二进制霍夫曼编码的方法很容易推广到r进制的情况，只是编码的过程中构成缩减信源时，每次都是将r个概率最小的信源符号合并，然后分别用码符号 0,1，...,(r-1)表示。
为了充分利用短码，使霍夫曼码的平均码长最短，必须使最后一个缩减信源恰好有r个信源符号，因此对于r元霍夫曼码，信源S符号个数q必须满足
q?(r?1)??r
其中?表示信源缩减次数。如果不满足上式，则可以在最后增补一些概率为零的信源符号，因此上式又可以写成
q?i?(r?1)??r
i为增加的信源符号数，并且是满足上式的最小正整数或0。这样处理后得到的r元霍夫曼码可充分利用短码，一定是紧致码。
4.3 扩展信源霍夫曼编码
对离散无记忆信源的N次扩展信源进行编码便得到N次扩展码。
采用霍夫曼编码法能够使码的平均长度最短，信息的冗余量最小。然而这种编码方法所形成的码字很不规整，这样不利于硬件的译码。在很多处理机中，我们采用一种新的折中的方法，称为扩展编码法。这种方法是由定长编码与霍夫曼编码法相结合形成的。有等长扩展法和不等长扩展编码方法，为了便于实现分级译码，我们一般采用等长扩展编码法，当然，也可以根据具体需要采用每次扩展位数不等的不等长扩展法。
5 MATLAB性能仿真
Problem 1:
对信源S编码，其中
8
河南大学民生学院本科毕业论文
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<0))~=0,
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(j) 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显示排序后位置的变动信息
9
河南大学民生学院本科毕业论文
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 编码效率
10
河南大学民生学院本科毕业论文
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)<=S(j) s=S(i); S(i)=S(j); S(j)=s; end end end
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))];
11
