2.3 霍夫曼码及其他编码方法
一、霍夫曼码
二、费诺编码
三、香农 -费诺 -埃利斯码
1．二元 Huffman编码
一,Huffman编码
④ 分配码元。
步骤：
① 递减排序； S=[s1,s2,…, sq]
② 合并概率最小的两个符号 ;
③ 重复 ①②，直至缩减信源中只有两个符号为止；
例 1,已知离散无记忆信源如下所示，对应的霍夫曼编码为：
??
?
??
??
??
?
??
?
0,1250,1250,250,5
uuuu
P
U 4321
消息
符号
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 ii 1, 7 5 b it)) lb p ( up ( uH ( U )
平均码长：
ig1, 7 5 c o d e / s
) lip ( uL
i
i
?
? ?
编码效率：
%100)( ?? LUH?
?编码不唯一
（ 0,1分配不
同，排序不同）
L c od e sig2.7 2 /?
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
10
1
0
1
0
1
码长 码字
2 10
2 11
3 000
3 001
3 010
4 0110
4 0111
1
1
00
0001
01
011
011
例 2．
?平均码长唯一
一,Huffman编码
码长方差,? ? 2
22
1
q
i i i
i
E l L P ( s ) ( l L )
?
??? ? ? ? ????? ?码 2
1．二元 Huffman编码 （例 2）
源符
Si
概率
P(Si)
S1 0.4
S2 0.2
S3 0.2
S4 0.1
S5 0.1
0
1
00
01
000
001
0010
0011
0
100
10
11
010
011
01
ii
i
L P s l c o d e sig5
1
( ) 0,4 1 0,2 2 0,2 3 0,1 4 0,1 4 2,2 /
?
? ? ? ? ? ? ? ? ? ? ? ??
i
L s l c ode si g5
1
( ) 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编码
n=(m－ 1)Q+m （ 对于二元编码, n=Q+m）
※ 为使短码充分利用,, 要求最后信源
有 m个符号
L mi n?
“合 m为一，一分为 m”
消
息
数
目
缩减次数
一,Huffman编码
且为最小为整数使填充符号,1),0'(' ???? m mnQPs ii
2,m元 Huffman编码
一,Huffman编码
2,m元 Huffman编码
步骤：
?验证 n是否满足 n=(m-1)Q+m，若不满足，可以人为地增
加一些概率为零的符号，使最后一步有 m个信源符号；
?取概率最小的 m个符号合并成一个新结点，并分别用 0，
1,…,（ m+1）给各分支赋值，把这些符号的概率相加
作为该新结点的概率；
?将新结点和剩下结点重新排队，重复步骤 2；
?取树根到叶子（信源符号对应结点）的各树枝上的赋值，
得到各符号码字。
解,n=5,若取 m =3
2,m元 Huffman编码
ZQ?
∴ 需加入两个填充符号
有 5=2Q+3
n=(m－ 1)Q+m
一,Huffman编码
ZQ?
例 3,三元 Huffman编码
??
?
??
??
??
?
??
?
05.005.02.03.04.0
54321 uuuuu
P
U
若取 m=4
有 5=3Q+4
取 5+2=3Q+4
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
g1, 3 c o d e / s i20, 0 520, 0 520, 210, 310, 4)lp ( uL
i ii3
???????????? ?
2,m元 Huffman编码过程
一,Huffman编码
消息符号
ui
符号概率
P(ui)
u1 0.4
u2 0.3
u3 0.2
u4 0.05
u5 0.05
u6 0
u7 0
0
1
2
3
0
1
2
3
0.1
码字
0
1
2
30
31
32
33
码长
1
1
1
2
2
2
2
c o d e / s i g21)lp ( uL
i ii4
1.1)05.005.0()2.03.04.0( ????????? ?
一,Huffman编码
H(U)=1.95bit
编码效率：
%6.88886.021.1 95.141.1 95.1)()4(
4
??????? lbL UH m?
2,r元 Huffman编码过程
%9595.058.13.1 95.133.1 95.1)()3(
3
??????? lbL UH m?
一般情况下，信源符号集的数目应远大于码元数。
定理 在变长编码中, 如果码字长度严格按照所对应符
号的出现概率逆序排列, 则其平均码长为最小 。
3,Huffman码的最佳性
? 码字长度与出现概率 逆序排列 ；
? 每次缩减信源的最后 r个码字末位不同。
一,Huffman编码
费诺（ Fano）编码（即时码）
二,费诺（ Fano）编码
1,递减排列 ;
2,等概分组 P(A)≈P(B);
3,每个子集以符号, 0”或, 1”标识 。
?方法,等概分割
?步骤：
费诺编码属于统计匹配编码，但它不是最佳的编码方法
例 4,DMS如下，用费诺编码方法编码
??
?
??
??
??
?
??
?
125.0125.025.05.0
4321 uuuu
P
U
消息符号
ui
符号概率
P(ui)
u1 0.5
u2 0.25
u3 0.125
u4 0.125
第一次
分组
0
1
第二次
分组
0
1
第三次
分组
0
1
码字
0
10
110
111
码长
1
2
3
3
H(U)=1.75bit
c o d e / s i g)lp ( uL
i ii4
75.1?? ? %100)( ??
L
UH?
消息
符号
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
1
第三次
分组
0
1
0
1
第四次
分组
0
1
码字 码长
00 2
010 3
011 3
10 2
110 3
1110 4
1111 4
( ) 2 7 4iiL P s l, c o d e / s i g???
() 0 9 5 3HSR, b i t / c o d e
L??
例 5
香农 -费诺 -埃利斯码
三,香农 -费诺 -埃利斯码
?方法,根据信源符号累积概率分配码字
不是分组码，也不是最佳码，但效率高
?步骤：
1,确定信源符号修正的累积概率函数；
2,将修正的累积概率函数转换成二进制
小数, 取小数点后 l(uk)位为码字 。
设信源为：
??
?
??
??
??
?
??
?
)()()()( 321
321
n
n
upupupup
uuuu
P
U
?
?
信源符号积累概率为：
?
?
?
k
i
ik upuF
1
)()(
信源符号修正的积累概率为：
)(21)()(
1
1
k
k
i
ik upupuF ?? ?
?
?
码长：
1)(1)( ??
?
?
??
??
k
k uplbul
平均码长：
)1)( 1()()()(
11
??
?
?
??
??? ??
?? k
n
k
kk
n
k
k uplbupulupL
2)(1)( ???? UHLUH
例 6,DMS如下，用香农 -费诺 -埃利斯编码方法编码
??
?
??
??
??
?
??
?
125.0125.05.025.0
4321 uuuu
P
U
消息
符号
ui
符号
概率
P(ui)
u1 0.25
u2 0,5
u3 0.125
u4 0.125
F(uk)
0.15
0.75
0.875
1
F(uk)
0.125
0.5
0.8125
0.9375
二进制
F(uk)
0.001
0.100
0.1101
0.1111
码长
l(uk)
3
2
4
4
码字
001
10
1101
1111
H(U)=1.75bit
c o d e / s i g)lp ( uL
i ii4
75.2?? ? %6.63)( ??
L
UH?
Huffman码在实际应用中的问题
?
?
?
?
?
对 不 等 概 信 源, 压 缩 效 果 明 显
更 适 合 大 消 息 集 信 源
在 信 源 统 计 特 性 已 知 情 况 下 实 现
一、霍夫曼码
二、费诺编码
三、香农 -费诺 -埃利斯码
1．二元 Huffman编码
一,Huffman编码
④ 分配码元。
步骤：
① 递减排序； S=[s1,s2,…, sq]
② 合并概率最小的两个符号 ;
③ 重复 ①②，直至缩减信源中只有两个符号为止；
例 1,已知离散无记忆信源如下所示，对应的霍夫曼编码为：
??
?
??
??
??
?
??
?
0,1250,1250,250,5
uuuu
P
U 4321
消息
符号
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 ii 1, 7 5 b it)) lb p ( up ( uH ( U )
平均码长：
ig1, 7 5 c o d e / s
) lip ( uL
i
i
?
? ?
编码效率：
%100)( ?? LUH?
?编码不唯一
（ 0,1分配不
同，排序不同）
L c od e sig2.7 2 /?
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
10
1
0
1
0
1
码长 码字
2 10
2 11
3 000
3 001
3 010
4 0110
4 0111
1
1
00
0001
01
011
011
例 2．
?平均码长唯一
一,Huffman编码
码长方差,? ? 2
22
1
q
i i i
i
E l L P ( s ) ( l L )
?
??? ? ? ? ????? ?码 2
1．二元 Huffman编码 （例 2）
源符
Si
概率
P(Si)
S1 0.4
S2 0.2
S3 0.2
S4 0.1
S5 0.1
0
1
00
01
000
001
0010
0011
0
100
10
11
010
011
01
ii
i
L P s l c o d e sig5
1
( ) 0,4 1 0,2 2 0,2 3 0,1 4 0,1 4 2,2 /
?
? ? ? ? ? ? ? ? ? ? ? ??
i
L s l c ode si g5
1
( ) 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编码
n=(m－ 1)Q+m （ 对于二元编码, n=Q+m）
※ 为使短码充分利用,, 要求最后信源
有 m个符号
L mi n?
“合 m为一，一分为 m”
消
息
数
目
缩减次数
一,Huffman编码
且为最小为整数使填充符号,1),0'(' ???? m mnQPs ii
2,m元 Huffman编码
一,Huffman编码
2,m元 Huffman编码
步骤：
?验证 n是否满足 n=(m-1)Q+m，若不满足，可以人为地增
加一些概率为零的符号，使最后一步有 m个信源符号；
?取概率最小的 m个符号合并成一个新结点，并分别用 0，
1,…,（ m+1）给各分支赋值，把这些符号的概率相加
作为该新结点的概率；
?将新结点和剩下结点重新排队，重复步骤 2；
?取树根到叶子（信源符号对应结点）的各树枝上的赋值，
得到各符号码字。
解,n=5,若取 m =3
2,m元 Huffman编码
ZQ?
∴ 需加入两个填充符号
有 5=2Q+3
n=(m－ 1)Q+m
一,Huffman编码
ZQ?
例 3,三元 Huffman编码
??
?
??
??
??
?
??
?
05.005.02.03.04.0
54321 uuuuu
P
U
若取 m=4
有 5=3Q+4
取 5+2=3Q+4
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
g1, 3 c o d e / s i20, 0 520, 0 520, 210, 310, 4)lp ( uL
i ii3
???????????? ?
2,m元 Huffman编码过程
一,Huffman编码
消息符号
ui
符号概率
P(ui)
u1 0.4
u2 0.3
u3 0.2
u4 0.05
u5 0.05
u6 0
u7 0
0
1
2
3
0
1
2
3
0.1
码字
0
1
2
30
31
32
33
码长
1
1
1
2
2
2
2
c o d e / s i g21)lp ( uL
i ii4
1.1)05.005.0()2.03.04.0( ????????? ?
一,Huffman编码
H(U)=1.95bit
编码效率：
%6.88886.021.1 95.141.1 95.1)()4(
4
??????? lbL UH m?
2,r元 Huffman编码过程
%9595.058.13.1 95.133.1 95.1)()3(
3
??????? lbL UH m?
一般情况下，信源符号集的数目应远大于码元数。
定理 在变长编码中, 如果码字长度严格按照所对应符
号的出现概率逆序排列, 则其平均码长为最小 。
3,Huffman码的最佳性
? 码字长度与出现概率 逆序排列 ；
? 每次缩减信源的最后 r个码字末位不同。
一,Huffman编码
费诺（ Fano）编码（即时码）
二,费诺（ Fano）编码
1,递减排列 ;
2,等概分组 P(A)≈P(B);
3,每个子集以符号, 0”或, 1”标识 。
?方法,等概分割
?步骤：
费诺编码属于统计匹配编码，但它不是最佳的编码方法
例 4,DMS如下，用费诺编码方法编码
??
?
??
??
??
?
??
?
125.0125.025.05.0
4321 uuuu
P
U
消息符号
ui
符号概率
P(ui)
u1 0.5
u2 0.25
u3 0.125
u4 0.125
第一次
分组
0
1
第二次
分组
0
1
第三次
分组
0
1
码字
0
10
110
111
码长
1
2
3
3
H(U)=1.75bit
c o d e / s i g)lp ( uL
i ii4
75.1?? ? %100)( ??
L
UH?
消息
符号
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
1
第三次
分组
0
1
0
1
第四次
分组
0
1
码字 码长
00 2
010 3
011 3
10 2
110 3
1110 4
1111 4
( ) 2 7 4iiL P s l, c o d e / s i g???
() 0 9 5 3HSR, b i t / c o d e
L??
例 5
香农 -费诺 -埃利斯码
三,香农 -费诺 -埃利斯码
?方法,根据信源符号累积概率分配码字
不是分组码，也不是最佳码，但效率高
?步骤：
1,确定信源符号修正的累积概率函数；
2,将修正的累积概率函数转换成二进制
小数, 取小数点后 l(uk)位为码字 。
设信源为：
??
?
??
??
??
?
??
?
)()()()( 321
321
n
n
upupupup
uuuu
P
U
?
?
信源符号积累概率为：
?
?
?
k
i
ik upuF
1
)()(
信源符号修正的积累概率为：
)(21)()(
1
1
k
k
i
ik upupuF ?? ?
?
?
码长：
1)(1)( ??
?
?
??
??
k
k uplbul
平均码长：
)1)( 1()()()(
11
??
?
?
??
??? ??
?? k
n
k
kk
n
k
k uplbupulupL
2)(1)( ???? UHLUH
例 6,DMS如下，用香农 -费诺 -埃利斯编码方法编码
??
?
??
??
??
?
??
?
125.0125.05.025.0
4321 uuuu
P
U
消息
符号
ui
符号
概率
P(ui)
u1 0.25
u2 0,5
u3 0.125
u4 0.125
F(uk)
0.15
0.75
0.875
1
F(uk)
0.125
0.5
0.8125
0.9375
二进制
F(uk)
0.001
0.100
0.1101
0.1111
码长
l(uk)
3
2
4
4
码字
001
10
1101
1111
H(U)=1.75bit
c o d e / s i g)lp ( uL
i ii4
75.2?? ? %6.63)( ??
L
UH?
Huffman码在实际应用中的问题
?
?
?
?
?
对 不 等 概 信 源, 压 缩 效 果 明 显
更 适 合 大 消 息 集 信 源
在 信 源 统 计 特 性 已 知 情 况 下 实 现
