二进制哈夫曼编码

课程设计任务书2023—2023学年第一学期专业：通信工程 学号： 姓名：课程设计名称： 信息论与编码课程设计 设计题目： 二进制哈夫曼编码的分析与实现 完成期限：自 年 月 日至 年 月 日共 一．设计目的1、深刻理解信源编码的根本思想与目的；2、理解哈夫曼编码方法的根本过程与特点；3、提高综合运用所学理论学问独立分析和解决问题的力量；二．设计内容出二进制码字，平均码长和编码效率，总结此编码方法的特点和应用。三．设计要求1、编写的函数要有通用性；2、信源可以自由选择，符号信源与图像信源均可。四．设计条件计算机、MATLAB或其他语言环境五．参考资料[1]曹雪虹，张宗橙.信息论与编码.北京：清华大学出版社，2023.[2]王慧琴.数字图像处理.北京：北京邮电大学出版社，2023.指导教师〔签字： 教研室主任〔签字批准日期： 年 月 日摘要(VLC)的一种。Huffman1952年提出一种编编码。它是依据可变长最正确编码定理，1，所以在压缩信源信息率的有用设备中，哈夫曼编码还是比较常用的。编码效率等的求解。关键词：Huffman；可变长编码；信源编码目录\l“_TOC_250010“1.课题描述 1\l“_TOC_250009“设计原理 1\l“_TOC_250008“设计过程 2\l“_TOC_250007“课题介绍 2\l“_TOC_250006“Huffman编码特点 2\l“_TOC_250005“哈夫曼编码方法 3\l“_TOC_250004“设计内容 3\l“_TOC_250003“设计步骤 4\l“_TOC_250002“哈夫曼编码的MATLAB实现 5\l“_TOC_250001“总 结 8\l“_TOC_250000“参考文献 9 课程设计说明书〔论文〕 课程设计说明书〔论文〕 19页1. 课题描述huffman编码是一种二进制编码的算法，目的是缩小原来的数据，简洁的说字，这样起到压缩数据的作用。哈夫曼编码是可变字长编码(VLC)的一种。Huffman1952年提出一种编码方法，该方法完全依据字符消灭概率来构造异Huffman编码。率的求解。设计原理设计原理如下：设数字图像像素灰度级集合为{d1,d2,…,dm},其对应的概率分别为p(d1),p(d2),…,p(dm)。按信息论中信源信息熵的定义，图像的熵定义为：Hmi1

PdilbP(di)bit字符 〔2.1〕图像的熵表示像素各个灰度级位数的统计平均值，给出了对此输入灰度级集合进展编码时所需的平均位数的下限。设βidi所对应的码字长度〔二进制代码的位数P〔di〕,则该数字图像所赐予的平均码字长度为：Rmi1HR

iP(di) 〔2.2〕10000 〔2.3〕R≧H条件下，总可以设计出某种RH，说明这种编码方法效率很RH。这种状态的编码方法，称为最正确编码。n表示编码前每个符号的平均码长，通常为用自然二进制码时的位数，则压缩比可表示为：r n 〔2.4〕R一般来讲，压缩比大，则说明被压缩掉的数据量多。一个编码系统要争论0。设计过程课题介绍Huffman编码特点〔Huffman〕编码是最正确变长编码方法。码。01差。mr1nr,r为进制数，n为缩减的次数。例如，要进展三进制编码，那么最好信源有7个符号，第1次合并后削减25223个符号时，为了尽量削减最长码的数量，112个概率最的概率最小，从而得到最高的编码效率。L较小的的效率仍旧需要按长序列来计算，这样才能使平均码字长度降低。哈夫曼编码方法P1≧P2≧…≧Pn1两个码元，并将这两个概率相加作为一个字母的概率，与未安排的二进制符号的字母重排队。对重排后的两个概率最小符号重复步骤〔2〕的过程。不断连续上述过程，直到最终两个符号配以0和1为止。相应的码字。设计内容8X，各个符号消灭的概率为：符号：u1 u2 u3 u4 u5 u6 u7 u8X= 4018101007060504试进展霍夫曼编码，并计算平均码长、编码效率、压缩比、冗余度等。设计步骤最终的各符号的霍夫曼编码如下：u1:1 u2:001 u3:011 u4:0000u5:0100u6:0101 u7:00010 u8:0001110u1:0 u2:110 u3:100 u4:1111u5:1011u6:1010 u7:11101 u8:11100全都的。再依据以上数据，可分别计算其信源的熵、平均码长、编码效率及冗余度，即熵:H(x)8

Pk1bPk

=－0.4lb0.4－0.18lb0.18－0.10lb0.1－0.07lb0.07－0.06lb0.06－0.05lb0.05－0.04lb0.04=2.558

kPk

=1×0.04+3×0.18+3×0.10+4×0.10+4×0.07+4×0.06+5×0.05+5×0.04=2.61H

2.55100

97.700R 2.61 0 002.61，因此压缩比为：2.611.15冗余度为：00r100X97.72.3％的冗余。哈夫曼编码的MATLAB实现matlabhumanff.mfunction[h,l]=huffman(p)iflength(find(p<0))~=0;error(”Inputisnotaprob.vector,thereisnegatibecomponent”);endifabs(sum(p)-1)>10e-10error(”Inputisnotaprob.vector,thesumofthecomponentisnotequalto1.”);endn=length(p); q=p;m=zeros(n-1,n);fori=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];endfori=1:n-1,c(i,:)=blanks(n*n);endc(n-1,n)=”0”;c(n-2,2*n)=”1”;fori=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”;forj=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));endmessagemessage函数，message函数的源代码为：functionr=message(x,n) x是概率分布，n是离散信源的分布值数目r=0;fori=1:nr=r-x(i)*log(x(i))/log(2);end此离散信源的平均信息量为”);r11的。如：13PU1 U13 16

U3

U4115

U51130huffmanmessage函数如下：clearall;p=[1/3,1/6,1/15,1/15,11/30] p=0.3333 0.1667 0.0667 0.0667 0.3667截图为：总 结关的技术。课本上的学问是机械的，抽象的。在本次课