2022年2022年霍夫曼编码的matlab实现 2.pdf

《2022年2022年霍夫曼编码的matlab实现 2.pdf》由会员分享，可在线阅读，更多相关《2022年2022年霍夫曼编码的matlab实现 2.pdf（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、重庆交通大学信息科学与工程学院综合性设计性实验报告专 业班 级： 通信工程 2012 级 1 班学号：631206040118 姓名：王松实验所属课程：信息论与编码实验室 (中心)：软件与通信实验中心指 导 教 师 ：黄大荣2015 年 4 月名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 6 页 - - - - - - - - - 教师评阅意见：签名：年月日实验成绩：霍夫曼编码的 matlab 实现一、实验目的和要求。利用哈夫曼编码进行通信可以大大提高信道的利用率，缩短

2、信息传输的时间，降低传输成本 。本实验用 Matlab 语言编程实现霍夫曼（ Huffman）编码。二、实验原理 。霍夫曼（ Huffman）编码算法是满足前缀条件的平均二进制码长最短的编-源输出符号， 而将较短的编码码字分配给较大概率的信源输出。算法是：在信源符号集合中， 首先将两个最小概率的信源输出合并为新的输出，其概率是两个相应输出符号概率之和。 这一过程重复下去， 直到只剩下一个合并输出为止，这个最后的合并输出符号的概率为1。这样就得到了一张树图，从树根开始，将编码符号1 和0 分配在同一节点的任意两分支上，这一分配过程重复直到树叶。 从树根到树叶途经支路上的编码最后就构成了一组异前置

3、码，就是霍夫曼编码输出。离散无记忆信源：例如Uu1u2u3u4u5P( U) = 0.4 0.2 0.2 0.1 0.1 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 6 页 - - - - - - - - - 码字 Wi信符 si概率P(si) 编码过程第一次第二次第三次W1=0 W2=10 W3=111 W4=1101 W5=1100 S1S2 S3S4S50.4 0.2 0.2 0.1 0.1 0.4 0.2 0.2 1 0.2 0 0.4 0.4 1 0.2 0

4、0.6 10.4 0 1A(1) 0 通过上表的对信源缩减合并过程，从而完成了对信源的霍夫曼编码。三、实验步骤分为两步，首先是码树形成过程： 对信源概率进行合并形成编码码树。然后是码树回溯过程：在码树上分配编码码字并最终得到霍夫曼编码。1、码树形成过程：将信源概率按照从小到大顺序排序并建立相应的位置索引。然后按上述规则进行信源合并，再对信源进行排序并建立新的位置索引，直到合并结束。在这一过程中每一次都把排序后的信源概率存入矩阵G 中，位置索引存入矩阵 Index 中。这样，由排序之后的概率矩阵G以及索引矩阵 Index就可以恢复原概率矩阵 P了，从而保证了回溯过程能够进行下去。2、码树回溯过程

5、 ：在码树上分配编码码字并最终得到Huffman 编码。从索引矩阵 M 的末行开始回溯。(1) 在Index 的末行 2元素位置填入 0和1。(2) 根据该行索引 1 位置指示，将索引 1 位置的编码（ 1）填入上一行的第一、第二元素位置，并在它们之后分别添加0和 1。(3) 将索引不为 1的位置的编码值（ 0）填入上一行的相应位置（第3 列）。(4) 以Index 的倒数第二行开始向上， 重复步骤 (1) (3)，直到计算至 Index的首行为止。四、程序代码：% 取得信源概率矩阵 , 并进行合法性判断clear; P=input(请输入信源概率向量 P=); N=length(P); fo

6、r component=1:1:N 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 6 页 - - - - - - - - - if(P(component)0.0001) error(信源概率之和必须为 1); end % 建立各概率符号的位置索引矩阵Index, 利于编码后从树根进行回溯, 从而得出对应的编码Q=P Index=zeros(N-1,N); %初始化 Index for i=1:N-1 Q,L=sort(Q); Index(i,:)=L(1:N-i+1)

