《信息理论与编码》课程教学课件（讲稿）第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               

码子不唯一（1）2进制霍夫曼编码。Uu,uzu,u.u,u,uPu0.350.300.200.100.0050.040.005码元集：X=0,1)码字码长符号概率P(u,)W.u,l0.35u1.001W0.30Us0.650.2000.351u.0.1000.1510.04us00.05100.005W60.0100.005u,01=035×1+0.30×2+0.20×3+0.10×4+0.04×5+0.005×6+0.005x6码元/符号=2.21

6 符号 概率 码字 Wi 码长 l i 0.35 1 1 0.30 01 2 0.20 001 3 0.10 0001 4 0.04 00001 5 0.005 000001 6 0.005 000000 6 ui u1 u2 u3 u4 u5 u6 u7 ( ) P ui 2进制霍夫曼编码。 码元集：X={0, 1} 1 2 3 4 5 6 7 U 0.35 0.30 0.20 0.10 0.04 0.005 0.005 U u u u u u u u P              0 05 . 0 65 . 0 35 . 0 15 . 0 01 . 1 00 . 0 0 0 0 0 0 1 1 1 1 1 1 . . . . . . . . l                0 35 1 0 30 2 0 20 3 0 10 4 0 04 5 0 005 6 0 005 6 2 21 码元/符号 码子不唯一（1）

码子不唯一（2）2进制霍夫曼编码Uuusuzu,uyusue码元集：X=0,11Pu0.0050.350.300.200.100.040.005码字码长符号概率W.uiliP(u.)1u,0.350.65120.3001.00Us0.200.351us0.1000.1510.04Ws00.05100.0050.01U0u0.00501=0.35×2+0.30×2+0.20×2+0.10×3+0.04×4+0.005×5+0.005×5=2.21码元/符号7

7 符号 概率 码字 Wi 码长 l i 0.35 11 2 0.30 10 2 0.20 01 2 0.10 001 3 0.04 0001 4 0.005 00001 5 0.005 00000 5 2进制霍夫曼编码。 码元集：X={0, 1} . . . . . . . . l                0 35 2 0 30 2 0 20 2 0 10 3 0 04 4 0 005 5 0 005 5 2 21 0 05 . 0 65 . 0 35 . 0 15 . 0 01 . 1 00 . 0 0 0 0 0 0 1 1 1 1 1 1 码元/符号 1 2 3 4 5 6 7 U 0.35 0.30 0.20 0.10 0.04 0.005 0.005 U u u u u u u u P              ui u1 u2 u3 u4 u5 u6 u7 ( ) P ui 码子不唯一（2）

码长码字码长码字码字不同，码长也不W;Wl;1;同，但平均码长相同，12111因此编码效率相同。0121020013012码方差：340010001()= E[(, -)1=P(u,)(, -)50000100014i=l6500000100001: (l) =1.42596500000000000,(l) = 0.30598

8 码字 Wi 码长 l i 1 1 01 2 001 3 0001 4 00001 5 000001 6 000000 6 码字 Wi 码长 l i 11 2 10 2 01 2 001 3 0001 4 00001 5 00000 5 q i i i i l E l l P u l l 2 2 2 1 ( ) [( ) ] ( )( )        码方差： l 2 1  ( ) 1.4259  l 2 2  ( ) 0.3059  码字不同，码长也不 同，但平均码长相同， 因此编码效率相同

r进制霍夫曼编码每次求缩减信源时，求r个最小概率之和，即将r个概率最小的符号缩减为一个新符号，并分别用1,2...r-1码元表示，直到最后一次缩减时，r个概率之和为1终止。新问题：缩减到最后时剩下不到r个符号了·为保证平均码长最小，希望缩减到最后刚好还剩下r个符号。为达到此目的，可给信源添加几个无用的符号（概率为0的符号），使得添加符号后的信源符号数9满足：q = (r-1)Q+ r信源缩减的次数

9 r 进制霍夫曼编码 •每次求缩减信源时，求r个最小概率之和，即 将r个概率最小的符号缩减为一个新符号，并 分别用1,2,.r-1码元表示，直到最后一次缩 减时，r 个概率之和为1终止。 •新问题：缩减到最后时剩下不到r 个符号了。 •为保证平均码长最小，希望缩减到最后刚好 还剩下r 个符号。为达到此目的，可给信源 添加几个无用的符号（概率为0的符号），使 得添加符号后的信源符号数 q 满足： q = (r-1)θ+ r 信源缩减的次数

3进制霍夫曼编码。UuuuzusususPu0.320.220.040.180.160.08码元集：X=0,1,2:9=7q=(r-1)0+r=20+3符号概率码字码长2.35H(U)~93.8%Ne-u,P(u,)W.ilogrli1.58×log3u0.322(1.00)n0.22us0.182(0.46)us0.16010.08Ws2(0.12)W60.0401ur0.000码元/符号1=0.32×1+0.22×1+0.18×2+0.16×2+0.08×3+0.04×3=1.5810

10 符号 概率 码字Wi 码长li 0.32 2 1 0.22 1 1 0.18 02 2 0.16 01 2 0.08 002 3 0.04 001 3 0.00 3进制霍夫曼编码。 U 码元集 ： X={0, 1, 2} U u u u u u u P 1 2 3 4 5 6 0.32 0.22 0.18 0.16 0.08 0.04              q r r      ( 1) 2 3   (0.12) (0.46) (1.00) 012 12 01 0 2 l              0.32 1 0.22 1 0.18 2 0.16 2 0.08 3 0.04 3 1.58 c H U l r ( ) 2.35 93.8% log 1.58 log 3      码元 /符号 ∴ q = 7 u i u 1 u 2 u 3 u 4 u 5 u 6 u 7 ( ) P ui