《信息理论与编码》课程教学课件（讲稿）第4章 离散无记忆信源无失真编码 4.5 变长编码方法 4.5.2 费诺（Fano）编码 4.5.3 香农编码

4.5.2费诺（Fano）编码·费诺（Fano）编码也是构造一个码树，因此，编出的码是非续长码，但不一定是最佳码。费诺编码步骤（以二进制编码为例）：（1）将信源符号按概率从大到小的排序：（2）将信源符号分成2组，使2组信源符号的概率之和近似相等，并给2组信源符号分别赋码元“0”和“1";（3）接下来再把各小组的信源符号细分为2组并赋码元，方法与第一次分组相同；（4）如此一直进行下去，直到每一小组只含一个信源符号为止；（5）由此即可构造一个码树，所有终端节点上的码宝组式费造码

1 4.5.2 费诺（Fano）编码 •费诺（Fano）编码也是构造一个码树，因此，编出的 码是非续长码，但不一定是最佳码。 •费诺编码步骤(以二进制编码为例)： （1）将信源符号按概率从大到小的排序； （2）将信源符号分成2组，使2组信源符号的概率之 和近似相等，并给2组信源符号分别赋码元“0”和 “1”； （3）接下来再把各小组的信源符号细分为2组并赋码 元，方法与第一次分组相同； （4）如此一直进行下去，直到每一小组只含一个信 源符号为止； （5）由此即可构造一个码树，所有终端节点上的码 字组成费诺码

Uuuzusu.Usuu,2进制费诺编码。[Pu]0.200.190.180.170.150.100.01码元集：X=0，1)概率码字 码长符号W.liuiP(u)0.20ui00.19U20.18U30.17u40.15us0.10u60.01U7T=P(u,),=0.20×2+0.19×3+0.18×3+0.17×2+0.15×3+0.10×4+0.01×4=2.74码元/符号2.61H(U)H(U)=-ZP(u,)logP(u,)=2.61 bit/符号=95%ne=Tlogr2.74×log2=

2 符号 ui 概率 P(ui ) 码字 Wi 码长 l i u1 0.20 00 2 u2 0.19 010 3 u3 0.18 011 3 u4 0.17 10 2 u5 0.15 110 3 u6 0.10 1110 4 u7 0.01 1111 4 2进制费诺编码。 码元集：X={0，1} 1 2 3 4 5 6 7 U 0.20 0.19 0.18 0.17 0.15 0.10 0.01 U u u u u u u u P              0 0 1 0 0 0 0 1 1 1 1 1 7 1 ( ) 0.20 2 0.19 3 0.18 3 0.17 2 0.15 3 0.10 4 0.01 4 2.74 i i i l P u l                   码元/符号 ( ) 2.61 95% log 2.74 log 2 c H U l r      7 1 ( ) ( )log ( ) 2.61 i i i H U P u P u      bit/符号

4.5.3香农编码香农（Shannon）编码步骤（以二进制编码为例）：（1）将信源符号按概率从大到小的排序：（2）按下式求第i个信源符号对应的码字的码长l，并取整；-logP(u,)≤l, <-logP(u,)+1（3）按下式求i个信源符号的累加概率P；P=0P,=ZP(u) i= 2,3,.,I（4）将累加概率P，转换成二进制数：（5）取P.二进制数小数点后l.个二进制数字作3为第i个信源符号的码字

3 4.5.3 香农编码 香农(Shannon)编码步骤(以二进制编码为例)： （1）将信源符号按概率从大到小的排序； （2）按下式求第i 个信源符号对应的码字的码 长l i ，并取整； （3）按下式求i 个信源符号的累加概率Pi ； （4）将累加概率Pi 转换成二进制数； （5）取Pi二进制数小数点后l i 个二进制数字作 为第i 个信源符号的码字。 log ( ) log ( ) 1      P u l P u i i i 1 1 1 0 ( ) 2, 3, , i i k k P P P u i q           

对给定信源「「uu,u,uyusuu0.170.150.100.01P(u,)[0.20.190.18进行r=2进制香农编码。码字w码长l累加概率消息符号u消息概率pi-logpiL300.202.34000u32.410.20010.19u232.480.180.39011u331000.172.560.57u431010.152.740.74us43.340.100.891110u670.010.996.661111110ur=3.14石码元/符号，n.=83.1%?

4 消息符号ui 消息概率pi -logpi 码长l i 累加概率 码字wi u1 0.20 2.34 3 0 000 u2 0.19 2.41 3 0.2 001 u3 0.18 2.48 3 0.39 011 u4 0.17 2.56 3 0.57 100 u5 0.15 2.74 3 0.74 101 u6 0.10 3.34 4 0.89 1110 u7 0.01 6.66 7 0.99 1111110 对给定信源 进行r=2进制香农编码。 1 2 3 4 5 6 7 ( ) 0.2 0.19 0.18 0.17 0.15 0.10 0.01 i U u u u u u u u P u              l  3.14 码元/符号， c  83.1%

比较UuWWsusus.u6Pu]0.200.190.180.170.150.010.10香农编霍夫曼编费诺编码码码平均码长2.722.743.14（码元/符号）95.3%编码效率95.96%83.1%5

5 比 较 1 2 3 4 5 6 7 U 0.20 0.19 0.18 0.17 0.15 0.10 0.01 U u u u u u u u P              霍夫曼编 码 费诺编码 香农编 码 平均码长 （码元/符号） 2.72 2.74 3.14 编码效率 95.96% 95.3% 83.1%