信息论编码课程设计.pdf

《信息论编码课程设计.pdf》由会员分享，可在线阅读，更多相关《信息论编码课程设计.pdf（12页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、课程设计任务书 2013 学年第一学期 专业：通信工程 学号：姓名：边阳 课程设计名称：信息论与编码课程设计 设计题目：二进制哈夫曼编码的分析与实现 完成期限：自 2013 年 11 月 4 日至 2013 年 11 月 10 日共 1 周 一设计目的 1、深刻理解信源编码的基本思想与目的；2、理解哈夫曼编码方法的基本过程与特点；3、提高综合运用所学理论知识独立分析和解决问题的能力；4、使用 MATLAB 或其他语言进行编程。二设计内容 假设已知一个信源的各符号概率，编写适当函数，对其进行哈夫曼编码，得出 M 进制码字，平均码长和编码效率，总结此编码方法的特点和应用。三设计要求 1、编写的函数

2、要有通用性；2、信源可以自由选择，符号信源与图像信源均可。四设计条件 计算机、MATLAB 或其他语言环境 五参考资料 1曹雪虹，张宗橙.信息论与编码.北京：清华大学出版社，2007.2王慧琴.数字图像处理.北京：北京邮电大学出版社，2007.指导教师（签字）：教研室主任（签字）：批准日期：年 月 日 摘 要 霍夫曼编码是可变字长编码(VLC)的一种。Huffman 于 1952 年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫作 Huffman 编码。它是根据可变长最佳编码定理，应用哈夫曼算法而产生的一种编码方法。在非均匀符号概率分

3、布的情况下，变长编码总的编码效率要高于等字长编码。因为具体规定了编码的方法，能使无失真编码的效率非常接近与 1，所以在压缩信源信息率的实用设备中，哈夫曼编码还是比较常用的。本课题利用哈夫曼编码的方法实现了对信源符号的熵、平均码长、传输速率、编码效率等的求解。关键词：哈弗曼编码；信源；哈夫曼树 课程设计说明书（论文）第 3 页 共 12 页 目 录 1 课题描述.4 2 设计原理.4 3 设计过程.5 3.1 课题介绍.5 3.1.1 Huffman 编码特点.6 3.1.2 哈夫曼编码方法.6 3.3 设计步骤.7 4 哈夫曼编码的 MATLAB 实现.8 总 结.11 参考文献.12 1 课

4、题描述 huffman 编码是一种二进制编码的算法，目的是缩小原来的数据，简单的说就是将出现概率较高的符号分配较少的码字，而出现概率大的符号分配较长的码字，这样起到压缩数据的作用。哈夫曼编码是可变字长编码(VLC)的一种。Huffman 于 1952 年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长 度最短的码字，有时称之为最佳编码，一般就叫作 Huffman 编码。本课题是利用哈夫曼编码方式来实现对信源符号码字、平均码长及编码效率的求解。开发工具:MATLAB。2 设计原理 设计原理如下：设数字图 像像素 灰度级集 合为 d1,d2,dm,其对 应的概 率分别为 p(d1)

