信息论--第四章·第七节 霍夫曼码与其他编码方法.pptVIP

第4章 无失真信源编码 4.7 霍夫曼码和其他编码方法 教学要求 了解Shannon编码思想、Shannon-Fano算法、香农-费诺-埃里斯编码算法； 掌握Huffman编码方法。 Shannon算法 Shannon编码思想 ：按概率编码 Shannon编码举例 利用码树图法可得到其编码 Huffman码的特点 用概率匹配方法进行编码 概率大的符号对应于短码，概率小的符号对应于长码，充分利用了短码 缩减信源的最后两个码字总是最后一位不同，从而保证了Huffman码是即时码 r元Huffman算法 r=3,A:{0,1,2} 改进方法 在6个信源符号的后面再加一个概率为0的符号，记为s7’,同时有p(s7’)=0，这个符号称为虚假符号。将信源按7个符号进行三元编码 其码树图 改进的r元Huffman编码 对于离散信源S:{s1,s2,…,sq} P(S):{p(s1),p(s2),……p(sq)} A;{a1,a2,…ar}; 第一次缩减信源S(1) ，每次将减少(r-1)个符号，分别形成S(2),S(3)… 如果i=r-{q-[r-1] }！＝０,其中 表示缩减次数,应当在原始信源中加上m个概率为0的虚假信源符号，然后进行编码，将得到最佳码 。 上例 ，q=6, r=3, =2 Fano编码举例 平均码长为L=2.64 信道码元/信源符号。 H(S)=2.55 bit/信源符号。 　 本例中费诺编码有较高的编码效率。费诺码比较适合于每次分组概率都很接近的信源。特别是对每次分组概率都相等的信源进行编码时，可达到理想的编码效率。 如果将信源做n次扩展后再进行编码，可以进一步提高编码效率 小结 重点：香农-费诺-埃里斯编码算法；Huffman编码。 难点：改进的r元Huffman算法。 思考题、作业： 思考：课本P188 10题、18题、21题。 作业：P188 T4.11,T4.12，T4.17 首先是速率匹配问题 其次是差错扩散问题 第三是霍夫曼码需要查表来进行编译码。 信源统计特性未知时，怎么办？可采用所谓通用编码的方法来解决。 Huffman码编码应用中的一些问题 4.7霍夫曼码和其他编码方法 * 它是满足Kraft不等式的一种直接的应用 例：一个离散信源S:{s1,s2,s3,s4} p(S):{1/2,1/4,1/8,1/8} 这时有：L1=log2=1; L2=log4=2; L3=L4=log8=3; 4.7霍夫曼码和其他编码方法 这个例子其编码效率为1，即为最佳码。但这种方法对于多数情况下是不能实现最佳码的，而且编码效率比较低。 4.7霍夫曼码和其他编码方法 L1=1, L2=2, L3=L4=3; Huffman码 将信源符号按概率从大到小的顺序排列，令 给两个概率最小的信源符号sn-1和sn各分配一个码元“0”和“1”，并将这两个信源符号合并成一个新符号，并用这两个最小的概率之和作为新符号的概率，结果得到一个只包含(n－1)个信源符号的新信源。称为信源的第一次缩减信源，用S1表示。 将缩减信源S1的符号仍按概率从大到小顺序排列，重复步骤2，得到只含(n－2)个符号的缩减信源S2。 重复上述步骤，直至缩减信源只剩两个符号为止，此时所剩两个符号的概率之和必为1。然后从最后一级缩减信源开始，依编码路径向前返回，就得到各信源符号所对应的码字。 编码步骤如下： 4.7霍夫曼码和其他编码方法 0 1 0 1 0 1 0 1 Huffman码 4.7霍夫曼码和其他编码方法 0 1 0 1 0 1 0 1 码符号/信源符号 Huffman码 4.7霍夫曼码和其他编码方法 0 1 0 1 0 1 0 1 码符号/信源符号 Huffman码 4.7霍夫曼码和其他编码方法 讨论： 1) 两种方法平均码长相等。 2) 计算两种码的码长方差： 第二种方法编出的码码字长度变化较小，便于实现。 Huffman码 4.7霍夫曼码和其他编码方法 Huffman码 离散信源如下: 解：编码过程略，Huffman编码结果如下： 4.7霍夫曼码和其他编码方法 Huffman码 平均码长为 信源熵为 编码效率为 4.7霍夫曼码和其他编码方法 Huffman码 注意：霍夫曼编码后的码字不是惟一的。 1）每次对缩减信源两个概率最小的符号分配“0”或“1”码元是任意的,因此编码的结果是不唯一的；但0/1分配的上下顺序在整个编码过程中应保持一致，否则不能构成唯一可译码。 2）缩减信源时，若合并后的概率与其他概率相等，这几个概率的次序可任意排列，但得到的码字不相同,对应的码长也不相同,但平均码长也不变。 4.7霍夫曼码和其他编码方法