课设报告12042130徐一凡

1、专业课程设计报告 题 目： 基于 Matlab 的哈夫曼、费诺与香农编码程序实现 姓 名：徐一凡专 业：通信工程班级学号：12042130同 组 人 ：李屹指导教师：陈光 南昌航空大学信息工程学院2015 年 7 月 3 日摘 要用预先规定的方法将文字、数字或其他对象编成数码，或将信息、数据转换成规定的电脉冲信号。编码在电子计算机、电视、遥控和通讯等方面广泛使用，其中哈夫曼、费诺与香农编码有广泛的应用。本次课程设计利用以上三种编码的原理及方法，通过编程实现编码，用Matlab实现了一组概率向量的哈夫曼、费诺与香农编码。 关键字：Matlab、哈夫曼编码、费诺编码、香农编码第一章 设计

2、要求1第二章 编码原理及方法22.1哈夫曼编码22.1.1概述22.1.2编码步骤22.1.3哈夫曼编码举例22.2费诺编码32.3香农编码32.3.1 概述32.3.2编码步骤42.4平均码长及编码效率的计算52.4.1平均码长52.4.2.编码效率5第三章 哈夫曼、费诺与香农编码的MATLAB程序实验63.1 三种编码的流程63.2 三种编码的算法设计63.2.1哈夫曼编码的算法设计63.2.2费诺编码的算法设计63.2.3香农编码的算法设计63.3 程序功能结构图7第四章 程序结果与分析84.1 程序运行结果84.2 结果分析9第五章 总结10参考文献11附录12第一章 设计要求 假设字

3、符集为X=，相应的概率向量为：P=0.2 0.15 0.13 0.12 0.1 0.09 0.08 0.07 0.06。设计要求：（1） 实现对具有概率向量P的离散无失真信源的哈夫曼、费诺与香 农编码；（2）对应给定概率的字符分别得到编码输出码字；（3） 计算平均码长；（4）分析比较 3 者的编码效率。 17第二章 编码原理及方法2.1哈夫曼编码2.1.1概述哈夫曼编码是一种编码方式，哈夫曼编码是可变字长编码的一种。哈夫曼于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长 度最短的码字，有时称之为最佳编码，一般就叫作哈夫曼码。哈夫曼压缩是个无损的压缩算法，一

4、般用来压缩文本和程序文件。它属于可变代码长度算法一种。2.1.2编码步骤（1） 将个信源按概率分布大小依递减次序排列：。（2） 用0,1码符号分别代表概率最小的两个信源符号，并将这两个概率最小的 信源符号合并成一个，得到只包含个符号的新信源，称为缩减信源。（3） 把缩减信源的符号仍按概率大小依递减次序排列，再将其最后两个概率最小的符号合并成一个符号，并分别用0和1符号表示，这样又形成了个符号的缩减信源。（4） 依此继续下去直至信源最后只剩两个符号为止，将这最后两个信源符号分别用二进制符号“0”和“1”表示。（5） 然后，从最后一级缩减信源开始，向前返回，就得出各信源符号所对应的符号序列，即相应

5、码字。2.1.3哈夫曼编码举例 设有离散无记忆信源 对其进行哈夫曼编码。 编码过程如下图所示：图2.1 哈夫曼编码过程2.2费诺编码 费诺编码属于概率匹配编码，但他不是最佳的编码方法。不过有时也可以得到紧致码的性能。费诺编码的过程如下：（1） 将信源消息符号按其出现的概率大小依次排列。（2） 将依次排列的信源符号按概率值分为两大组，使两个组的概率之和近似相同，并对各组赋予一个二进制码元“0”和“1”。（3） 将每一大组的信源符号再分为两组，使划分后的两个组的概率之和近似相同，并对各组赋予一个二进制符号“0”和“1”。（4）如此重复，直至每个组只剩下一个信源符号为止。（5）信源符号所对应的码字即

6、为费诺码。2.3香农编码2.3.1 概述香农第一定理指出了平均码长与信源之间的关系，同时也指出了可以通过编码使平均码长达到极限值，这是一个很重要的极限定理。如何构造这种码？香农第一定理指出，选择每个码字的长度满足下式： 就可以得到这种码。这种编码方法就是香农编码。香农编码法冗余度稍大，实用性不大，但有重要的理论意义。2.3.2编码步骤（1） 将信源发出的N个消息符号按其出现的概率大小依次排列。（2）  按下式计算第i个消息的二进制代码的码长并取整。（3） 为了变成唯一可译码，首先计算第i个消息的累加概率。（4） 将累加概率（为小数）变成二进制数。（5） 去除小数点，并根据码长，取小数

