《霍夫曼编码的分析与实现》由会员分享，可在线阅读，更多相关《霍夫曼编码的分析与实现（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 讲解：陈青云
