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%