霍夫曼编码及其MATLAB实现

一、设计内容

1. 根据霍夫曼编码，对某个离散无记忆信源，每个信源符号都以一定的概率出现，对该信源符号进行霍夫曼编码，得到相应的码字和码树。
2. 使用MATLAB进行霍夫曼编码，输入已知的信源符号及对应的出现概率，根据霍夫曼编码算法，输出该信源的霍夫曼编码对应的码字，并计算信源熵H(X)、平均码长、编码效率和冗余度。

二、设计原理

2.1 编码的目的

2.2 霍夫曼编码特点

由于哈夫曼编码总是以最小概率相加的方法来“缩减”参与排队的概率个数，因此概率越小，对缩减的贡献越大，其对于消息的码字也越长；最小概率相加的方法使得编码不具有唯一性，尤其是碰到存在几个消息符号有着相同概率的情况，将会有多种路径选择，亦即具有多种可能的代码组集合；尽管对同一信源存在着多种结果的哈夫曼编码，但它们的平均码长几乎都是相等的，因为每一种路径选择都是使用最小概率相加的方法，其实质都是遵循最佳编码的原则，因此哈夫曼编码是最佳编码。哈夫曼编码是一种最佳编码，实现也不困难，因此到目前为止它仍是应用最为广泛的无失真信源编码之一。

2.3 霍夫曼编码原理

三、 设计步骤

3.1 二进制哈夫曼编码过程

3.2 计算结果

四、霍夫曼编码的MATLAB编程实现

4.1 程序流程图

其中，霍夫曼编码的具体过程为：信源s1中的q个符号仍按概率大小以递减次序排列，再将其最后两个概率最小的符号合并成一个符号，并分别用0、1码符号表示，这样又形成了由q-2个符号构成的缩减信源s2。依次继续下去，直到缩减信源只剩下两个符号为止，将最后两个字符分别用0、1码符号表示，从右向左读取相应的码字，即为对应信源符号的码字。

4.2 Matlab程序

clear; clc; p=input('请输入数据( 例如[0.3,0.2,0.1] ):\n');%提示输入界面 n=length(p); %N取输入行向量P的长度，即需要编码元素个数 for i=1:n if p(i)<0 %判断输入P矩阵各元素是否全为大于零的有效概率值； fprintf('\n错误：概率值不能小于0!\n'); p=input('请重新输入数据:'); end end if abs(sum(p)-1)>0.00001 %IF语句判断输入矩阵的概率和是否为合理值1 fprintf('\n霍夫曼码中概率总和不能大于1!\n'); p=input('请重新输入数据:'); end Pr=sort(p,'descend');%将输入的信源符号降序排序 q=Pr; a=zeros(n-1,n); %生成一个n-1行 n列的数组，用来记录每行最小两概率叠加后概率排列次序 for i=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]; end for i=1:n-1 %第二个FOR循环生成一个N-1行、N2（N×N）列数组C，每行可看作N个段，每段长为N，记录一个码字（每个码字的长度不会超过N） c(i,1:n*n)=blanks(n*n); end c(n-1,n)='0'; %给C矩阵的N-1行的第一个段赋值0 c(n-1,2*n)='1';%第二个段赋值1。（这两个码字对应编码中最后相加为一的两个概率) for i=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'; %根据之前的规则，在分支的第一个元素最后补0 c(n-i,n+1:2*n-1)=c(n-i,1:n-1); c(n-i,2*n)='1'; %根据之前的规则，在分支的第一个元素最后补1 %决定矩阵C从倒数第二行开始到第一行的每段的码字值。 %每一行值都从下一行值得到，找到在下一行码字中相加本行最小两个概率得到的概率的对应码字， %本行两个最小概率对应码字分别为此码字最后加“0”，加“1” for j=1:i-1 c(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)); end end %完成huffman码字的分配 %FOR循环找到其余的本行在下一行对应的码字，该码字保持不变。循环结 %束后，C矩阵第一行的N段对应输入N个概率所对应符号的码字。该码字 %按码字长短排列 for i=1:n h(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); 

4.3 运行结果

五、小结

通过本次课程大作业，我对霍夫曼编码有了更深的了解，在做课程大作业的过程中我掌握了二元霍夫曼编码树的构造方法。哈夫曼编码是一种变长的无失真编码方案。哈夫曼在编码在数字通信中有着重要的意义。可以根据信源符号的使用概率的高低来确定码元的长度。既实现了信源的无失真地编码，又使得编码的效率最高。此外，在实验的过程中也遇到了一些问题，通过查找资料和相关书籍得到了解决。通过此次实验，我了解了霍夫曼编码的特点，能够运用霍夫曼编码的基本原理及编码算法的来设计与实现程序。包括使对一些Matlab语句的掌握得更加熟练。我受益匪浅，为以后更进一步深入学习奠定了基础。