23霍夫曼码及其他编码方法 霍夫曼码 、费诺编码 、香农费诺埃利斯码
2.3 霍夫曼码及其他编码方法 一、霍夫曼码 二、费诺编码 三、香农-费诺-埃利斯码
Huffman:编码 1.二元 Huffman编码 步骤: ①递减排序;S=s,S2 ②合并概率最小的两个符号 ③重复①②,直至缩减信源中只有两个符号为止; ④分配码元。一阶三
1．二元Huffman编码 一、Huffman编码 ④ 分配码元。 步骤： ① 递减排序；S=[s1，s2，…，sq ] ② 合并概率最小的两个符号; ③ 重复①②，直至缩减信源中只有两个符号为止；
例1: 已知离散无记忆信源如下所示,对应的霍夫曼编码为: u u P0.50.250.250.125 消息、符号 信息熵: 码长码字符号概率 (U)=∑p()1bp(=1.75b P(ui 0 平均码长: 0.5 p(u 10 233 11.0=1.75c0de/s 110 110 0.125 0.5 0.125 111 编码效率 H() 7 100 L
例1: 已知离散无记忆信源如下所示，对应的霍夫曼编码为： = 0.5 0.25 0.125 0.125 u u u u P U 1 2 3 4 消息 符号 ui 符号 概率 P(ui) u1 0.5 u2 0.25 u3 0.125 u4 0.125 0.25 0.5 1.0 0 1 0 1 0 1 1 1 11 11 码长 码字 1 0 2 10 3 110 3 111 信息熵： = − = i H(U) p(ui )lbp(ui ) 1.75bit 平均码长： 1.75code/si g L p(u )li i i = = 编码效率： 100% ( ) = = L H U
Huffman编码 1.二元 Huffman编码 例2 03y 消息消息 0 码长码字符号概率 SiP(Si) 26 10 10 0.20 0.19 L=2.72 code/sig 000 00 0.18 035 001 s40.17 p0i>编码不唯 3 010 010 0.15 (0、1分配不 010 0110 0.10 同,排序不同) 0111 oo;0101 0>平均码长唯
➢编码不唯一 （0、1分配不 同，排序不同） L code sig = 2.72 / 1．二元Huffman编码 消息 符号 si 消息 概率 P(si ) s1 0.20 s2 0.19 s3 0.18 s4 0.17 s5 0.15 s6 0.10 s7 0.01 0 1 0 1 0 0 0 1 0 1 0 1 0 1 码长 码字 2 10 2 11 3 000 3 001 3 010 4 0110 4 0111 1 1 00 00 01 01 011 011 例2． ➢平均码长唯一 一、Huffman编码
Huffman编码 1.二元 Huffman编码(例2) 码2 码长方差:d=E[(-D)]∑P-D 源 概率 0 S S 0.4 00 00 S2 0.2 0 0.2 000 0.10010 2=0.16 5 0.1 G=136 0011 011 L=∑P(具=4×1+0,2×2+02x3+0,1×+01x=2,2l
码长方差： ( )2 2 2 1q i i i i E l L P( s )( l L ) = = − = − 码2 1．二元Huffman编码 （例 2 ） 源符Si 概率P(Si) S 1 0.4 S 2 0.2 S 3 0.2 S 4 0.1 S 5 0.1 0 1 0 0 0 1 00 0 00 1 001 0 001 1 01 0 0 1 0 1 1 01 0 01 1 0 1 i i i L P s l code sig 51 ( ) 0.4 1 0.2 2 0.2 3 0.1 4 0.1 4 2.2 / = = = + + + + = i i i L P s l code sig 51 ( ) 0.4 2 0.2 2 0.2 2 0.1 3 0.1 3 2.2 / = = = + + + + = 21 = 1.36 22 = 0.16 ✓ 一、Huffman编码