《霍夫曼编码的分析与实现》由会员分享,可在线阅读,更多相关《霍夫曼编码的分析与实现(9页珍藏版)》请在金锄头文库上搜索。
1、信息论与编码设计作业霍夫曼编码的分析与实现通信 1311刘倩 13200119132陈青云 13200119131袁冬梅 13200119128通信 1311 陈青云 刘倩 袁冬梅1目录一、设计内容 .1二、设计原理 .21、霍夫曼编码步骤: .22、霍夫曼编码特点: .42.1 最佳编码: .42.2 霍夫曼的显著特点: .42.3 霍夫曼编码的非唯一性 .4三、设计步骤 .51、以框图形式画出哈霍夫曼码过程 .52、计算平均码长、编码效率、冗余度。 .5四、霍夫曼编码的 MATLAB 实现: .61、MATLAB 编程 .62、运行结果及分析: .7五.分工情况 .8通信 1311 陈青云
2、 刘倩 袁冬梅2霍夫曼编码的分析与实现一、设计内容 1、根据霍夫曼编码算法,考虑一个有多种可能的符号(各种符号发生的概率不同的信源)得到霍夫曼编码和码树; 2、 使用 MATLAB 进行编程,编写的函数具有通用性,理解每个函数的具体意义和适用范围,程序输出显示所有的码字,平均码长,编码效率。 例如:一个有 n 个符号的信源 X,各个符号出现的概率为:P:x1 x2 x3 x4 x5 x6例:P(X):0.40,0.18,0.15,0.10,0.07,0.05,0.03 ,0.02进行霍夫曼编码,计算出平均码长、编码效率、冗余度。 二、设计原理1、霍夫曼编码步骤:(1)将信源消息符号按其出现的概
3、率大小依次排列:P1 P2 Pn 。(2)取两个概率最小的字母分别配以 0 和 1 两个码元,并将这两个概率相加作为一个新的字母的概率,与未分配的二进制符号的字母重新排队。 (3)对重排后的两个概率最小符号重复步骤(2)的过程。 (4)不断继续上述过程,直到最后两个符号配以 0 和 1 为止。 (5)从最后一级开始,向前返回得到各个信源符号所对应的码元序列,即相应的码字 。通信 1311 陈青云 刘倩 袁冬梅3Huffman 编码的程序流程图:开始输入信源符号对应概率 P(i )判断 P(i)是否0判别概率总和是否1 %IF 语句判断输入矩阵的概率和是否为合理值 1fprintf(n 霍夫曼码
4、中概率总和不能大于 1!n); p=input(请重新输入数据:) end q=p; a=zeros(n-1,n); %生成一个 n-1 行 n 列的数组, 用来记录每行最小两概率叠加后概率排列 次序。for i=1:n-1 % 第一个 FOR 循环确定概率大小值的排列,得到 a 数组 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 for i=1:n-1 %第二个 FOR 循环生成一个 N-1 行、N2(NN)列数组 C,每行可看作N 个段,每段长为 N,记录一个码字(每个码字的长度不会超过 N)。c(
5、i,1:n*n)=blanks(n*n); end c(n-1,n)=0; % 给 C 矩阵的 N-1 行的第一个段赋值 0。 通信 1311 陈青云 刘倩 袁冬梅7c(n-1,2*n)=1;%第二个段赋值 1。(这两个码字对应编码中最后相加为一的两个概率。)for i=2:n-1 % 主要的程序,循环 N-2 次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) c(n-i,n)=0 %根据之前的规则,在分支的第一个元素最后补 0c(n-i,n+1:2*n-1)=c(n-i,1:n-1) c(n-i,2
6、*n)=1 %根据之前的规则,在分支的第一个元素最后补 1%决定矩阵 C 从倒数第二行开始到第一行的每段的码字值。每一行值都从下一行值得到,找到在下一行码字中相加本行最 小两个概率得到的概率的对应码字,本行两个最小概率对应码字分别为此码字最后加“0” ,加“1” 。 for j=1:i-1 c(n-i,(j+1)*n+1:(j+2)*n)=c(n-i+1,n*(find(a(n-i+1,:)=j+1)-1)+1:n*find(a(n-i+1,:)=j+1) end end %完成 huffman 码字的分配%FOR 循环找到其余的本行在下一行对应的码字,该码字保持不变。循环结 束后,C 矩阵第
7、一行的 N 段对应输入 N 个概率所对应符号的码字。该码字按 码字长短排列for i=1:n h(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 编码的长度 end %第五个 FOR 循环根据 M 矩阵第一行记录的概率排序位置分配给每个概率对 应符号的码字。l=sum(p.*ll); %计算平均码长 fprintf(n Huffman 编码结果为:n); hfprintf(n 编码的平均码长为:n); l hh=sum(p.*(-log2(p)
8、; %计算信源熵 fprintf(n 信源熵为 :n); hh fprintf(n 编码效率为 :n); t=hh/l %计算编码效率哈夫曼.m 运用典型的 IF 和 FOR 控制流循环语句,该程序包括两个 IF 控制流和 5 个 FOR 循环结构。2、运行结果及分析:通信 1311 陈青云 刘倩 袁冬梅8完成编写设计后,在 MATLAB 中运行并验证结果,首先输入概率向量: p=0.30,0.20,0.18,0.10,0.08,0.07,0.04,0.03 回车即可得到执行的结果,编码长度为 L=2.7100,H(X)= 2.6606,结果如上图所得的结果与实际预测的理论结果L=2.71,H(X)=2.66 。五.分工情况资料查找:袁冬梅、刘倩、陈青云MATLAB 实现:陈青云报告制作:刘倩、陈青云Ppt 制作:袁冬梅、刘倩Ppt 讲解:陈青云