5、,p(d2),p(dm)。按信息论中信源信息熵的定义，图像的熵定义为：字符bitdilbPdiPHmi)(1 （2.1）图像的熵表示像素各个灰度级位数的统计平均值，给出了对此输入灰度 级集合进行编码时所需的平均位数的下限。设 i 为数字图像中灰度级 di 所对应的码字长度（二进制代码的位数），其相应出现的概率为 P（di）,则该数字图像所赋予的平均码字长度为：midiiPR1)(（2.2）00100RH （2.3）根据信息论中信源编码理论，可以证明在 RH 条件下，总可以设计出某种无失真编码方法。当然如果编码结果使 R 远大于 H，表明这种编码方法效率很低，占用比特数太多。最好编码结果是使 R

6、 等于或接近于 H。这种状态的编码课程设计说明书（论文）第 5 页 共 12 页 方法，称为最佳编码。压缩比是指编码前后平均码长之比，如果用 n 表示编码前每个符号的平均码长，通常为用自然二进制码时的位数，则压缩比可表示为：Rnr （2.4）一般来讲，压缩比大，则说明被压缩掉的数据量多。一个编码系统要研究的问题是设法减小编码平均长度 R，使编码效率尽量趋于 1，而冗余度趋于 0。3 设计过程 3.1 课题介绍 3.1.1 Huffman编码特点 凡是能载荷一定的信息量，且码字的平均长度最短，可分离的变长码的码字集合称为最佳变长码。为此必须将概率大的信息符号编以短的码字，概率小的符号编以长的码字

7、，使得平均码字长度最短。哈夫曼（Huffman）编码是最佳变长编码方法的一种，它是根据可变长最佳编码定理，应用哈夫曼算法而产生的一种编码方法。进行哈夫曼编码时，为得到码方差最小的码，应使合并的信源符号位于缩减信源序列尽可能高的位置上，以减少再次合作的次数，充分利用短码。哈夫曼码是用概率匹配方法进行信源编码。它有两个明显的特点：一是哈夫曼码的编码方法保证了概率大的符号对应于短码，概率小的符号对应于长码，充分利用了短码；二是缩减信源的最后两个码字总是最后一位不同，从而保证了哈夫曼编码是即时码。哈夫曼编码方法得到的码并非是唯一的，造成并非唯一的原因是：首先，每次对信源缩减时，赋予信源最后两个概率最小

8、的符号，用 0 和 1 可以任意的，所以可以得到不同的哈夫曼码，但不会影响码字的长度。其次：对信源进行缩减时，两个概率最小的符号合并后的概率与其他信源符号的概率相同时，这两者在缩减信源中进行概率排序，其位置放置次序是可以任意的，故会得到不同的哈夫曼码。此时将影响码字的长度，一般将合并的概率放在上面，这样可以获得较小的码方差。对于多进制哈夫曼编码，为了提高编码效率，就要使长码的符号数量尽量少、概率尽量小，所以信源符号数最好满足rnrm1,其中 r 为进制数，n 为缩减的次数。例如，要进行三进制编码，那么最好信源有 7 个符号，第 1 次合并后减少 2 个成为 5 个，第 2 次合并后又减少 2

9、个成为 3 个，这样给每一步赋予三进制符号就没有浪费了。但如果信源只有 6 个符号时，为了尽量减少最长码的数量，则应该在第 1 次合并时添置概率为零的虚拟符号 1 个，事实上只合并 2 个概率最小的符号，后面每次合并三个，就可以使得最长码的符号数量最少，也就是长码的概率最小，从而得到最高的编码效率。哈夫曼变长码的效率是相当高的，它可以单个信源符号编码或用L 较小的信源序列编码，对编码器的设计来说也将简单的多。但是应当注意，要达到很高的效率仍然需要按长序列来计算，这样才能使平均码字长度降低。3.1.2 哈夫曼编码方法(1)将信源消息符号按其出现的概率大小依次排列为 P1P2 Pn (2)将两个概

10、率最小的字母分别配以 0 和 1 两个码元，并将这两个概率相加作为一个新字母的概率，与未分配的二进制符号的字母重新排队。(3)对重排后的两个概率最小符号重复步骤（2）的过程。(4)不断继续上述过程，直到最后两个符号配以 0 和 1 为止。(5)从最后一级开始，向前返回得到各个信源符号所对应的码元序列，即相应的码字。3.2 设计内容 一个有 8 个符号的信源 X，各个符号出现的概率为：X=04.005.006.007.010.010.018.040.087654321概率：符号：uuuuuuuu 课程设计说明书（论文）第 7 页 共 12 页 试进行霍夫曼编码，并计算平均码长、编码效率、压缩比、

11、冗余度等。3.3 设计步骤 最终的各符号的霍夫曼编码如下：u1:1 u2:001 u3:011 u4:0000 u5:0100 u6:0101 u7:00010 u8:00011 霍夫曼编码时，对同一源图像序列，霍夫曼编码并不是唯一的。如果节 标 1 和标 0 的对调，则相应的霍夫曼编码变成：u1:0 u2:110 u3:100 u4:1111 u5:1011 u6:1010 u7:11101 u8:11100 对照两组霍夫曼编码不难看出，尽管两者的组成不同，但两者的平均码长是一致的。再根据以上数据，可分别计算其信源的熵、平均码长、编码效率及冗余度，即 熵:b P kkPxHk1)(81 =0

12、.4lb 0.40.18lb 0.180.10lb 0.10.07lb 0.070.06lb 0.06 0.05lb 0.050.04lb 0.04 =2.55 平均码长：k P kxRk81)(=10.04+30.18+30.10+40.10+40.07+40.06+50.05 +50.04 =2.61 编码效率：00007.9710061.255.2RH 压缩之前 8 个符号需要 3 个比特量化，经压缩之后的平均码字长度为 2.61，因此压缩比为：15.161.23C 冗余度为：003.21r 对上述信源 X 的霍夫曼编码，其编码效率已达97.7，仅有 2.3的冗余。4 哈夫曼编码的 MA

13、TLAB 实现 在 matlab中调用了用户自定义文件humanff.m的文件，其源代码为：function h,l=huffman(p)if length(find(p10e-10 error(Input is not a prob.vector,the sum of the component is not equal to1.);end n=length(p);%得到输入的元素个数 q=p;m=zeros(n-1,n);for i=1:n-1,q,e=sort(q);m(i,:)=e(1:n-i+1),zeros(1,i-1);q=q(1)+q(2)+q(3:n),e;end for i

14、=1:n-1,c(i,:)=blanks(n*n);end%以下计算各个元素码字 课程设计说明书（论文）第 9 页 共 12 页 c(n-1,n)=0;c(n-2,2*n)=1;for i=2:n-1;c(n-i,1:n-1)=c(n-i+1,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-1 c(n-i,(j+1)*n+1:(j+2)*n)=c(n-i+1,n*(find(m(n-i+1,:)=j+1)-1)+.1

15、:n*find(m(n-i+1,:)=j+1);end 在计算信源平均信息量的时候调用了 message 函数，在计算信源平均信息量的时候调用了 message 函数，message 函数的源代码为：function r=message(x,n)%参数 x 是概率分布，n 是离散信源的分布值数目 r=0;for i=1:n r=r-x(i)*log(x(i)/log(2);end disp(此离散信源的平均信息量为);r 通常哈夫曼编码学的效率是小于 1 的，但当信源为某些特殊情况时，可以是效率达到 1，当然是不可能超过 1 的。如：3011151151613154321UUUUUP 分别调用

16、 huffman 和 message 函数如下：clear all;p=1/3,1/6,1/15,1/15,11/30%定义概率序列 p=0.3333 0.1667 0.0667 0.0667 0.3667 截图为：课程设计说明书（论文）第 11 页 共 12 页 总 结 通过该课程设计，我掌握了编译程序的原理以及步骤，还有编译程序工作的基本过程及其各阶段的基本任务，熟悉了编译程序总流程框图，构造工具及其相关的技术。课本上的知识是机械的，抽象的。在本次课程设计，我有很大的收获。这首先体现在理论知识的完善上：采用等长编码的优点是编码过程和解码过程简单，可是这种方法没有考虑各个符号出现的概率，实际

17、上就是将它们当做等概率事件处理的，所以它的编码效率比较低，而哈夫曼编码是根据可变长最佳编码定理，应用哈夫曼算法而产生的一种编码方法，它的平均码长最小，消息传输速率最大，编码效率最高；同时实践能力和动手能力有了质的飞跃!设计中，我自感知识的缺陷，不断的上网查阅资料，翻阅各类相关书籍，自己动手，自己设计，让我的思维逻辑更加清晰。在上机操作中，靠这次设计我熟练掌握了计算机编程，将理论变为实际开了一个好头。在我设计好之后，老师对我进行指导，使得我的课程设计进一步完善,更加完美。在这次课程设计过程中，我发现了自己综合应用能力的欠缺。以后，我会更加重视用软件编程，应用计算机来对处理信号。总之，基本达到了预期的课程设计目的。参考文献 1 李朝辉，张弘.数字图像处理及应用.北京：机械工业出版社，2004.2 贾永红.数字图像处理.武汉：武汉大学出版社，2003.3 周炯磐，丁晓明.信源编码原理.北京：人民邮电出版社，1996.4 吴柏修，祝宗泰，钱霖君.信息论与编码.南京：东南大学出版社，1991.