7、点后位作为第i个消息的代码组。由下式确定。 （取整）2.4平均码长及编码效率的计算2.4.1平均码长 设有信源编码后的码字分别为，各码字相应的码长分别为，。因是唯一可译码，信源符号和码字一一对应，则这个码的平均长度为 平均长度表示每个信源符号编码相对平均需用的码符号个数。2.4.2.编码效率编码效率定义为：其中为平均码长。此处。因为编码效率一定是小于或等于1的数。第三章 哈夫曼、费诺与香农编码的MATLAB程序实验3.1 三种编码的流程三种编码部分对应的流程如下面三张流程图提取二进制数小数点后Li位作为码字计算第i个消息的累加概率将累加概率转换为二进制数概率分布按降序排列图3.1香农编码流程框

8、图所得信源符号就是费诺码概率分布按降序排列在每组中重复上一步直至每组只剩一个符号按概率和近似相同分成两组，分别给予二进制码元0、1图3.2费诺编码流程框图在每组中重复上一步直至只剩下两个信源符号为止将概率最小两个符号分配以0、1，然后合并作为新符号重新排序概率分布按降序排列所得信源符号就是费诺码图3.3哈夫曼编码流程框图3.2 三种编码的算法设计3.2.1哈夫曼编码的算法设计按要求输入信源符号概率后用sort()函数将信源符号概率由大到小排序，每次选出最小的两个值，作为二叉树的两个子叶节点，将合并后的和作为它们的根节点，这两个子叶节点不再参与比较，而是新的根节点参与比较。重复选出合并的步骤，直

9、到最后得到和为1的根节点。将形成的二叉树的左节点标0，右节点标1。把从最上面的根节点到最下面的子叶节点途中遇到的0、1序列串起来，这样就得到了各个符号的哈夫曼编码。并且对编码后的平均码 长，以及编码的传输效率进行了求解。3.2.2费诺编码的算法设计按要求输入信源符号概率后用sort()函数将信源符号概率由大到小排序，然后用递归的思想进行费诺编码，求得了每个字符的二进制码字。并且对编码后的平均码 长，以及编码的传输效率进行了求解。 3.2.3香农编码的算法设计按要求输入信源符号概率后用sort()函数将信源符号概率由大到小排序，计算对应的累加概率，套用前面原理中的Li的不等式计算出Li然后从累加

10、概率中取出码字。并且对编码后的平均码长，以及编码的传输效率进行了求解。3.3 程序功能结构图综合上述，整个程序的结构功能如下：输入信源符号个数输入信源符号概率计算信源熵调用对应编码函数进行对应编码计算对应的平均码长、编码效率输出显示对应码字、平均码长以及编码效率图3.4程序功能结构框图对应代码请参考附录程序清单第四章 程序结果与分析4.1 程序运行结果（1） 香农编码结果图4.1香农编码结果（2） 费诺编码结果图4.2费诺编码结果（3） 哈夫曼编码结果图4.3哈夫曼编码结果4.2 结果分析从上面的三个运行结果可以看出该结果与理论一致，香农码的冗余度最高，编码效率最低，而费诺和哈夫曼编码的编码效

11、率则更高，其中哈夫曼编码的编码效率最高。第五章 总结通过这次课程设计对MATLAB的运用更加熟练，对MATLAB的理解也更加的深刻。还有最重要的是阅资料，从海量的信息中筛选出有用的信息，然后灵活的运用掌握的信息，这种能力对于自主学习很重要。编程的过程中遇到了很多的问题，比如，在编写哈夫曼编码的程序的时候，对于input语句的应用不熟练，导致了程序的不完善，没有办法根据需要去输入概率，只能在源程序上修改概率，最终这个问题通过不断的尝试和修改还是解决了。另外对信息论与编码知识的有了更深刻的理解，通过程序编码的实践更加地巩固了对哈夫曼、费曼与香农编码原理及方法的了解，解决了当时在课堂上因为条件限制而

12、未解决的疑问。本次课程设计优点是整体的算法比较简单，实现起来比较容易结果也简单明了，同样的这次设计的缺点也很明显，没有好的输入界面，也无法选择对应的编码方式，从输入到输出都显得比较粗糙。经过本次实验，充分学习了三种编码理论及其重点内容，掌握了三种编码原理的同时也锻炼了编程水平，为以后的学习中出现的可能问题做好了准备，锻炼了动手能力和设计能力，掌握了一种科技工具，丰富了学习生活。参考文献1 蔡旭辉. MATLAB基础与应用教程.北京：人民邮电出版社，2009.2 曹雪虹. 信息论与编码.北京：清华大学出版社，2009.3 周荫清. 信息理论基础（第四版）.北京：北京航空航天大学出版社，2012.

