霍夫曼编码的分析与实现.doc

通信1311 陈青云 刘倩 袁冬梅 PAGE 7 信息论与编码设计作业 霍夫曼编码的分析与实现 通信1311 刘倩 陈青云袁冬梅 目录 TOC \o 1-3 \h \z \u 一、设计内容 1 二、设计原理 2 1、霍夫曼编码步骤： 2 2、霍夫曼编码特点： 4 2.1最佳编码： 4 2.2霍夫曼的显著特点： 4 2.3霍夫曼编码的非唯一性 4 三、设计步骤 5 1、以框图形式画出哈霍夫曼码过程 5 2、计算平均码长、编码效率、冗余度。 5 四、霍夫曼编码的MATLAB实现: 6 1、MATLAB编程 6 2、运行结果及分析： 7 五.分工情况 8 霍夫曼编码的分析与实现 一、设计内容? ?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）将信源消息符号按其出现的概率大小依次排列： P1?≥?P2?≥?????≥?Pn?。 （2）取两个概率最小的字母分别配以0和1两个码元，并将这两个概率相加作为一个新的字母的概率，与未分配的二进制符号的字母重新排队。? （3）对重排后的两个概率最小符号重复步骤（2）的过程。? （4）不断继续上述过程，直到最后两个符号配以0和1为止。? （5）从最后一级开始，向前返回得到各个信源符号所对应的码元序列，即相应的码字?。 Huffman编码的程序流程图： 开始 开始 输入信源符号对应概率P（i）? 输入信源符号对应概率P（i） 否判断P（i）是否0 否 判断P（i）是否0 是 是 否判别概率总和是否=1 否 判别概率总和是否=1 是??? 是 对概率数组q升序排序 对概率数组q升序排序 用0，1表示概率最小的两个信源符号 用0，1表示概率最小的两个信源符号 将数组q前两项加和，得到新的概率序列 将数组q前两项加和，得到新的概率序列 否否判断信源符号是否只剩两个符号 否 否 判断信源符号是否只剩两个符号 ? 生成n-1行n列，每个元素含有n个字符的空白矩阵是 生成n-1行n列，每个元素含有n个字符的空白矩阵 是 进行Huffman编码，并完成码字分配 进行Huffman编码，并完成码字分配 计算一个Huffman码字的平均码长 计算一个Huffman码字的平均码长 结束计算信源熵和编码效率 结束 计算信源熵和编码效率  2、霍夫曼编码特点：? 2.1最佳编码： 能载荷一定的信息量，且码字的平均长度最短，可分离的变长的码字集合称为最佳变长码。为此必须将概率大的信息符号编以短的码字，概率小的符号编以长的码字，使得平均码字最短，为最佳编码方法。霍夫曼码是用用概率匹配的方法进行信源编码。 2.2霍夫曼的显著特点： 1.霍夫曼的编码方法保证了概率大的符号对应于短码，概率小的符号度对应于长码，充分利用了短码； 2. 霍夫曼是一种即时码：由于代表信源符号的节点都是终端节点，因此其编码不可能是其他终端节点对应的编码的前缀，即霍夫曼编码所得的码字为即时码。? ? 3.霍夫曼编码是一种分组码，各个信源符号都被映射成一组固定次序的码符号。? ? 4.霍夫曼编码是一种唯一可解的码，任何符号序列只能以一种方式译码。 注：它可以单个信源符号编码或用L较小的信源序列编码。但是应当注，要达到很高的效率仍然需要按长序列计算，这样才能使平均码字长度降低。编码过程中，当缩减信源的概率分布重新排列时，应使合并得到的概率和尽量处于高的位置，这样可使合并的元素重复编码次数减少，使短码得到充分利用。 2.3霍夫曼编码的非唯一性 霍夫曼编码方法得到的码并非是唯一的，造成并非唯一的原因是：（1）首先，每次对信源缩减时，赋予信源最后两个概率最小的符号，用0和1可以任意的，所以可以得到不同的霍夫曼码，但不会影响码字的长度。（2）对信源进行缩减时两个概率最小的符号合并后的概率与其他信源符号的概率相同时，这两者在缩减信源中进行概率排序，其位置放置次序是可以任意的，故会得到不同的霍夫曼码。此时将影响码字的长度，一般将合并的概率放在上面，这样可以获得较小的码方差。? ? 三、设计