《信息理论与编码》课程教学课件（讲稿）第4章 离散无记忆信源无失真编码 4.5 变长编码方法 4.5.1 霍夫曼编码

4.5变长编码方法变长编码采用非续长码：力求平均码长最小，此时编码效率最高，信源的允余得到最大程度的压缩；对给定的信源，使平均码长达到最小的编码方法称为最佳编码，编出的码称为最佳码三种变长编码方法：霍夫曼编码、费诺编码以及香农编码霍夫曼编码是真正意义下的最佳编码

1 4.5 变长编码方法 变长编码采用非续长码； •力求平均码长最小，此时编码效率最高，信 源的冗余得到最大程度的压缩； •对给定的信源，使平均码长达到最小的编码 方法称为最佳编码，编出的码称为最佳码； •三种变长编码方法：霍夫曼编码、费诺编码 以及香农编码； •霍夫曼编码是真正意义下的最佳编码

4.5.1霍夫曼编码二进制霍夫曼编码过程如下：(1)将信源符号按概率大小排序：(2)对概率最小的两个符号求其概率之和，同时给两符号分别赋予码元“0"和“1”；(3)将“概率之和”当作一个新符号的概率，与剩下符号的概率一起，形成一个缩减信源，再重复上述步骤，直到“概率之和”为1为止；(4)按上述步骤实际上构造了一个码树，从树根到端点经过的树枝即为码字

2 4.5.1 霍夫曼编码 二进制霍夫曼编码过程如下： (1)将信源符号按概率大小排序； (2)对概率最小的两个符号求其概率之和，同 时给两符号分别赋予码元“0”和“1”； (3)将“概率之和”当作一个新符号的概率， 与剩下符号的概率一起，形成一个缩减信 源，再重复上述步骤，直到“概率之和” 为1为止； (4)按上述步骤实际上构造了一个码树，从树 根到端点经过的树枝即为码字

uuzususu.ususU2进制霍夫曼编码1111111Pu2223242526262码元集：X=0,1)码长码字符号概率uiP(u,)W.li1/2u1.001/22uz1/211/23us01/221/24u1/2301/2501/24us1/251/26us01/26u0品63H(U)X6+×6=X1=100%NeP62.22622322xlog2ilogr码元/符号

3 符号 概率 码字 Wi 码长 l i 1 1 01 2 001 3 0001 4 00001 5 000001 6 000000 6 ui u 1 2 1 u2 u3 u4 u5 u6 u7 ( ) P ui 4 1 25 1 26 1 26 1 22 1 23 1 2 4 1 2 1 2 2 1 2 3 1 2 5 1 2 0 0 0 0 0 0 1 1 1 1 1 1 1 00 . 1 2 3 4 5 6 7 2 3 4 5 6 6 1 1 1 1 1 1 1 2 2 2 2 2 2 2 U u u u u u u u U P                2进制霍夫曼编码。 码元集：X={0, 1} l 2 3 4 5 6 6 1 1 1 1 1 1 1 63 1 2 3 4 5 6 6 2 2 2 2 2 2 2 32                c H U l r  63 32 63 32 ( ) 100% log log 2     码元/符号

霍夫曼编码的基本特点编出的码是非续长码：霍夫曼编码实际上构造了一个码树，码树从最上层的端点开始构造，直到树根结束，最后得到一个横放的码树，而且码字在终端节点上。平均码长最小：霍夫曼编码采用概率匹配方法来决定各码字的码长，概率大的符号对应于短码，概率小的符号对应于长码。码字不唯一：每次对概率最小的两个符号求概率之和形成缩减信源时，就构造出两个树枝，由于给两个树枝赋码元是任意的，码字不唯一

4 霍夫曼编码的基本特点 •编出的码是非续长码：霍夫曼编码实际上构造了 一个码树，码树从最上层的端点开始构造，直到 树根结束，最后得到一个横放的码树，而且码字 在终端节点上。 •平均码长最小：霍夫曼编码采用概率匹配方法来 决定各码字的码长，概率大的符号对应于短码， 概率小的符号对应于长码。 •码字不唯一：每次对概率最小的两个符号求概率 之和形成缩减信源时，就构造出两个树枝，由于 给两个树枝赋码元是任意的，码字不唯一

定长编码与变长编码穴余压缩效果比较usususuuru2u,H(U)=63/32bit/符号U1111111H(U)63/32Pu~0.3X=1-2324252%2011222Hmax(U)log7定长编码：{001，010，011，100，101，110，111)变长编码：1，01，001，0001，00001，000001，000000定长编码变长编码1=1=3码元/符号T=63/322码元/符号H(U)63/3263/32H(U)=0.65625bit/码元H(X)=bit/码元H(X)=T3163/321H(X)0.65625H(X)=65.625%=100%nene=二Hmax (X)Hmax(X)log2log2y=1-n,=0Y。=1-n.=0.343755

5 定长编码与变长编码冗余压缩效果比较 H U( ) 63 32  l l   3 max ( ) 0.65625 65.625% ( ) log 2 c H X H X     l  63 32 max ( ) 1 100% ( ) log 2 c H X H X     定长编码 变长编码 码元/符号 码元/符号 bit/符号 ( ) 63 32 ( ) 0.65625 3 H U H X l    ( ) 63 32 ( ) 1 63 32 H U H X l bit/码元    bit/码元 max ( ) 63 32 1 1 0.3 ( ) log 7 H U H U       1 0.34375 c c      1 0 c c      定长编码：{001，010，011，100，101，110，111} 变长编码：{1，01，001，0001，00001，000001，000000} 1 2 3 4 5 6 7 2 3 4 5 6 6 1 1 1 1 1 1 1 2 2 2 2 2 2 2 U u u u u u u u U P               