霍夫曼编码的分析与实现

1、信息论与编码设计作业霍夫曼编码的分析与实现通信 1311刘倩青云冬梅信 1311 陈青云 刘倩 袁冬梅1目录一、设计内容一、设计内容.1二、设计原理二、设计原理.21、霍夫曼编码步骤：、霍夫曼编码步骤：.22、霍夫曼编码特点：、霍夫曼编码特点：.42.1 最佳编码：.42.2 霍夫曼的显著特点：.42.3 霍夫曼编码的非唯一性.4三、设计步骤三、设计步骤.51、以框图形式画出哈霍夫曼码过程、以框图形式画出哈霍夫曼码过程.52、计算平均码长、编码效率、冗余度。、计算平均码长、编码效率、冗余度。.5四、霍夫曼编码的四、霍

2、夫曼编码的 MATLAB 实现实现:.61、MATLAB 编程编程.62、运行结果及分析：、运行结果及分析：.7五五.分工情况分工情况.8通信 1311 陈青云 刘倩 袁冬梅2霍夫曼编码的分析与实现霍夫曼编码的分析与实现一、设计内容一、设计内容 1、根据霍夫曼编码算法，考虑一个有多种可能的符号（各种符号发生的概率不同的信源）得到霍夫曼编码和码树； 2、 使用 MATLAB 进行编程，编写的函数具有通用性，理解每个函数的具体意义和适用范围，程序输出显示所有的码字，平均码长，编码效率。 例如:一个有 n 个符号的信源 X，各个符号出现的概率为：P:x1 x2 x3 x4 x5 x6例：P(X):0

3、.40，0.18，0.15，0.10，0.07，0.05，0.03，0.02进行霍夫曼编码，计算出平均码长、编码效率、冗余度。 二、设计原理二、设计原理1、霍夫曼编码步骤：、霍夫曼编码步骤：（1）将信源消息符号按其出现的概率大小依次排列： P1 P2 Pn 。（2）取两个概率最小的字母分别配以 0 和 1 两个码元，并将这两个概率相加作为一个新的字母的概率，与未分配的二进制符号的字母重新排队。 （3）对重排后的两个概率最小符号重复步骤（2）的过程。 （4）不断继续上述过程，直到最后两个符号配以 0 和 1 为止。 （5）从最后一级开始，向前返回得到各个信源符号所对应的码元序列，即相应的码字 。

4、通信 1311 陈青云 刘倩 袁冬梅3Huffman 编码的程序流程图：编码的程序流程图： 开始输入信源符号对应概率 P（i）判断 P（i）是否0判别概率总和是否=1对概率数组 q 升序排序用 0，1 表示概率最小的两个信源符号将数组 q 前两项加和，得到新的概率序列判断信源符号是否只剩两个符号生成 n-1 行 n 列，每个元素含有 n 个字符的空白矩阵进行 Huffman 编码，并完成码字分配计算一个 Huffman 码字的平均码长计算信源熵和编码效率结束否否否否是是是通信 1311 陈青云 刘倩 袁冬梅42、霍夫曼编码特点：、霍夫曼编码特点： 2.1 最佳编码：能载荷一定的信息量，且码字的

5、平均长度最短，可分离的变长的码字集合称为最佳变长码。为此必须将概率大的信息符号编以短的码字，概率小的符号编以长的码字，使得平均码字最短，为最佳编码方法。霍夫曼码是用用概率匹配的方法进行信源编码。2.2 霍夫曼的显著特点：1.霍夫曼的编码方法保证了概率大的符号对应于短码，概率小的符号度对应于长码，充分利用了短码；2. 霍夫曼是一种即时码：由于代表信源符号的节点都是终端节点，因此其编码不可能是其他终端节点对应的编码的前缀，即霍夫曼编码所得的码字为即时码。 3.霍夫曼编码是一种分组码，各个信源符号都被映射成一组固定次序的码符号。 4.霍夫曼编码是一种唯一可解的码，任何符号序列只能以一种方式译码。注：

6、它可以单个信源符号编码或用 L 较小的信源序列编码。但是应当注，要达到很高的效率仍然需要按长序列计算，这样才能使平均码字长度降低。编码过程中，当缩减信源的概率分布重新排列时，应使合并得到的概率和尽量处于高的位置，这样可使合并的元素重复编码次数减少，使短码得到充分利用。2.3 霍夫曼编码的非唯一性霍夫曼编码方法得到的码并非是唯一的，造成并非唯一的原因是：（1）首先，每次对信源缩减时，赋予信源最后两个概率最小的符号，用 0 和 1 可以任意的，所以可以得到不同的霍夫曼码，但不会影响码字的长度。（2）对信源进行缩减时两个概率最小的符号合并后的概率与其他信源符号的概率相同时，这两者在缩减信源中进行概率

7、排序，其位置放置次序是可以任意的，故会得到不同的霍夫曼码。此时将影响码字的长度，一般将合并的概率放在上面，这样可以获得较小的码方差。 通信 1311 陈青云 刘倩 袁冬梅5三、设计步骤三、设计步骤 1、以框图形式画出哈霍夫曼码过程、以框图形式画出哈霍夫曼码过程 霍夫曼编码过程：哈夫曼码树：2、计算平均码长、编码效率、冗余度。、计算平均码长、编码效率、冗余度。 在变字长编码时每个符号的平均码长为： 503. 0504. 0407. 0408. 041 . 0218. 022 . 023 . 0)(81iiilxpL=2.71 码元/符号平均信息量就是信息熵为：8)(log)()(iixpxPXH

8、通信 1311 陈青云 刘倩 袁冬梅6=0.3log（0.3）+0.2log（0.2）+0.18log（0.18）+0.1log(0.1)+0.08log(0.08)+0.07log(0.07)+0.04log(0.04)+0.03log(0.03)=2.66 码元/符号 编码效率为： 98. 071. 266. 2)(LXH 冗余度为:02. 098. 011r四、霍夫曼编码的四、霍夫曼编码的 MATLAB 实现实现: 1、MATLAB 编程编程 p=input(请输入数据:) %提示输入界面 n=length(p); %N 取输入行向量 P 的长度，即需要编码元素个数。for i=1:n

9、if p(i)1 %IF 语句判断输入矩阵的概率和是否为合理值 1fprintf(n 霍夫曼码中概率总和不能大于 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）

10、列数组 C，每行可看作N 个段，每段长为 N，记录一个码字（每个码字的长度不会超过 N）。c(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 %根据之前的规则，在分支

11、的第一个元素最后补 0c(n-i,n+1:2*n-1)=c(n-i,1:n-1) c(n-i,2*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

12、码字的分配 %FOR 循环找到其余的本行在下一行对应的码字，该码字保持不变。循环结 束后，C 矩阵第一行的 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); %计算信源熵 fprintf(n 信源熵为:n); hh fprintf(n 编码效率为:n); t=hh/l %计算编码效率哈夫曼.m 运用典型的 IF 和 FOR 控制流循环语句，该程序包括两个 IF 控制流和 5 个 FOR 循环结构。2、运行结果及分析：、运行结果及分析：通信 1311 陈青云 刘倩 袁冬梅8 完成编写设计后，在 MATLAB 中运行并验证结果，首