7、,zeros(1,i-1); G(i,:)=Q; Q=Q(1)+Q(2),Q(3:N),1; %将Q 中概率最小的两个元素合并，元素不足的地方补1 end % 根据以上建立的 Index 矩阵，进行回溯，获取信源编码for i=1:N-1 Char(i,:)=blanks(N*N);%初始化一个由空格符组成的字符矩阵N*N,用于存放编码end % 从码树的树根向树叶回溯，即从G 矩阵的最后一行按与 Index 中的索引位置的对应关系向其第一行进行编码Char(N-1,N)=0;%G 中的N-1行即最后一行第一个元素赋为0，存到 Char中N-1行的N 列位置Char(N-1,2*N)=1;%G

8、中的N-1行即最后一行第二个元素赋为1，存到 Char中N-1行的2*N列位置% 以下从 G 的倒数第二行开始向前编码for i=2:N-1 Char(N-i,1:N-1)=Char(N-i+1,N*(find(Index(N-i+1,:)=1) -(N-2):N*(find(Index(N-i+1,:)=1); % 将Index 后一行中索引为 1的编码码字填入到当前行的第一个编码位置 Char(N-i,N)=0; %然后在当前行的第一个编码位置末尾填入0 Char(N-i,N+1:2*N-1)=Char(N-i,1:N-1); %将G 后一行中索引为 1的编码码字填入到当前行的第二个编码位

9、置 Char(N-i,2*N)=1; %然后在当前行的第二个编码位置末尾填入1 for j=1:i-1 %内循环作用：将Index 后一行中索引不为 1处的编码按照左右顺序填入当前行的第3个位置开始的地方 , 最后计算到 Index 的首行为止Char(N-i,(j+1)*N+1:(j+2)*N)=Char(N-i+1,N*(find(Index(N-i+1,:)=j+1)-1)+1:N*find(Index(N-i+1,:)=j+1); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - -

10、第 4 页，共 6 页 - - - - - - - - - end end %Char中第一行的编码结果就是所需的Huffman 编码输出，通过 Index 中第一行索引将编码对应到相应概率的信源符号上。 for i=1:N Result(i,1:N)=Char(1,N*(find(Index(1,:)=i)-1)+1:find(Index(1,:)=i)*N); end %打印编码结果 String=信源概率及其对应的 Huffman编码如下 ; disp(String);disp(P);disp(Result); 五、对比分析，通过给给定不同的信源，对结果进行分析对比验证，并得出相应分分析

11、报告。以0.1,0.2,0.3,0.2,0.1,0.1为例：运行程序，结果如下以0.3 0.3 0.2 0.1 0.1为例：运行程序，结果如下名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 6 页 - - - - - - - - - 分析：由上图可知程序已完成了Huffman编码的功能，但是霍夫曼编码是不唯一的 . 因为： 信源符号合并中遇到最小概率相同的情况时可任意选择来做合并；在码树分配编码码字的时候1 和0 的位置可以是任意的。六：提交实验报告。1、在该实验的过程中

12、，利用一个矩阵记录每次排序前概率的所在位置，是该实验的关键，在编码的过程中利用该矩阵就能比较容易进行huffman编码。2、通过这个实验， 对huffman编码的具体实现原理了解的更加深刻，在实验的过程中也遇到了一些问题， 通过查找资料和相关书籍得到了解决，通过此次试验，了解了 Huffman编码的特点， 能够运用 Huffman编码的基本原理及编码算法的来设计与实现程序。收获颇多，为以后更进一步学习奠定了基础, 总的来说，在完成该实验的过程中， 学到了比较多的知识， 包括使对一些 matlab 语句的掌握的更加熟练，完成一个算法必须要有一个整体的把握等等。3、通过本次课程设计， 我对二叉树和 huffman编码树有了更深的了解， 在做课程设计的过程中我掌握了二元huffman编码树的构造方法，哈夫曼编码是一种变长的编码方案。 它由最优二叉树既哈夫曼树得到编码，码元内容为到根结点的路径中与父结点的左右子树的标识。 所以哈夫曼在编码在数字通信中有着重要的意义。可以根据信源符号的使用概率的高低来确定码元的长度。既实现了信源的无失真地编码，又使得编码的效率最高。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 6 页 - - - - - - - - -