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编码
Huffman编码 1.二元 Huffman编码 二元 Huffman码的特点: ※概率大→短码 短码充分利用 概率小→长码 ※每次缩减信源的最后两个码字总是最后一位不同 (前面各位相同) 惟一可译
二元Huffman码的特点： → → 概率大 短码 短码充分利用 概率小 长码 ※ ※ 每次缩减信源的最后两个码字总是最后一位不同 （前面各位相同） 1．二元Huffman编码 ——惟一可译 一、Huffman编码
Huffman编码 2.m元 Huffman编码“合m为一,一分为m” ※为使短码充分利用,L→min,要求最后信源 有m个符号填克法 n=(m-1)Q+m(对于二元编码,n=Q+m) 缩减次韶 填充符号s;'(P'=0),使Q 为整数,且为最小
n=(m－1)Q+m （对于二元编码，n=Q+m） ※ 为使短码充分利用， ，要求最后信源 有m个符号 L min → “合m为一，一分为m” 消 息 数 目 缩减次数 一、Huffman编码 填充符号 使 为整数,且为最小 1 '( ' 0), − − = = m n m si Pi Q 2．m元Huffman编码
Huffman编码 2.m元 Huffman编码 步骤: ①验证n是否满足n=(m-1)Qm,若不满足,可以人为地增 加一些概率为零的符号,使最后一步有m个信源符号; ②取概率最小的m个符号合并成一个新结点,并分别用0, ,…,(m+1)给各分支赋值,把这些符号的概率相加 作为该新结点的概率; ③将新结点和剩下结点重新排队,重复步骤2; ④取树根到叶子(信源符号对应结点)的各树枝上的赋值, 得到各符号码字
一、Huffman编码 2．m元Huffman编码 步骤： 验证n是否满足n=(m-1)Q+m，若不满足，可以人为地增 加一些概率为零的符号，使最后一步有m个信源符号； 取概率最小的m个符号合并成一个新结点，并分别用0， 1，…，（m+1）给各分支赋值，把这些符号的概率相加 作为该新结点的概率； 将新结点和剩下结点重新排队，重复步骤2； 取树根到叶子（信源符号对应结点）的各树枝上的赋值， 得到各符号码字
Huffman编码 2.m元 Huffman编码 例3.三元 Huffman编码 n=(m-1)Q+m P0.40.3020.050.05 解:n=5,若取m=3 若取m=4 有5=203回∈有5=30+4②ez 取5+2=3Q+4 ∴需加入两个填充符号
解：n=5,若取m =3 2．m元Huffman编码 Q Z ∴需加入两个填充符号 有5=2Q+3 n=(m－1)Q+m 一、Huffman编码 Q Z 例3．三元Huffman编码 = 0.4 0.3 0.2 0.05 0.05 u1 u2 u3 u4 u5 P U 若取m=4 有5=3Q+4 取5+2=3Q+4
Huffman编码 2.m元 Huffman编码过程 消息符号符号概率 码字码长 P(ui 0 0.4 0 8=∑p(u)1=0.4×1+0.3×1+0.2×2+0.05×2+0.05×2=1.3code/s 0.2 4 0.05 0.3 0.05 22
2．m元Huffman编码过程 一、Huffman编码 消息符号 ui 符号概率 P(ui) u1 0.4 u2 0.3 u3 0.2 u4 0.05 u5 0.05 0 1 2 0 1 2 0.3 0 码字 1 20 21 22 码长 1 1 2 2 2 L p(u) l 0.4 1 0.3 1 0.2 2 0.05 2 0.05 2 1.3code/sig i 3 = i i = + + + + =