基于MATLAB的二元/三元霍夫曼编码仿真

说明：《信息论与信息编码》课程设计
一、设计要求：
1、完成编程仿真，写成函数形式（建议用Matlab）
2、输入：任意信源的概率分布（信源符号不小于20个）
3、输出：二进制/三进制编码后的：码字、平均码长、编码效率

二、Matlab代码：

function Huffman_code
clc
%输入符号的数目和进制
num=input('请输入符号的个数:');

%随机产生符号的概率分布
symbol_PD=rand(1,num);
symbol_PD=symbol_PD./sum(symbol_PD(:));

fprintf('\n随机产生%d个符号，其概率(和为1)从小到大依次为\n',num)
symbol_PD=sort(symbol_PD)
symbol_PD2=symbol_PD;
symbol_PD3=symbol_PD;
PD=symbol_PD;


%PartI 产生二进制霍夫曼编码
for i=1:num-1   
    [symbol_PD2,S]=sort(symbol_PD2);
    M(i,:)=[S(1:num-i+1),zeros(1,i-1)];
    symbol_PD2(1)=symbol_PD2(1)+symbol_PD2(2);
    symbol_PD2(2)=[];
    symbol_PD2(num-i+1)=1;
    H2(i,1:num*num)=blanks(num*num);
end
H2(num-1,num)='1';
H2(num-1,2*num)='0';
for i=2:num-1
    t1=find(M(num-i+1,:)==1);
    H2(num-i,1:num-1)=H2(num-i+1,num*t1-(num-2):(num*t1)); 
    H2(num-i,num)='0'; 
    H2(num-i,num+1:2*num-1)=H2(num-i,1:num-1); 
    H2(num-i,2*num)='1'; 
    for j=1:i-1
        t2=find(M(num-i+1,:)==j+1);
        H2(num-i,(j+1)*num+1:(j+2)*num)=H2(num-i+1,num*(t2-1)+1:num*t2);
    end
end 
for i=1:num
    t3=find(M(1,:)==i);
    Huffman_Code2(i,1:num)=H2(1,num*(t3-1)+1:t3*num); 
end
%求二进制霍夫曼编码平均码长
Huffman_Code2=cellstr(Huffman_Code2);
for i=1:num
    Huffman_Code2= strtrim(Huffman_Code2);
end
fprintf('\nPartI 对应的二进制霍夫曼编码是\n')
Huffman_Code2a=Huffman_Code2'
ave2=0;
u=1;
while  u<=length(PD)
    ave2=ave2+PD(u)*length(char(Huffman_Code2(u)));
    u=u+1;
end
fprintf('平均码长为%f\n',ave2)
%求二进制霍夫曼编码编码效率
hx1=0;
v=1;
while v<=length(PD)
    hx1=hx1-PD(v)*log2(PD(v));
    v=v+1;
end
n2=hx1/ave2;
fprintf('编码效率为%2.2f%%\n',n2*100) 


%PartII 产生三进制霍夫曼编码
%判断是否需要添加0概率符号
zero=[0];
a=0;
if mod(num,2)==0
    symbol_PD3=[zero symbol_PD3];
    a=1;
end
L=length(symbol_PD3);
times=floor(num/2);%次数

for i=1:times
    [symbol_PD3,S1]=sort(symbol_PD3);
    M1(i,:)=[S1(1:L-2*(i-1)),zeros(1,2*(i-1))];
    symbol_PD3(1)=symbol_PD3(1)+symbol_PD3(2);
    symbol_PD3(2)=[];
    symbol_PD3(3)=[];
    symbol_PD3(L-i+1)=1;
    symbol_PD3(L-i)=1;
end

for i=1:times
    H3(i,1:L*L)=blanks(L*L);
end
H3(times,L)='2'; 
H3(times,2*L)='1'; 
H3(times,3*L)= '0';

for i=2:times
    H3(times-i+1,1:L-1)=H3(times-i+2,L*(find(M1(times-i+2,:)==1))-(L-2):L*(find(M1(times-i+2,:)==1)));            
    H3(times-i+1,L)='2'; 
    H3(times-i+1,L+1:2*L-1)=H3(times-i+1,1:L-1); 
    H3(times-i+1,2*L)='1';
    H3(times-i+1,2*L+1:3*L-1)=H3(times-i+1,1:L-1);
    H3(times-i+1,3*L)='0';
    for j=1:2*(i-1)
        H3(times-i+1,(j+2)*L+1:(j+3)*L)=H3(times-i+2,L*(find(M1(times-i+2,:)==j+1)-1)+1:L*find(M1(times-i+2,:)==j+1)); 
    end 
end
%求二进制霍夫曼编码平均码长
for i=1:(L-a)
    Huffman_Code3(i,1:L)=H3(1,L*(find(M1(1,:)==i)-1)+1:find(M1(1,:)==i)*L); 
end
Huffman_Code3=cellstr(Huffman_Code3);
for i=1:num
    Huffman_Code3= strtrim(Huffman_Code3);
end
fprintf('\nPartII 对应的三进制霍夫曼编码是\n')
Huffman_Code3a=Huffman_Code3'
ave3=0;
u=1;
while  u<=length(PD)
    ave3=ave3+PD(u)*length(char(Huffman_Code3(u)));
    u=u+1;
end
fprintf('平均码长为%f\n',ave3)
%求三进制霍夫曼编码编码效率
hx3=0;
v2=1;
while v2<=length(PD)
    hx3=hx3-PD(v2)*(log(PD(v2))/log(3));s
    v2=v2+1;
end
n3=hx3/ave3;
fprintf('编码效率为%2.2f%%\n',n3*100) 
end 

三、仿真结果

请输入符号的个数:20
随机产生20个符号，其概率(和为1)从小到大依次为
symbol_PD =
  1 至 8 列
    0.0035    0.0038    0.0051    0.0108    0.0190    0.0207    0.0307    0.0352
  9 至 16 列
    0.0424    0.0487    0.0495    0.0544    0.0717    0.0771    0.0784    0.0787
  17 至 20 列
    0.0850    0.0883    0.0914    0.1055

PartI 对应的二进制霍夫曼编码是

Huffman_Code2a =
  1×20 cell 数组
  1 至 5 列
    {'11010110'}    {'11010111'}    {'1101010'}    {'110100'}    {'001010'}
  6 至 11 列
    {'001011'}    {'11011'}    {'00100'}    {'1000'}    {'1001'}    {'1100'}
  12 至 18 列
    {'0000'}    {'0001'}    {'0011'}    {'0100'}    {'0101'}    {'0110'}    {'0111'}
  19 至 20 列
    {'101'}    {'111'}

平均码长为4.014915
编码效率为98.88%

PartII 对应的三进制霍夫曼编码是
Huffman_Code3a =
  1×20 cell 数组
  1 至 5 列
    {'2212222'}    {'2212221'}    {'2212220'}    {'221221'}    {'221220'}
  6 至 12 列
    {'22121'}    {'22120'}    {'2211'}    {'2210'}    {'222'}    {'220'}    {'012'}
  13 至 20 列
    {'011'}    {'010'}    {'21'}    {'20'}    {'12'}    {'11'}    {'10'}    {'02'}

平均码长为2.792546
编码效率为89.70%