实验二霍夫曼编码

1、（2015 2016学年第1学期）课程名称：信息论与编码基础姓名：陈明明学院：工学院专业：计算机年级：2014级学号：2144022251进入实验室 时间进入时仪器 设备状况离开实验室 时间离开时仪器 设备状况机器号14:55正常16:30正常46实验项目名称霍夫曼编码2016 年5月16 日 第 7-8节 综合楼 Z525 号室、实验目的1. 进一步深入理解Huffman编码算法的原理;2. 提高独立进行算法编程的能力。、实验内容1. 用Matlab实现二进制Huffman编码算法程序；2. 要求程序输出显示所有的码字以及编码效率；3. 设计简单的输入界面(可以是简单的文字提示信息)，程序运

2、行时提示用户输入代表信 源符号概率的向量；要对用户输入的概率向量进行合法性检查。【二进制Huffman编码程序实现】(1)程序的输入：以一维数组的形式输入要进行huffman编码的信源符号的概率，在运行该 程序前，显示文字提示信息，提示所要输入的概率矢量；然后对输入的概率矢量进行合法性 判断，原则为：如果概率矢量中存在小于 0的项，则输入不合法，提示重新输入；如果概率 矢量的求和大于1,则输入也不合法，提示重新输入。(2) huffman编码具体实现原理:1) 在输入的概率矩阵p正确的前提条件下，对p进行排序，并用矩阵L记录p排序之 前各元素的顺序，然后将排序后的概率数组p的前两项，即概率最小

3、的两个数加和，得到新 的一组概率序列，重复以上过程，最后得到一个记录概率加和过程的矩阵 p以及每次排序之 前概率顺序的矩阵a。2)新生成一个n-1行n列，并且每个元素含有n个字符的空白矩阵，然后进行 huffman编 码：将c矩阵的第n-1行的第一和第二个元素分别令为 0和1 (表示在编码时，根节点之 下的概率较小的元素后补0，概率较大的元素后补1，后面的编码都遵守这个原则)然后对n-i-1的第一、二个元素进行编码，首先在矩阵a中第n-i行找到值为1所在的位置，然后在c矩阵中第n-i行中找到对应位置的编码（该编码即为第n-i-1行第一、二 个元素的根节点），则矩阵c的第n-i行的第一、二个元素

4、的n-1的字符为以上求得的编码 值，根据之前的规则，第一个元素最后补0,第二个元素最后补1,则完成该行的第一二个元素的编码，最后将该行的其他元素按照“矩阵 c中第n-i行第j+1列的值等于对应于a矩阵中第 n-i+1行中值为j+1的前面一个元素的位置在c矩阵中的编码值”的原则进行赋值，重复以 上过程即可完成huffman编码。三、实验过程及结果（包括源程序和计算步骤）p=input（请输入概率矢量:）;n=len gth（p）;for i=1:nif p（i）0fprintf（n概率矢量中存在小于0的项，输入不合法，请重新输入n）;p=input（ 请输入概率矢量:）;endendif abs

5、（sum（p）-1）0fprintf（ n概率矢量的求和大于1，输入不合法，请重新输入!n）;p=input（请输入概率矢量:）;endq=p;a=zeros （n-1, n）;for i=1:n-1q,l=sort(q)a(i,:)二1(1: n-i+1),zeros(1,i-1)q=q(1)+q(2) ,q(3: n),1;endfor i=1:n-1c(i,1: n*n)二bla nks(n*n);endc(n-1, n)二O;c(n-1,2*n)二1;for i=2:n-1c(n-i,1: n-1)=c( n-i+1, n*(fi nd(a( n-i+1,:)=1)-( n-2): n

6、*(fi nd(a( n-i+1, :)=1)c(n-i, n)二 0c(n-i, n+1:2* n-1)=c( n-i,1: n-1)c( n-i,2* n)二1for j=1:i-1c(n-i,(j+1)* n+1:(j+2)* n)=c( n-i+1, n*(fi nd(a( n-i+1,:)=j+1)-1)+1: n*find(a( n-i+1,:)=j+1)endend for i=1:n h(i,1: n)=c(1, n*(fi nd(a(1,:)=i)-1)+1:fi nd(a(1,:)=i)* n) ll(i)=le ngth(fi nd(abs(h(i,:)=32)endl=sum(p.*ll);fprintf( n 霍夫曼编码:n);hhh=sum(p.*(-log2(p);fprintf( n霍夫曼编码效率:n);t=hh/l靑输入跟率矢豊0. 350. 250. 15 0. 130. OS 0.05J1 =0. 05000,08000.12000, 1500山 2胡00,35CQ1 =6D4321电6543210000C00000c00000c00000c0OLIQ0111QIC0010LL010Oil00101100Oi10IL10110011LO00OLOO