一、实验目的：
(1)了解信源变长码的编码方法；
(2)掌握哈夫曼编码方法；
(3)掌握MATLAB的编程。
二、实验仪器：
Matlaba
三、实验原理：
二元霍夫曼编码步骤如下:
1.将信源符号按概率从大到小的顺序排列，令
2.给两个概率最小的信源符号Sn-1和Sn,各分配一个码元“0”和“1”，并将这两个信源符号合并成一个新符号，并用这两个最小的概率之和作为新符号的概率，结果得到一个只包含(n-1)个信源符号的新信源。称为信源的第一次缩减信源，用S1表示。
3.将缩减信源的符号仍按概率从大到小顺序排列，重复步骤2，得到只含(n-2)个符号的缩减信源S2
4.重复上述步骤，直至缩减信源只剩两个符号为止，此时所剩两个符号的概率之和必为1。然后从最后一级缩减信源开始，依编码路径向前返回，就得到各信源符号所对应的码字。
四、实验步骤:
1.先利用Matlab编写函数；
2.再根据函数将实验要求生成实验结果；
3.根据实验内容填写实验报告；
五、实验内容及数据整理：
用Matlab软件编程实现Huffman编码
六、实验结果及讨论
第一种方法:
clear;clc;close allp=input('请输入数据( 例如[0.3,0.2,0.1] ):\n');%提示输入界面n=length(p); %N取输入行向量P的长度，即需要编码元素个数fori=1:nifp(i)<0 %判断输入P矩阵各元素是否全为大于零的有效概率值；fprintf('\n错误：概率值不能小于0!\n');p=input('请重新输入数据:');endendifabs(sum(p)-1)>0.00001 %IF语句判断输入矩阵的概率和是否为合理值1fprintf('\n霍夫曼码中概率总和不能大于1!\n');p=input('请重新输入数据:');endPr=sort(p,'descend');%将输入的信源符号降序排序q=Pr;a=zeros(n-1,n); %生成一个n-1行 n列的数组，用来记录每行最小两概率叠加后概率排列次序fori=1:n-1 %第一个FOR循环确定概率大小值的排列，得到a数组[q,l]=sort(q);a(i,:)=[l(1:n-i+1),zeros(1,i-1)];q=[q(1)+q(2),q(3:n),1];endfori=1:n-1 %第二个FOR循环生成一个N-1行、N2（N×N）列数组C，每行可看作N个段，每段长为N，记录一个码字（每个码字的长度不会超过N）c(i,1:n*n)=blanks(n*n);endc(n-1,n)='0'; %给C矩阵的N-1行的第一个段赋值0c(n-1,2*n)='1';%第二个段赋值1。（这两个码字对应编码中最后相加为一的两个概率)fori=2:n-1 %主要的程序，循环N-2次c(n-i,1:n-1)=c(n-i+1,n*(find(a(n-i+1,:)==1))-(n-2):n*(find(a(n-i+1,:)==1)));c(n-i,n)='0'; %根据之前的规则，在分支的第一个元素最后补0c(n-i,n+1:2*n-1)=c(n-i,1:n-1);c(n-i,2*n)='1'; %根据之前的规则，在分支的第一个元素最后补1%决定矩阵C从倒数第二行开始到第一行的每段的码字值。%每一行值都从下一行值得到，找到在下一行码字中相加本行最小两个概率得到的概率的对应码字，%本行两个最小概率对应码字分别为此码字最后加“0”，加“1”forj=1:i-1c(n-i,(j+1)*n+1:(j+2)*n)=c(n-i+1,n*(find(a(n-i+1,:)==j+1)-1)+1:n*find(a(n-i+1,:)==j+1));endend%完成huffman码字的分配%FOR循环找到其余的本行在下一行对应的码字，该码字保持不变。循环结 %束后，C矩阵第一行的N段对应输入N个概率所对应符号的码字。该码字 %按码字长短排列fori=1:nh(i,1:n)=c(1,n*(find(a(1,:)==i)-1)+1:find(a(1,:)==i)*n);ll(i)=length(find(abs(h(i,:))~=32)); %计算每一个huffman编码的长度end%第五个FOR循环根据M矩阵第一行记录的概率排序位置分配给每个概率对应符号的码字。average_len=sum(Pr.*ll); %计算平均码长HX=sum(Pr.*(-log2(Pr))); %计算信源熵yita=HX/average_len; %计算编码效率r=1-yita; %计算冗余度disp(['信号符号S： ',num2str(1:n)]);fprintf('\n信源符号出现的概率为:\n');disp(Pr);fprintf('\nHuffman编码结果为:\n');disp(h);fprintf('\n编码的平均码长为:');disp(average_len);fprintf('\n信源熵为:');disp(HX);fprintf('\n编码效率为:');disp(yita);fprintf('\n冗余度为:');disp(r);
第二种方法：
function[ u, c, e, f] = Untitled2( A )%HUFF_CODEC 哈夫曼编码的MATLAB实现%A 输入的原始频率分布，为行向量eg A=[1,2,3,4,5]A=sort(A,'descend');%按降序排列T=A;u=A;A=A/sum(A);[~,n]=size(A);%生成待编码矩阵，每列最后一个元素为特殊元素的位置B=zeros(n,n);fori=1:nB(i,1)=T(i);%生成编码表的第一列endr=B(i,1)+B(i-1,1);%最后两个元素相加T(n-1)=r;T(n)=0;T=sort(T,'descend');t=n-1;forj=2:n%生成编码表的其他各列fori=1:tB(i,j)=T(i);endift>1K=find(T==r);B(n,j)=K(end);%从第二列开始，每列的最后一个元素记录特征元素在该列的位置r=(B(t-1,j)+B(t,j));%最后两个元素相加T(t-1)=r;T(t)=0;T=sort(T,'descend');t=t-1;elseB(n,j)=1;endend%生成Huffman码字矩阵和排序后元素的码表向量m=3;s1=sym('[2,1]');s2=s1;%码表，用1表示0,2表示1，因为0会因为被省略导致无法记录%这里意思是从倒数第三列开始建表，因为最后一列和倒数第二列的情况我们可以直接推出。fori=n-2:-1:1p=B(n,i+1);%p是每列保存的特殊元素的位置，特殊元素指的是由上一列最后两个数新合成的数ifp==1s2(1:m-2)=s1(2:m-1);elseifp==ms2(1:m-2)=s1(1:m-2);elseifp==2s2(1)=s1(1);s2(2:m-2)=s1(3:m-1);elses2(1:p-1)=s1(1:p-1);s2(p+1:m-2)=s1(p+1:m-2);ends2(m-1)=[char(s1(p)),'2'];s2(m)=[char(s1(p)),'1'];m=m+1;s1=s2;endL=zeros(1,n);fori=1:n[~,r]=size(char(s2(i)));L(i)=r;end%将码表转换成0和1输出arr=zeros(1,n);arr(1:n)=s2(1:n);str=[];fori=1:ns=num2str(arr(i));s=strrep(s,'1','0');s=strrep(s,'2','1');ifi==1str=s;elsestr=[str,' ',s];endendstr=regexp(str,' ','split');%计算返回值c=str;e=sum(L.*A);%平均码长H1=log2(A);H=-A*(H1');%熵f=H/e;%编码效率end
