回复 2楼 ahyshong
在Matlab上跑了一遍 好像不对?在n>10后会出现编码效率大于1 而且能看出来编码出来的不是唯一码了
程序如下
N=10;%N位的信源
SignalSourcewithoutNormilization=unifrnd(0,1,1,N);%产生随机数
sum=0;
for n=1:N
sum=sum+SignalSourcewithoutNormilization(n);
end
SignalSource=SignalSourcewithoutNormilization./sum;%归一化
SignalSource=sort(SignalSource,'descend')
%排序
SortingMatrix=zeros(N,N);
for i=1:N
P=sort(SignalSource,'descend');%降序排列各概率
SortingMatrix(i,1)=P(i);%将信源各概率输入排列矩阵第一列
end
rear=SortingMatrix(i,1)+SortingMatrix(i-1,1);%合并概率最小两项
P(N-1)=rear;P(N)=0;
P=sort(P,'descend');
t=N-1;
for j=2:n%生成编码表的其他各列
for i=1:t
SortingMatrix(i,j)=P(i);
end
if t>1
K=find(P==rear);
SortingMatrix(N,j)=K(end);%每列最后一个元素用于记录合并发生位置
rear=(SortingMatrix(t-1,j)+SortingMatrix(t,j));%合并最后两项(即概率最小两项)
P(t-1)=rear;
P(t)=0;
P=sort(P,'descend');
t=t-1;
else
SortingMatrix(n,j)=1;
end
end
%生成Huffman码字矩阵和排序后元素的码表
m=3;s1=sym('[2,1]');s2=s1;%码表,用1表示0,2表示1,因为0会因为被省略导致无法记录
%最后一列和倒数第二列的情况可以直接推出故从倒数第三列开始建表
for i=N-2:-1:1
p=SortingMatrix(N,i+1);%p是每列保存上一列最后两个数的合并项的位置
if p==1
s2(1:m-2)=s1(2:m-1);
elseif p==m
s2(1:m-2)=s1(1:m-2);
elseif p==2
s2(1)=s1(1);
s2(2:m-2)=s1(3:m-1);
else
s2(1:p-1)=s1(1:p-1);
s2(p+1:m-2)=s1(p+1:m-2);
end
s2(m-1)=[char(s1(p)),'2'];
s2(m)=[char(s1(p)),'1'];
m=m+1;
s1=s2;
end
L=zeros(1,N);
for i=1:N
[~,rear]=size(char(s2(i)));
L(i)=rear;
end
%将码表转换成0和1输出
array=zeros(1,N);
array(1:n)=s2(1:N);
String=[];
for i=1:n
s=num2str(array(i));
s=strrep(s,'1','0');
s=strrep(s,'2','1');
if i==1
String=s;
else
String=[String,' ',s];
end
end
String=regexp(String,' ','split')%编码后的输出码表
AverageLength=0;
for n=1:N
AverageLength=AverageLength+L(n)*SignalSource(n);
end
AverageLength%平均码长
H=0;
for n=1:N
H=H-SignalSource(n)*log2(SignalSource(n));
end
H
Efficiency=H/AverageLength%编码效率
出来的结果:
>> Huffman
SignalSource =
0.2088 0.1922 0.1591 0.1555 0.1081 0.0495 0.0409 0.0382 0.0247 0.0230
String =
'01' '00' '111' '110' '101' '1111' '11111' '11111' '111111' '111110'
AverageLength =
2.9497
H =
2.9558
Efficiency =
1.0021