13、附录程序清单1. 主程序：n=input('输入单符号信源个数n=');s=0;l3=0;H=0;p=zeros(1,n);for i=1:np(1,i)=input('输入单符号信源概率:');s=s+p(i);%概率累加H=H+(-p(i)*log2(p(i);%计算信源信息熵endif sum(p)<1|sum(p)>1 error('不符合概率分布无效')endy=fliplr(sort(p);%大到小排序hfmbm(y,n,H);%哈夫曼编码fnbm(n,p,y,H);%费诺编码xnbm(n,H,y);%香农编码2. 哈夫曼

14、编码函数hfmbm.m文件function hfmbm(y,n,H)Q=y;m=zeros(n-1,n);for i=1:n-1 %循环缩减对概率值排序，画出由每个信源符号概率到1.0 处的路径，Q,l=sort(Q);m(i,:)=l(1:n-i+1),zeros(1,i-1);Q=Q(1)+Q(2),Q(3:n),1;endfor i=1:n-1c(i,:)=blanks(n*n);endc(n-1,n)='0'c(n-1,2*n)='1'for i=2:n-1 %对字符数组c码字赋值过程，记下沿路径的“1”和“0”；c(n-i,1:n-1)=c(n-i+1

15、,n*(find(m(n-i+1,:)=1)-(n-2):n*(find(m(n-i+1,:)=1);c(n-i,n)='0'c(n-i,n+1:2*n-1)=c(n-i,1:n-1);c(n-i,2*n)='1'for j=1:i-1c(n-i,(j+1)*n+1:(j+2)*n)=c(n-i+1,n*(find(m(n-i+1,:)=j+1)-1)+1:n*find(m(n-i+1,:)=j+1);endendfor i=1:nh(i,1:n)=c(1,n*(find(m(1,:)=i)-1)+1:find(m(1,:)=i)*n);%码字赋值ll(i)=l

16、ength(find(abs(h(i,:)=32); %各码字码长endl=sum(y.*ll); %计算平均码长n=H/l; %计算编码效率fprintf('按概率降序排列的霍夫曼码码字:n');disp(h) %按照输入顺序排列的码字fprintf('平均码长:n');disp(l) %输出平均码长fprintf('编码效率:n');disp(n) %输出编码效率3. 费诺编码函数fnbm.m文件function fnbm(n,p,y,H)l2=0;x=f1(1,n,p,1);for i=1:n%计算平均码长L2(i)=length(find

17、(x(i,:);l2=l2+y(i)*L2(i);endN2=H/l2;%计算编码效率fprintf('按概率降序排列的费诺码码字:n');disp(x)%显示按概率降序排列的码字fprintf('平均码长:n');disp(l2)%显示平均码长fprintf('编码效率:n');disp(N2)%显示编码效率f1.m文件function x=f1(i,j,p,r)global x; x=char(x);if(j<=i)return;elseq=0;for t=i:j%对于区间i,j自上而下求累加概率值q=p(t)+q;y(t)=q;end

18、for t=i:j%把所有自上而下的累加概率值与该区间总概率值减该累加概率值之差取绝对值存在一数组v(t)=abs(y(t)-(q-y(t);endfor t=i:jif(v(t)=min(v)%求该数组中最小的一个值来确定分界点位置for k=i:t %赋值码字x(k,r)='0'endfor k=(t+1):jx(k,r)='1'endd=t;f1(i,d,p,r+1);%递归调用及相互调用f2(d+1,j,p,r+1);f1(d+1,j,p,r+1);f2(i,d,p,r+1);elseendendendreturn;f2.m文件function x=f2

19、(i,j,p,r)global x;x=char(x);if(j<=i)return;elseq=0;for t=i:j%对于区间i,j自上而下求累加概率值q=p(t)+q;y(t-i+1)=q;endfor t=1:j-(i-1)%把所有自上而下的累加概率值与该区间总概率值减该累加概率值之差取绝对值存在一数组v(t)=abs(y(t)-(q-y(t);endfor t=1:j-(i-1)if(v(t)=min(v)%求该数组中最小的一个值来确定分界点位置d=t+i-1;for k=i:d%赋值码字x(k,r)='0'endfor k=(d+1):jx(k,r)='1'endf2(d+1,j,p,r+1);%递归调用及相互调用f1(i,d,p,r+1);f2(i,d,p,r+1);f1(d+1,j,p,r+1);elseendendendreturn;4. 香农编码函数xnbm.m文件function xnbm(n,H,y)l1=0;D=zeros(n,4);%生成n*4的零矩阵D(:,1)=y'%把y赋给零矩阵的第一列for i=2:nD(1,