第4章 离散无记忆信源无失真编码 4.5.1.pdfVIP

4.5 变长编码方法 变长编码采用非续长码； •力求平均码长最小，此时编码效率最高，信 源的冗余得到最大程度的压缩； •对给定的信源，使平均码长达到最小的编码 方法称为最佳编码，编出的码称为最佳码； •三种变长编码方法：霍夫曼编码、费诺编码 以及香农编码； •霍夫曼编码是真正意义下的最佳编码。 1 4.5.1 霍夫曼编码 二进制霍夫曼编码过程如下： (1)将信源符号按概率大小排序； (2)对概率最小的两个符号求其概率之和，同 时给两符号分别赋予码元 “0”和 “1”； (3)将 “概率之和”当作一个新符号的概率， 与剩下符号的概率一起，形成一个缩减信 源，再重复上述步骤，直到 “概率之和” 为1为止； (4)按上述步骤实际上构造了一个码树，从树 根到端点经过的树枝即为码字。 2 U  u1 u2 u3 u4 u5 u6 u7    2进制霍夫曼编码。 P   1 1 1 1 1 1 1   U  2 3 4 5 6 6  2 2 2 2 2 2 2  码元集：X={0, 1} 符号 概率 码字 码长 ui P (u ) i W l i i u 1 2 1 1 1 1 u2 1 22 1 1.00 01 2 1 2 u3 1 23 1 1 1 22 0 001 3 u4 1 24 1 23 0 0001 4 5 1 u 1 2 1 24 0 00001 5 5 1 u 1 26 1 25 0 000001 6 6 0 u7 1 26 0 000000 6 1 1 1 1 1 1 1 63 H (