s=s+p(i); 9
H=H+(- p(i)*log2(p(i))); end
if (s<=0.999999||s>=1.000001) error('不符合分布概率') end
fori=1:N-1 for j=i+1:N if p(i) x=f1(1,N,p,1); fori=1:N L(i)=length(find(x(i,:))); l=l+p(i)*L(i); end n=H/l; fprintf('按概率降序排列的码子:\\n'); disp(x) fprintf('平均码长:\\n'); disp(l) fprintf('编码效率:\\n'); disp(n) function x=f1(i,j,p,r) global x; x=char(x); if(j<=i) return; else q=0; for t=i:j q=p(t)+q; y(t)=q; end for t=i:j v(t)=abs(y(t)-(q-y(t))); end for t=i:j if(v(t)==min(v)) for k=i:t x(k,r)='0'; 10 end for k=(t+1):j x(k,r)='1'; end d=t; f1(i,d,p,r+1); f2(d+1,j,p,r+1); f1(d+1,j,p,r+1); f2(i,d,p,r+1); else end end end return; function x=f2(i,j,p,r) global x; x=char(x); if(j<=i) return; else q=0; for t=i:j q=p(t)+q;y(t-i+1)=q; end for t=1:j-(i-1) v(t)=abs(y(t)-(q-y(t))); end for t=1:j-(i-1) if(v(t)==min(v)) d=t+i-1; for k=i:d x(k,r)='0'; end for k=(d+1):j x(k,r)='1'; end f2(d+1,j,p,r+1); f1(i,d,p,r+1); f2(i,d,p,r+1); f1(d+1,j,p,r+1); else end end end 11 实验四哈夫曼编码（2学时） 一、实验目的 1.掌握哈夫曼编码原理； 2.熟练掌握哈夫曼树的生成方法； 3.学会利用 MATLAB MATLABMATLABMATLABMATLAB实现 哈夫曼 编码 ； 4.提高独立进行算法编程的能力。 二、实验内容 1.用 MATLAB MATLABMATLABMATLABMATLAB实现 哈夫曼 哈夫曼 编码算法程序； 2.要求程序输出显示所有的码字以及编效率； 3.设计简单的输入界面（可以是文字提示信息），程序运行时用 设计简单的输入界面（可以是文字提示信息），程序运行时用 设计简单的输入界面（可以是文字提示信息），程序运行时用 设计简单的输入界面（可以是文字提示信息），程序运行时用 设计简单的输入界面（可以是文字提示信息），程序运行时用 户输入代表信源符号概率的向量；要对用进行合法性检查 户输入代表信源符号概率的向量；要对用进行合法性检查 ； 4.( 选做 )随机生成一幅图像， 随机生成一幅图像， 实现 哈夫曼 图像编码，比较前后 图像编码，比较前后 图片 大小。 三、实验仪器设备 1.计算机－系统最低配置 256M 内存、 P4 CPUCPUCPU； 2. MATLAB MATLABMATLABMATLABMATLAB编程软件。 编程软件。 四、实验原理 1.二进制 哈夫曼 编码的基本原理及算法 (1) 把信源符号集中的所有按概率从大到小排队 把信源符号集中的所有按概率从大到小排队 ； (2) 取概率最小的两个符号作为片叶子合并（缩减）到一节点 取概率最小的两个符号作为片叶子合并（缩减）到一节点 ； (3) 视此节点为新符号，其概率等于被合并（缩减）的两个之和参 视此节点为新符号，其概率等于被合并（缩减）的两个之和参 与概率排队 ； (4) 重复 (2)(3) (2)(3) 两步骤，直至全部符号都被合并（缩减）到根 两步骤，直至全部符号都被合并（缩减）到根 ； (5) 从根出发，对各分枝标记 从根出发，对各分枝标记 从根出发，对各分枝标记 0和 1。从根到叶的 路径就给出了各个码字。从根到叶的 路径就给出了各个码字编码和长 。 2.哈夫曼 树的编码原理 (1) 程序的输入：以一维数组形式要进行 程序的输入：以一维数组形式要进行 程序的输入：以一维数组形式要进行 程序的输入：以一维数组形式要进行 程序的输入：以一维数组形式要进行 程序的输入：以一维数组形式要进行 程序的输入：以一维数组形式要进行 程序的输入：以一维数组形式要进行 程序的输入：以一维数组形式要进行 程序的输入：以一维数组形式要进行 程序的输入：以一维数组形式 要进行 程序的输入：以一维数组形式要进行 程序的输入：以一维数组形式要进行 程序的输入：以一维数组形式要进行 程序的输入：以一维数组形式要进行 程序的输入：以一维数组形式要进行 程序的输入：以一维数组形式要进行 程序的输入：以一维数组形式要进行 程序的输入：以一维数组形式要进行 哈夫曼 哈夫曼 哈夫曼 编码的 信源符号编码的 信源符号编码的 信源符号编码的 信源符号编码的 信源符号编码的 信源符号编码的 信源符号编码的 信源符号概率，在运行该程序前显示文字提信息所要输入的矢量； 概率，在运行该程序前显示文字提信息所要输入的矢量； 概率，在运行该程序前显示文字提信息所要输入的矢量； 概率，在运行该程序前显示文字提信息所要输入的矢量； 然后对输入的概率矢量进行合法性判断，原则为：如果中存在 然后对输入的概率矢量进行合法性判断，原则为：如果中存在 然后对输入的概率矢量进行合法性判断，原则为：如果中存在 然后对输入的概率矢量进行合法性判断，原则为：如果中存在 然后对输入的概率矢量进行合法性判断，原则为：如果中存在 然后对输入的概率矢量进行合法性判断，原则为：如果中存在 然后对输入的概率矢量进行合法性判断，原则为：如果中存在 然后对输入的概率矢量进行合法性判断，原则为：如果中存在 然后对输入的概率矢量进行合法性判断，原则为：如果中存在 然后对输入的概率矢量进行合法性判断，原则为：如果中存在 然后对输入的概率矢量进行合法性判断，原则为：如果中存在 然后对输入的概率矢量进行合法性判断，原则为：如果中存在 然后对输入的概率矢量进行合法性判断，原则为：如果中存在 小于 0的项，则输入不合法提示重新；如果概率矢量求和大于 1，则输入也不合法，提示重新。 (2) 在输入的概率矩阵 p正确的前提条件下 ,对 p进行排序，并用矩阵 L记 录 p排序之前各元素的顺，然后将概率数组 p的前两项，即 概率最小的两个数加和，得到新一组序列重复以上过程后 概率最小的两个数加和，得到新一组序列重复以上过程后 概率最小的两个数加和，得到新一组序列重复以上过程后 概率最小的两个数加和，得到新一组序列重复以上过程后 概率最小的两个数加和，得到新一组序列重复以上过程后 概率最小的两个数加和，得到新一组序列重复以上过程后 概率最小的两个数加和，得到新一组序列重复以上过程后 概率最小的两个数加和，得到新一组序列重复以上过程后 概率最小的两个数加和，得到新一组序列重复以上过程后 概率最小的两个数加和，得到新一组序列重复以上过程后 概率最小的两个数加和，得到新一组序列重复以上过程后 概率最小的两个数加和，得到新一组序列重复以上过程后 概率最小的两个数加和，得到新一组序列重复以上过程后 得到一个记录概率加和过程的矩阵 p以及每次排序之前概率顺的矩阵 ； 12 (3) 新生成一个 n-1行 n列，并且每个元素含有 n个字符的空白矩阵，然后 进行 哈夫曼 编码。 五、实验步骤 1. 输入一个离散信源，并检查该是否完备集； 2. 使用 哈夫曼 编码原理进行 哈夫曼 程序编写 ； 3. 输出离散信源中每个符号的 哈夫曼 编码 及平均码长 和编码效率 ，并与手工 ，并与手工 运算的结果进行比较。 六、实验报告要求 1.按照本节内容后实验报告形式书写； 2.实验总结和心得要详细，可以根据自己情况写出建议。 七、实验注意事项 1.比较大小 在 MATLAB MATLABMATLABMATLABMATLAB中， 调用的是 sort 函数 ； 2.仔细理解、体会 哈夫曼 编码思想 。 八、思考题 比较香农编码、费诺哈夫曼并说出他们的优缺点？ 附录 1：实验报告样式： 实 验 报 告 班级： 姓名： 学号： 组别： 同组人： 课程名称： 实验室： 实验时间： （使用实验报告纸的，以上内容可按照实验报告纸格式填写） 实验四 哈夫曼编码 一、实验目的： 二、实验内容与原理： 三、实验器材（设备、元器件、软件工具、平台）： 四、实验步骤： 五、程序流程图： 六、实验数据及结果分析： 七、实验结论： 八、思考题： 九、编程、调试过程中遇到的问题及解决方法： 十、其他：实验总结、心得体会及对本实验方法、手段及过程的改进建议等。 附录 2：哈夫曼编码程序 ： clear all; close all; clc; 13 n=input('输入信源符号数:'); p=zeros(1,n); fori=1:n p(1,i)=input('输入信源符号概率:'); end q=p; if sum(p)<1||sum(p)>1 error('输入概率不符合概率分布') end a=zeros(n-1,n); n=length(p); fori=1:n-1 [q,l]=sort(q); a(i,:)=[l(1:n-i+1),zeros(1,i-1)]; q=[q(1)+q(2),q(3:n),1]; end fori=1:n-1 c(i,1:n*n)=blanks(n*n); end c(n-1,n)='1'; c(n-1,2*n)='0'; fori=2:n-1 c(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