2.4 算术编码
Huffman编码更适合于大消息集信源，对于小消息集信源
使用算术编码和游程编码压缩效果更好。
主要内容：
?积累概率的递推公式
?算术编码原理
?算术编码的码长
?递推公式的应用
?不做乘法的算术编码
2.4.1 积累概率的递推公式
? 信源符号积累概率
??
?
??
??
??
?
??
?
)p ( u)p ( u)p ( u
uuu
P
U
n21
n21
?
?设信源
信源符号积累概率：
?
?
?
?
1
1
)()(
k
i
ik upuF
0)( 1 ?uF )()( 12 upuF ?
)()()( 213 upupuF ??
)()()( 1 iii uFuFup ?? ?
2.4.1 积累概率的递推公式
? 信源序列积累概率传递公式
设独立信源序列
? ?
?
?
?
?
??
??
)()()(
)()()()(
,,,,,,,2121
rr
rr
mnk
upSpSup
uFSpSFSuF
uuussssS ???
信源序列 S添加一
个新的信源符号 ur
后所得新序列 Sur
的积累概率。
信源序列 S的
概率。
信源符号 ur的
积累概率。
信源序列 S添加一
个新的信源符号 ur
后所得新序列 Sur
的概率。
信源符号 ur
的概率。信源序列的积累概率 F(S)与信源符号的积累概率一样，可用
[0,1)区间内的个点来表示，因此积累概率 F(S)将区间 [0,1)
分成许多不同的小区间，他们互不重叠，序列 S的概率 p(S)
就是两点间小区间的长度。小区间内的一个点可用来表示
序列的概率。
2.4.2 算术编码原理
? 基本思路：
把信源序列的积累概率映射到 [0,1)区间上，使每个序列对
应该区间内的一点，这些点把区间 [0,1)分成许多不同的小
区间，这些小区间的长度等于对应序列的概率，在小区间
内取一个浮点小数，使其长度与该序列的概率相匹配。
算术编码的主要任务是计算信源序列对应的小区间。
2.4.2 算术编码原理
? 小区间划分的递推计算公式
小区间左端点递推公式：
)()()()( rr ul owSr an geSl owSul ow ???
小区间右端点递推公式：
)()()()( rr uhi ghSr an geSl o wSuhi gh ???
新序列 Sur对
应区间的左端
点值。
信源序列 S对
应区间的左端
点值。
信源序列 S对
应区间的宽度
值。
信源符号 ur对
应区间的左端
点值。
新序列 Sur对
应区间的右端
点值。
信源序列 S对
应区间的左端
点值。
信源序列 S对
应区间的宽度
值。
信源符号 ur对
应区间的右端
点值。
2.4.2 算术编码原理
? 计算小区间端点值的步骤
（ 1）给出信源符号对应的区间；
（ 2）初始时，设 S=?（ ?代表空集）,low(?)=0,high(?)=1，
range(?)=1
（ 3）输入 ur，根据公式计算序列 Sur的左右端点值，依次下去，
直到全部信源序列对应的区间被确定为止。
2.4.2 算术编码原理
? [例 2-10]设信源
求信源序列 S=abda对应的小区间
??
?
??
??
??
?
??
?
125.0125.025.05.0
dcba
P
U
信源符号对应区间端点值
符号 概率 区间
a 0.5 [0,0.5)
b 0.25 [0.5,0.75)
c 0.125 [0.75,0.875)
d 0.125 [0.875,1)
信源序列对应区间端点值
信源序列 low high
a 0 0.5
ab 0.25 0.375
abd 0.359 375 0.375
abda 0.359 375 0.367 187 5
2.4.2 算术编码原理
? 信源序列对应区间的划分
0.75
a b c d
0 0.5 0.875 1
aa ab ac ad
0.250 0.375 0.5
aba abb abc abd
0.25 0.359 375 0.375
a b c d
0.359 375 0.367 187 5 0.375
不同的信源序列分别对应不同的互不重叠的小区间，取小区间内的一个点
作为对应序列的编码。 --------即时码
S=abda的编码
2.4.2 算术编码原理
? 译码步骤：
（ 1）判断码字落在哪个符号区间，翻译出 1个符号；
（ 2）将码字减去刚翻译出的符号的左端点值；
（ 3）用刚翻译出的符合对应的区间的长度去除步骤 2的结果，
判断此值落在哪个符号区间，翻译出一个新符号；
（ 4）反复步骤（ 2）（ 3）直至全部信源序列被翻译完为止。
2.4.2 算术编码原理
0.75
a b c d
0 0.5 0.875 1
aa ab ac ad
0.250 0.375 0.5
aba abb abc abd
0.25 0.359 375 0.375
a b c d
0.359 375 0.367 187 5 0.375
a[ 0,0, 5 )0250, 8 7 5 ) / 0, 1( 0, 8 7 5
d[ 0, 8 7 5,1 )0, 8 7 50, 5 ) / 0, 2 5-( 0, 7 1 8 7 5
b[ 0, 5,0, 7 5 )0, 7 1 8 7 50 ) / 0, 5-375 ( 0, 3 5 9
a[ 0,0, 5 )375 0, 3 5 9
????
???
???
??
2.4.3 算术编码的码长
? 码字长度应与序列的概率匹配
])(1[lo g SpL a?
取信源序列码字的前 L位，若后面有尾数，就进位到第 L位。
根据信源编码定理可知信源序列 S的平均码长满足：
1)(l o g)()()()(l o g)( ????? ???
S
a
SS
a SpSpSlSpSpSp
平均每个信源符号的码长：
1n )H ( SnLn )H ( S nn ???
对于 DMS有 n H ( S ))H ( S n ?
n
1H ( S )
n
LH ( S ) ???
2.4.4 递推公式的应用
? 用序列积累概率的递推公式进行序列的算术编码的
计算步骤：
（ 1）根据信源符号积累概率公式计算信源符号的积累概率；
（ 2）初始时，设 S=?,F(?)=0,p(?)=1；
（ 3）根据序列的积累概率递推公式，计算序列的积累概率 F(ur)
和序列的概率 p(ur)；
（ 4）计算码长；
（ 5）将 F(s)写成二进制数形式，取其前 L位作为序列 S的码字，
若后面有尾数就进位到第 L位。
2.4.4 递推公式的应用
例 [2-12] 设二元独立信源
求信源序列 S=1010的算术编码。
????????????? 75.025.0 10PU
解,信源符号的积累概率 F(0)=0； F(1)=0.25
信源序列 1010算术编码
序列 F(S) p(S) L 序列码字
? 0 1 0
1 0.01 0.11 1 1
10 0.01 0.0011 2 01
101 0.010011 0.001001 3 011
1010 0.010011 0.00001001 5 01010
)()()(
)()()()(
rr
rr
upSpSup
uFSpSFSuF
?
??
S=?,F(?)=0,p(?)=1
2.4.4 递推公式的应用
算术编码具有渐近最佳性：当序列无限增长时，
平均码长渐近地等于序列的熵值。
实际存在问题：递推运算中都有乘法 —— 运算量大
解决办法,1）编码对象是二元序列，符号概率较小的
一个为 2-k的形式，则乘以 2-k等于移位，乘以 1-2-k等于
移位相减。
2）不做乘法的算术编码。
2.4.5 不做乘法的算术编码
二元信源序列积累概率的递推公式为：
F(S0)=F(S)+p(S)F(0)=F(S)
F(S1)=F(S)+p(S)F(1)
p(S1)=p(S)p(1)
p(S0)=p(S)p(0)
p(S)=p(S0)+p(S1),F(1)=p(0)
如果令 p(S1)≈2-qp(S)，则不做乘法的二进制算术编码的递推公式为
p(S0)=p(S)-p(S1)
F(S0)=F(S)
F(S1)=F(S)+p(S)F(1)
=F(S)+p(S)p(0)
=F(S)+p(S0)
即,p(S1)≈2-qp(S)
p(S0)=p(S)-p(S1)
F(S0)=F(S)
F(S1)=F(S)+p(S0)
? 不做乘法的算术编码步骤：
（ 1）初始时，设 S=?,p(?)=0.111….1, F(?)=0.000…0;
（ 2）输入一个信源符号，用递推公式计算 p(S1),p(S0)，
F(S0),F(S0)；
（ 3）重复步骤（ 2），直至信源序列结束。
2.4.5 不做乘法的算术编码
实际应用时,由 p(S1)≈2-qp(S)，一般 2-q近似等于二元
序列中小概率符号的概率值。通常取 p(0)≈2-q。
2.5 游程编码（ RLC）
游程编码属于无损压缩编码
1) 二元信源序列
将“白”、“黑”二元信源用｛ 0,1｝表示。
2) 游程和游程序列
1° 游程：规定以,0”开始的二元序列，
例 000 1 0 111 00 1 000 1…
2° 游程长度,序列中连续,0”段称, 0” 游程 或,白” 游
程,其 0 的个数称,0” 游程长度,记 lW；
序列中连续,1”段称, 1” 游程 或,黑” 游程,其 1的个数称
,1” 游程长度,记 lB。
3° 游程序列, 将二元序列中的 lW,lB按其在二元序列
中的顺序排列的序列称 游程序列 。
上例 3113213…
3) 游程编码
? 将游程变换成游程序列后,二元序列就变换成多元序列,
? 下面分别对“白” 游程 L(0)和黑” 游程 L(1)的编码进行讨论
1° 白游程的熵
lW, 白游程的长度 p(lW), 白游程长度的概率
L白游程的最大长度
2° 黑游程的熵
lB,黑游程的长度 p(lB), 白游程长度的概率
L白游程的最大长度
)()(
1
W
L
L
WW llbplpH
W
?
?
??
)()(
1
B
L
L
BB llbplpH
B
?
?
??
2.5 游程编码（ RLC）
2.5 游程编码（ RLC）
? 3° 白、黑游程编码的平均码长
? 4° 白、黑游程的平均长度
5° 白、黑像素的熵 hW hB 与平均码长
1??? BBB HLH1???
WWW HLH
)(
1
W
L
L
WW lplL
W
?
?
??
W
W
W
W
W
W l
Lk
l
Hh ??
B
B
B
B
B
B l
Lk
l
Hh ??
WW
W
W
W
W
W
ll
H
l
L
l
H 1???
B
BBB
W
WWW lhkhlhkh
11 ??????
)(
1
B
L
L
BB lplL
B
?
?
??
BB
B
B
B
B
B
ll
H
l
L
l
H 1???
6° 像素的熵 h01与平均码长
pW,黑像素的概率 pB,白像素的概率
BBWWWBBBWWWB kpkpkhphph ????
W
W
WWWWWW l
phpkphp ???
B
B
BBBBBB l
phpkphp ???
B
B
W
W
WBWBWB l
p
l
phkh ????
2.5 游程编码（ RLC）
2.6 改进的 Huffman码（ MH）
传真机信源编码
应用于文件传真：如文件、手写稿、表格、报纸、图纸等“白”、“黑”
像素点的信息。
CCITT(国际电话电报咨询委员会 )为了保证传真文件的清
晰度,对于 A4 幅面的文件（ 210mm× 297mm）规定
1° 行扫描线共有：
297mm× 4线 /mm = 1188 线
或 297mm× 8线 /mm = 2376 线
2° 每条扫描线：
1728像素点 /线, 8像素点 /mm
3° 对于 A4 幅面的文件像素点
1728 像素点 /线 × 1188 线 = 2052864像素点
1728 像素点 /线 × 2376 线 = 4105728像素点
直接编码,以码率 2400 bit/s 或 4800 bit/s 传输时间至少需 5min以上,
2.6 改进的 Huffman码（ MH）
2.6 改进的 Huffman码（ MH）
?方法介绍,?Huffman编码＋游程编码
MH编码,l=K+R，查表
对游程编码之前,先要测得白、黑游程的概率分布,作
为编码的依据,
CCITT(国际电话电报咨询委员会 )推荐 8种样张
我国原邮电部推荐 7种样张
为了减少码表数,采用截断 Huffman编码 (MH)
一类为结尾码,白、黑游程的长度为 0--63
另一类为基干码,游程长度为 64的整倍数
2.6 改进的 Huffman码（ MH）
例, 一行中一段
解：
① lW＝ 131=2× 64+3,K=10010 R=1000 ∴ 100101000 （ l1=9）
② lB=0× 64+4, R=011 （ l2=3）
③ lW=0× 64+6,R=1110 （ l3=4）
④ lB=1× 64+6, K=0000001111 R=0010 （ l4=14）
比较,MH：码元表,9+3+4+14=30bit
直接编码,131+4+6+70=211bit
压缩比 211/30=7.03
lW＝ 131 lB=4 lW=6 lB=70
A,比较：码元表,MH,2× (64+1728/64)＝ 182个
直接 Huffman,2× 1729=3458个
性能,P（ lW<61） ＝ 80% P（ lB<6） ＝ 80%
∴ 工程上性能不差
B,极限压缩比
个码元余信息量，分母：实际编码后每，分子：直接编码 }10{,)(10 XHk ?
② 性能分析
2.6 改进的 Huffman码（ MH）
Huffman编码更适合于大消息集信源，对于小消息集信源
使用算术编码和游程编码压缩效果更好。
主要内容：
?积累概率的递推公式
?算术编码原理
?算术编码的码长
?递推公式的应用
?不做乘法的算术编码
2.4.1 积累概率的递推公式
? 信源符号积累概率
??
?
??
??
??
?
??
?
)p ( u)p ( u)p ( u
uuu
P
U
n21
n21
?
?设信源
信源符号积累概率：
?
?
?
?
1
1
)()(
k
i
ik upuF
0)( 1 ?uF )()( 12 upuF ?
)()()( 213 upupuF ??
)()()( 1 iii uFuFup ?? ?
2.4.1 积累概率的递推公式
? 信源序列积累概率传递公式
设独立信源序列
? ?
?
?
?
?
??
??
)()()(
)()()()(
,,,,,,,2121
rr
rr
mnk
upSpSup
uFSpSFSuF
uuussssS ???
信源序列 S添加一
个新的信源符号 ur
后所得新序列 Sur
的积累概率。
信源序列 S的
概率。
信源符号 ur的
积累概率。
信源序列 S添加一
个新的信源符号 ur
后所得新序列 Sur
的概率。
信源符号 ur
的概率。信源序列的积累概率 F(S)与信源符号的积累概率一样，可用
[0,1)区间内的个点来表示，因此积累概率 F(S)将区间 [0,1)
分成许多不同的小区间，他们互不重叠，序列 S的概率 p(S)
就是两点间小区间的长度。小区间内的一个点可用来表示
序列的概率。
2.4.2 算术编码原理
? 基本思路：
把信源序列的积累概率映射到 [0,1)区间上，使每个序列对
应该区间内的一点，这些点把区间 [0,1)分成许多不同的小
区间，这些小区间的长度等于对应序列的概率，在小区间
内取一个浮点小数，使其长度与该序列的概率相匹配。
算术编码的主要任务是计算信源序列对应的小区间。
2.4.2 算术编码原理
? 小区间划分的递推计算公式
小区间左端点递推公式：
)()()()( rr ul owSr an geSl owSul ow ???
小区间右端点递推公式：
)()()()( rr uhi ghSr an geSl o wSuhi gh ???
新序列 Sur对
应区间的左端
点值。
信源序列 S对
应区间的左端
点值。
信源序列 S对
应区间的宽度
值。
信源符号 ur对
应区间的左端
点值。
新序列 Sur对
应区间的右端
点值。
信源序列 S对
应区间的左端
点值。
信源序列 S对
应区间的宽度
值。
信源符号 ur对
应区间的右端
点值。
2.4.2 算术编码原理
? 计算小区间端点值的步骤
（ 1）给出信源符号对应的区间；
（ 2）初始时，设 S=?（ ?代表空集）,low(?)=0,high(?)=1，
range(?)=1
（ 3）输入 ur，根据公式计算序列 Sur的左右端点值，依次下去，
直到全部信源序列对应的区间被确定为止。
2.4.2 算术编码原理
? [例 2-10]设信源
求信源序列 S=abda对应的小区间
??
?
??
??
??
?
??
?
125.0125.025.05.0
dcba
P
U
信源符号对应区间端点值
符号 概率 区间
a 0.5 [0,0.5)
b 0.25 [0.5,0.75)
c 0.125 [0.75,0.875)
d 0.125 [0.875,1)
信源序列对应区间端点值
信源序列 low high
a 0 0.5
ab 0.25 0.375
abd 0.359 375 0.375
abda 0.359 375 0.367 187 5
2.4.2 算术编码原理
? 信源序列对应区间的划分
0.75
a b c d
0 0.5 0.875 1
aa ab ac ad
0.250 0.375 0.5
aba abb abc abd
0.25 0.359 375 0.375
a b c d
0.359 375 0.367 187 5 0.375
不同的信源序列分别对应不同的互不重叠的小区间，取小区间内的一个点
作为对应序列的编码。 --------即时码
S=abda的编码
2.4.2 算术编码原理
? 译码步骤：
（ 1）判断码字落在哪个符号区间，翻译出 1个符号；
（ 2）将码字减去刚翻译出的符号的左端点值；
（ 3）用刚翻译出的符合对应的区间的长度去除步骤 2的结果，
判断此值落在哪个符号区间，翻译出一个新符号；
（ 4）反复步骤（ 2）（ 3）直至全部信源序列被翻译完为止。
2.4.2 算术编码原理
0.75
a b c d
0 0.5 0.875 1
aa ab ac ad
0.250 0.375 0.5
aba abb abc abd
0.25 0.359 375 0.375
a b c d
0.359 375 0.367 187 5 0.375
a[ 0,0, 5 )0250, 8 7 5 ) / 0, 1( 0, 8 7 5
d[ 0, 8 7 5,1 )0, 8 7 50, 5 ) / 0, 2 5-( 0, 7 1 8 7 5
b[ 0, 5,0, 7 5 )0, 7 1 8 7 50 ) / 0, 5-375 ( 0, 3 5 9
a[ 0,0, 5 )375 0, 3 5 9
????
???
???
??
2.4.3 算术编码的码长
? 码字长度应与序列的概率匹配
])(1[lo g SpL a?
取信源序列码字的前 L位，若后面有尾数，就进位到第 L位。
根据信源编码定理可知信源序列 S的平均码长满足：
1)(l o g)()()()(l o g)( ????? ???
S
a
SS
a SpSpSlSpSpSp
平均每个信源符号的码长：
1n )H ( SnLn )H ( S nn ???
对于 DMS有 n H ( S ))H ( S n ?
n
1H ( S )
n
LH ( S ) ???
2.4.4 递推公式的应用
? 用序列积累概率的递推公式进行序列的算术编码的
计算步骤：
（ 1）根据信源符号积累概率公式计算信源符号的积累概率；
（ 2）初始时，设 S=?,F(?)=0,p(?)=1；
（ 3）根据序列的积累概率递推公式，计算序列的积累概率 F(ur)
和序列的概率 p(ur)；
（ 4）计算码长；
（ 5）将 F(s)写成二进制数形式，取其前 L位作为序列 S的码字，
若后面有尾数就进位到第 L位。
2.4.4 递推公式的应用
例 [2-12] 设二元独立信源
求信源序列 S=1010的算术编码。
????????????? 75.025.0 10PU
解,信源符号的积累概率 F(0)=0； F(1)=0.25
信源序列 1010算术编码
序列 F(S) p(S) L 序列码字
? 0 1 0
1 0.01 0.11 1 1
10 0.01 0.0011 2 01
101 0.010011 0.001001 3 011
1010 0.010011 0.00001001 5 01010
)()()(
)()()()(
rr
rr
upSpSup
uFSpSFSuF
?
??
S=?,F(?)=0,p(?)=1
2.4.4 递推公式的应用
算术编码具有渐近最佳性：当序列无限增长时，
平均码长渐近地等于序列的熵值。
实际存在问题：递推运算中都有乘法 —— 运算量大
解决办法,1）编码对象是二元序列，符号概率较小的
一个为 2-k的形式，则乘以 2-k等于移位，乘以 1-2-k等于
移位相减。
2）不做乘法的算术编码。
2.4.5 不做乘法的算术编码
二元信源序列积累概率的递推公式为：
F(S0)=F(S)+p(S)F(0)=F(S)
F(S1)=F(S)+p(S)F(1)
p(S1)=p(S)p(1)
p(S0)=p(S)p(0)
p(S)=p(S0)+p(S1),F(1)=p(0)
如果令 p(S1)≈2-qp(S)，则不做乘法的二进制算术编码的递推公式为
p(S0)=p(S)-p(S1)
F(S0)=F(S)
F(S1)=F(S)+p(S)F(1)
=F(S)+p(S)p(0)
=F(S)+p(S0)
即,p(S1)≈2-qp(S)
p(S0)=p(S)-p(S1)
F(S0)=F(S)
F(S1)=F(S)+p(S0)
? 不做乘法的算术编码步骤：
（ 1）初始时，设 S=?,p(?)=0.111….1, F(?)=0.000…0;
（ 2）输入一个信源符号，用递推公式计算 p(S1),p(S0)，
F(S0),F(S0)；
（ 3）重复步骤（ 2），直至信源序列结束。
2.4.5 不做乘法的算术编码
实际应用时,由 p(S1)≈2-qp(S)，一般 2-q近似等于二元
序列中小概率符号的概率值。通常取 p(0)≈2-q。
2.5 游程编码（ RLC）
游程编码属于无损压缩编码
1) 二元信源序列
将“白”、“黑”二元信源用｛ 0,1｝表示。
2) 游程和游程序列
1° 游程：规定以,0”开始的二元序列，
例 000 1 0 111 00 1 000 1…
2° 游程长度,序列中连续,0”段称, 0” 游程 或,白” 游
程,其 0 的个数称,0” 游程长度,记 lW；
序列中连续,1”段称, 1” 游程 或,黑” 游程,其 1的个数称
,1” 游程长度,记 lB。
3° 游程序列, 将二元序列中的 lW,lB按其在二元序列
中的顺序排列的序列称 游程序列 。
上例 3113213…
3) 游程编码
? 将游程变换成游程序列后,二元序列就变换成多元序列,
? 下面分别对“白” 游程 L(0)和黑” 游程 L(1)的编码进行讨论
1° 白游程的熵
lW, 白游程的长度 p(lW), 白游程长度的概率
L白游程的最大长度
2° 黑游程的熵
lB,黑游程的长度 p(lB), 白游程长度的概率
L白游程的最大长度
)()(
1
W
L
L
WW llbplpH
W
?
?
??
)()(
1
B
L
L
BB llbplpH
B
?
?
??
2.5 游程编码（ RLC）
2.5 游程编码（ RLC）
? 3° 白、黑游程编码的平均码长
? 4° 白、黑游程的平均长度
5° 白、黑像素的熵 hW hB 与平均码长
1??? BBB HLH1???
WWW HLH
)(
1
W
L
L
WW lplL
W
?
?
??
W
W
W
W
W
W l
Lk
l
Hh ??
B
B
B
B
B
B l
Lk
l
Hh ??
WW
W
W
W
W
W
ll
H
l
L
l
H 1???
B
BBB
W
WWW lhkhlhkh
11 ??????
)(
1
B
L
L
BB lplL
B
?
?
??
BB
B
B
B
B
B
ll
H
l
L
l
H 1???
6° 像素的熵 h01与平均码长
pW,黑像素的概率 pB,白像素的概率
BBWWWBBBWWWB kpkpkhphph ????
W
W
WWWWWW l
phpkphp ???
B
B
BBBBBB l
phpkphp ???
B
B
W
W
WBWBWB l
p
l
phkh ????
2.5 游程编码（ RLC）
2.6 改进的 Huffman码（ MH）
传真机信源编码
应用于文件传真：如文件、手写稿、表格、报纸、图纸等“白”、“黑”
像素点的信息。
CCITT(国际电话电报咨询委员会 )为了保证传真文件的清
晰度,对于 A4 幅面的文件（ 210mm× 297mm）规定
1° 行扫描线共有：
297mm× 4线 /mm = 1188 线
或 297mm× 8线 /mm = 2376 线
2° 每条扫描线：
1728像素点 /线, 8像素点 /mm
3° 对于 A4 幅面的文件像素点
1728 像素点 /线 × 1188 线 = 2052864像素点
1728 像素点 /线 × 2376 线 = 4105728像素点
直接编码,以码率 2400 bit/s 或 4800 bit/s 传输时间至少需 5min以上,
2.6 改进的 Huffman码（ MH）
2.6 改进的 Huffman码（ MH）
?方法介绍,?Huffman编码＋游程编码
MH编码,l=K+R，查表
对游程编码之前,先要测得白、黑游程的概率分布,作
为编码的依据,
CCITT(国际电话电报咨询委员会 )推荐 8种样张
我国原邮电部推荐 7种样张
为了减少码表数,采用截断 Huffman编码 (MH)
一类为结尾码,白、黑游程的长度为 0--63
另一类为基干码,游程长度为 64的整倍数
2.6 改进的 Huffman码（ MH）
例, 一行中一段
解：
① lW＝ 131=2× 64+3,K=10010 R=1000 ∴ 100101000 （ l1=9）
② lB=0× 64+4, R=011 （ l2=3）
③ lW=0× 64+6,R=1110 （ l3=4）
④ lB=1× 64+6, K=0000001111 R=0010 （ l4=14）
比较,MH：码元表,9+3+4+14=30bit
直接编码,131+4+6+70=211bit
压缩比 211/30=7.03
lW＝ 131 lB=4 lW=6 lB=70
A,比较：码元表,MH,2× (64+1728/64)＝ 182个
直接 Huffman,2× 1729=3458个
性能,P（ lW<61） ＝ 80% P（ lB<6） ＝ 80%
∴ 工程上性能不差
B,极限压缩比
个码元余信息量，分母：实际编码后每，分子：直接编码 }10{,)(10 XHk ?
② 性能分析
2.6 改进的 Huffman码（ MH）
