Huffman编码软件实现

1、信息与编码实验报告姓名： 学号： 专业班级： 学院： 联系方式: 实验二：Huffman编码软件实现一、实验目的1. 进一步熟悉Huffman编码过程；2. 掌握Matlab程序的设计和调试技术。二、实验要求1. 输入：信源符号个数r、信源的概率分布P；2. 输出：每个信源符号对应的Huffman编码的码字。三、实验内容1) 从键盘输入组成信源S的字符个数N；2) 从键盘输入信源S和组成信源的字符所对应的概率数组P；3) 对信源进行二进制Huffman编码。四、实验报告1. 简要总结Huffman编码的原理与特点 霍夫曼（Huffman）编码是1952年为文本文件而建立，是一种统计编码。属于无

2、损压缩编码。霍夫曼编码的码长是变化的，对于出现频率高的信息，编码的长度较短；而对于出现频率低的信息，编码长度较长。这样，处理全部信息的总码长一定小于实际信息的符号长度。霍夫曼编码，有如下特征：a 它是一种分组码：各个信源符号都被映射成一组固定次序的码符号。b 它是一种唯一可解的码：任何码符号序列只能以一种方式译码。c 它是一种即时码：由于代表信源符号的节点都是终端节点，因此其编码不可能是其他终端节点对应的编码的前缀，即霍夫曼编码所得的码字为即时码。所以，一串码符号中的每个码字都可不考虑其后的码符号直接解码出来。2. 写出Huffman编码的基本步骤，画出实现Huffman编码的程序流程图。设信

3、源s=s1,s2,sq,其对应的概率分布为p(si)=p1,p2,pq,霍夫曼编码的编码步骤如下：a. 将q个信源符号按概率递减的方式排列。b. 用0、1码符号分别表示概率最小的两个信源符号，并将这两个概率最小的信源符号合并成一个新的符号，其概率为两符号概率之和，从而得到只包含q-1个符号的新信源，称为s信源的缩减信源s1.c. 将缩减信源s1中的符号仍按概率大小以递减次序排列，再将其最后两个概率最小的符号合并成一个符号，并分别用0、1码符号表示，这样又形成了由q-2个符号构成的缩减信源s2.d. 依次继续下去，直到缩减信源只剩下两个符号为止，将最后两个字符分别用0、1码符号表示，从右向左读取

4、相应的码字，即为对应信源符号的码字。霍夫曼编码程序流程图：开始输入信源符号对应的概率p(si)=p1,p2,pq将x1.x2合并成一个新的符号，其概率为两符号概率之和，s信源的缩减信源s1.将缩减信源将剩下的最后两个字符分别用0、1码符号表示把以上概率按递减的方式排列用0、1码符号分别表示概率最小的两个信源符号x1.x2将缩减信源s1中的符号仍按概率大小以递减次序排列进行q-2次循环从右向左读取相应的码字，输出码字结束3. 给出Huffman编码的源程序，并给出实验过程中的测试结果例：使用matlab语言对以下信源进行Huffman编码，并使用该程序求每个信源符号对应的Huffman编码的码字

5、。程序如下所示：%哈夫曼编码的MATLAB实现（基于0、1编码）：clc;clear;A=0.4,0.18,0.1,0.1,0.07,0.06,0.05,0.04;%信源消息的概率序列A=fliplr(sort(A);%按降序排列T=A;m,n=size(A);B=zeros(n,n-1);%空的编码表（矩阵）for i=1:n B(i,1)=T(i);%生成编码表的第一列endr=B(i,1)+B(i-1,1);%最后两个元素相加T(n-1)=r;T(n)=0;T=fliplr(sort(T);t=n-1;for j=2:n-1%生成编码表的其他各列 for i=1:t B(i,j)=T(i

6、); end K=find(T=r); B(n,j)=K(end);%从第二列开始，每列的最后一个元素记录特征元素在该列的位置 r=(B(t-1,j)+B(t,j);%最后两个元素相加 T(t-1)=r; T(t)=0; T=fliplr(sort(T); t=t-1;endB;%输出编码表END1=sym(0,1);%给最后一列的元素编码END=END1;t=3;d=1;for j=n-2:-1:1%从倒数第二列开始依次对各列元素编码 for i=1:t-2 if i1 & B(i,j)=B(i-1,j) d=d+1; else d=1; end B(B(n,j+1),j+1)=-1; te

7、mp=B(:,j+1);x=find(temp=B(i,j); END(i)=END1(x(d); end y=B(n,j+1); END(t-1)=char(END1(y),0; END(t)=char(END1(y),1; t=t+1; END1=END;end A%排序后的原概率序列 END%编码结果for i=1:n a,b=size(char(END(i); L(i)=b;endavlen=sum(L.*A)%平均码长 H1=log2(A);H=-A*(H1)%熵P=H/avlen%编码效率结果输出如下：A为排序后的原概率序列A = 0.4000 0.1800 0.1000 0.1000 0.0700 0.0600 0.0500 0.0400每个信源符号对应的Huffman编码的码字为：END = 1, 001, 011, 0000, 0100, 0101, 00010, 00011 平均码长为avlen =2.6100熵H = 2.5524编码效率P =0.97794. 总结实验过程遇到的问题及解决方法在一开始编程时，不要忘记对原始概率先进行降序排列，并把最小的两个概率相加求和。循环结束后，对最后的两个字符分别用0、1表示。然后按照从左到右的方式进行编码，输出码字。注意matlab编程中的一些细节问题，不要出错。5.实验收获及总结通过本次实验，加深