《信息论与编码课程大作业二进制哈夫曼编码.doc》由会员分享,可在线阅读,更多相关《信息论与编码课程大作业二进制哈夫曼编码.doc(7页珍藏版)》请在金锄头文库上搜索。
1、 信息论与编码课程大作业 题 目: 二进制哈夫曼编码 学生姓名: 学 号: 2010020200 专业班级: 2010级电子信息班 2013年 5月 18日 二进制哈夫曼编码1、二进制哈夫曼编码的原理及步骤1、1信源编码的计算设有N个码元组成的离散、无记忆符号集,其中每个符号由一个二进制码字表示,信源符号个数n、信源的概率分布P=p(si),i=1,.,n。且各符号xi的以li个码元编码,在变长字编码时每个符号的平均码长为 ;信源熵为: ;唯一可译码的充要条件: ; 其中m为码符号个数,n为信源符号个数,Ki为各码字长度。 构造哈夫曼数示例如下图所示。1.00000000 0.400.60 0
2、.300.300.150.150.090.60 0.030.030.040.051、2 二元霍夫曼编码规则 (1)将信源符号依出现概率递减顺序排序。 (2)给两个概率最小的信源符号各分配一个码位“0”和“1”,将两个信源符号合并成一个新符号,并用这两个最小的概率之和作为新符号的概率,结果得到一个只包含(n-1)个信源符号的新信源。称为信源的第一次缩减信源,用s1 表示。(3)将缩减信源 s1 的符号仍按概率从大到小顺序排列,重复步骤(2),得到只含(n-2)个符号的缩减信源s2。(4)重复上述步骤,直至缩减信源只剩两个符号为止,此时所剩两个符号 的概率之和必为 1,然后从最后一级缩减信源开始,
3、依编码路径向前返回,就得到各信源符号所对应的码字。1、3 二元哈夫曼编码流程图如下图所示。 开始 等待数据输入判断输入的概 率是否小于零 是 结束 显示结果 计算码长 生成一个n - 1行n列的数组判断概率和是 否大于1 是按照哈弗曼的编码规则进行编码 计算信源熵 计算编码效率2、二元哈夫曼编码程序p=input(please input a number:) %提示输入界面n=length(p);for i=1:nif p(i)0fprintf(n The sum of the probabilities in huffman can more than 1!n);p=input(pleas
4、e input a number:) %如果输入的概率数组总和大于 1,则重endq=p;a=zeros(n-1,n); %生成一个 n-1 行 n 列的数组 for i=1:n-1q,l=sort(q); %对概率数组q进行从小至大的排序,并且用l数组返回一个q排序前的顺序编号a(i,:)=l(1:n-i+1),zeros(1,i-1); %由数组 l 构建一个矩阵,该矩阵表明概率合并q=q(1)+q(2),q(3:n),1; %将排序后的概率数组 q 的前两项,即概率最小的两endfor i=1:n-1c(i,1:n*n)=blanks(n*n); endc(n-1,n)=0; %由于a矩
5、阵的第n-1行的前两个元素为进行huffman编码加和运算时所得的最c(n-1,2*n)=1;for i=2:n-1c(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; %根据之前的规则,在分支的第一个元素最后补 0c(n-i,n+1:2*n-1)=c(n-i,1:n-1); c(n-i,2*n)=1; %根据之前的规则,在分支的第一个元素最后补 1for j=1:i-1c(n-i,(j+1)*n+1:(j+2)*n)=c(n-i+1,n*(find(a(n-i+1,:)=j+1)
6、-1)+1:n*find(a(n-i+1,:)=j+ 1);endend %完成 huffman 码字的分配 for i=1:nh(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 编码的长度enddisp(二元霍夫曼编码平均码长)l=sum(p.*ll) %计算平均码长%fprintf(n huffman code:n);hdisp(信源熵)hh=sum(p.*(-log2(p) %计算信源熵%fprintf(n the huffman e
7、ffciency:n);disp(编码效率)t=hh/l %计算编码效率3、运行结果及分析 当输入数据0.01,0.02,0.03,0.04,0.10,0.15,0.20,0.25,0.20时3、1运行结果:please input a number:0.01,0.02,0.03,0.04,0.10,0.15,0.20,0.25,0.20p = Columns 1 through 5 0.0100 0.0200 0.0300 0.0400 0.1000 Columns 6 through 9 0.1500 0.2000 0.2500 0.2000二元霍夫曼编码平均码长l = 2.7400h =
8、 1110100 1110101 111011 11100 1111 110 00 10 01信源熵hh = 2.6883编码效率t = 0.98113、2分析: 1、在哈弗曼编码的过程中,对缩减信源符号按概率有大到小的顺序重新排列,应使合并后的新符号尽可能排在靠前的位置,这样可使合并后的新符号重复编码次数减少,使短码得到充分利用。 2、哈弗曼编码效率相当高,对编码器的要求也简单得多。 3、哈弗曼它保证了信源概率大的符号对应于短码,概率小的符号对应于长码,每次缩减信源的最后两个码字总是最后一位码元不同,前面的各位码元都相同,每次缩减信源的最长两个码字有相同的码长。 4、哈弗曼的编法并不一定是唯
9、一的。4、体会 此次设计用matlab编程实现哈夫曼对信源无失真编码。由于课本知识点的不太理解,一点都不知道编码的过程,后来通过阅读课本、网上查阅资料,最后才对本次设计有了一定的理解,详细理解了哈夫曼的具体编码过程。经过理解,发现这种编码其实挺简单的,最重要的是怎样用程序把他实现,这对我们的编程能力也是一次考验。设计要求中要求计算信源熵,这又考察了现代通信原理的知识。所以这次设计所设计的知识面广,有利于我们对相关知识进一步加深、巩固。更加深刻的感觉到哈夫曼编码能够大大提高通信的效率 通过这次设计,让我明白,在平时的学习中,对于每一个知识点都不能一知半解,否则在具体的实际运用中就会现“原形”。比
10、如这次哈夫曼编码,如果我们只读一下它的编码过程的步骤,不实际举一个例子来验证,我们就很有可能在很多地方犯错。所以需要我们在阅读课本的时候还要仔细思考课本有关编码的示例,这对于我们掌握课本知识尤其重要的。这次设计编程的思路,编辑,调试等让我明白编程时一定要保持清醒的头脑,有严谨的思维才能将实验要求实现得完整;调试过程会发现很多问题,这时不能烦躁,要耐心的去发现问题,不断掌握matlab软件的各种调试方法。此次的实践又是对我的一次警醒,要有认真的态度,才有可能做好每一件事的!最后非常感谢一直给我教导的老师和帮助同学们,他们的支持和鼓励让我在遇到挫折时能够战胜它,也让我成功了完成了这次课程设计。今后我要更加努力的学习专业知识,提高自我的能力!