2.7 通用编码
一、分段编码（ LZ码）
二、匹配编码
三,LZW算法
一、分段编码（ LZ码）
? 分段规则：
使连着的信源符号尽可能少，但不能出现重复段。
yj=yiur (j>i)
两个数可用一个数 Nj （第 j段段的码字）来表示
Nj=mi+r
特点：编码与符号概率无关。编码效率比较高。
一、分段编码（ LZ码）
? 第 j段码长公式：
? ? ? ?mjl o g1)(Nl o gl ajaj ???
? 编码步骤：
1.将信源序列分段
2.计算 Nj及第 j段码长 lj
3.将 Nj编成二进制码，取 lj位为段的码字。
[例 1] 设信源符号集 U={a0,a1,a2,a3}，求信源
序列 S=a0a0a2a3a1a1a0a0a0a3a2
的 LZ编码。
分 7段,a0,a0a2,a3,a1,a1a0,a0a0,a3a2
j 段序号 i r Nj lj 码字
1 a0 0 0 0 2 00
2 a0a2 1 2 6 3 110
3 a3 0 3 3 4 0011
4 a1 0 1 1 4 0001
5 a1a0 4 0 16 5 10000
6 a0a0 1 0 4 5 00100
7 a3a2 3 2 14 5 01110
? ?mjl o gl aj ?
信源序列码字：
001 100 011 000 110 000 001 000 111 0
二、段匹配码（ LZ78算法）
? 编码步骤：
1.分段
2.将段号和信源符号分别进行编码，
若组成二元码，段号所需码长
每个信源符号所需码长：
? ?lbcl ?1
? ?lbml ?2
[例 2] 设信源符号集 U={a0,a1,a2,a3}，求信源序列
S=a0a0a2a3a1a1a0a0a0a3a2 的匹配编码。
分 7段,a0,a0a2,a3,a1,a1a0,a0a0,a3a2
段号码字 000 001 010 011 100 101 110
段号 1 2 3 4 5 6 7
符号 a0 a0a2 a3 a1 a1a0 a0a0 a3a2
码字
a0 00 a1 01 a2 10 a3 11
C=7 段号所需码长,? ? 37
1 ?? lbl
m=4 信源符号所需码长,? ? 24
1 ?? lbl
00 00 10 11 01 01 00 00 00 11 10
信源序列编码序列：
000 000 010 010 010 110 110 110 001 001 010 000 110 111 0
二、段匹配码
? 平均码长：
? 当 n很长时：
? ? ? ?
n
lb mlb ccL )( ??
)(UHL ?
LZ78码是一种简单的通用编码，编码方法不需要
知道信源的统计概率分布，而且编码方法简单，
编译码速度快，又能达到最佳压缩编码效率
三,LZW算法
? LZW编码算法步骤：
1.串表初始化：将所有单个字符存入串表中，并给每个符
号赋一个码字值；
2.将第一个输入字符作为“前缀串” P；
3.每个新输入的字符作为扩展字符 S。
若 PS字符串不在串表中，输出 P对应的码字，将 PS存入
串表并分配一个码字值； S→P ；
若 PS已在串表中,PS→P ；
4.重复步骤 3，知道完成编码。
[例 3] 由三元字符 X,Y,Z组成的信源序列为：
S=XYXYZYXYXYXXXXXXX 求 LZW编码。
X
1
Y
2
Z
3
XY
4
YX
5
XYZ
6
ZY
7
YXY
8
YXYX
9
XX
10
字符串
码 字
XXX
11
XXXX
12
输入信源序列 X Y XY Z YX YXY X XX XXX
输出 LZW码字 1 2 4 3 5 8 1 10 11
编码表（串表）
LZW算法是 LZ78算法的使用修正形式，保留了 LZ码的自适应性
能，压缩效率大致相同，成为计算机文件压缩的标准算法。
且算法硬件实现容易。
本章重点内容
? 信息量、信息熵、互信息的概念及定义式。
? 克拉夫特不等式
? 无失真变长信源编码定理（香农第一定理）
? 主要的编码方法,Huffman码, 费诺码,香农 -
费诺码、算术码,MH码, LZ码 。
? 各种编码方法的平均码长和编码效率的计算。
本章难点
? 克拉夫特不等式,
表述了信源符号数与码字长度应满足什么条件才
能构成即时码。
? 唯一可译码有相同不等式存在 ----麦克米
伦不等式
? 这两个不等式都只是描述了可构造性，不
能作为判定的论据。
?
?
? ?
n
i
lim
1
1
? 唯一可译码的判定准则：
树图法,（即时码必为惟一可译码）
尾随后缀法,（尾随后缀集合 F中不含任一码字）
本章难点
0
10 11
00
10
01
0
11
1
0
100
110
011
101
0
1
11
1
例, C1={0,10,1100,1110,1011,1101}
F:{11,00,10,01,0,11,
1,100,110,011,101}
10
eg:1011001110...
例, C2={1,10,100,1000} 1
10
100
0
00
0? F={0,00}
C3={1,01,001,0001}
? F=?
一、分段编码（ LZ码）
二、匹配编码
三,LZW算法
一、分段编码（ LZ码）
? 分段规则：
使连着的信源符号尽可能少，但不能出现重复段。
yj=yiur (j>i)
两个数可用一个数 Nj （第 j段段的码字）来表示
Nj=mi+r
特点：编码与符号概率无关。编码效率比较高。
一、分段编码（ LZ码）
? 第 j段码长公式：
? ? ? ?mjl o g1)(Nl o gl ajaj ???
? 编码步骤：
1.将信源序列分段
2.计算 Nj及第 j段码长 lj
3.将 Nj编成二进制码，取 lj位为段的码字。
[例 1] 设信源符号集 U={a0,a1,a2,a3}，求信源
序列 S=a0a0a2a3a1a1a0a0a0a3a2
的 LZ编码。
分 7段,a0,a0a2,a3,a1,a1a0,a0a0,a3a2
j 段序号 i r Nj lj 码字
1 a0 0 0 0 2 00
2 a0a2 1 2 6 3 110
3 a3 0 3 3 4 0011
4 a1 0 1 1 4 0001
5 a1a0 4 0 16 5 10000
6 a0a0 1 0 4 5 00100
7 a3a2 3 2 14 5 01110
? ?mjl o gl aj ?
信源序列码字：
001 100 011 000 110 000 001 000 111 0
二、段匹配码（ LZ78算法）
? 编码步骤：
1.分段
2.将段号和信源符号分别进行编码，
若组成二元码，段号所需码长
每个信源符号所需码长：
? ?lbcl ?1
? ?lbml ?2
[例 2] 设信源符号集 U={a0,a1,a2,a3}，求信源序列
S=a0a0a2a3a1a1a0a0a0a3a2 的匹配编码。
分 7段,a0,a0a2,a3,a1,a1a0,a0a0,a3a2
段号码字 000 001 010 011 100 101 110
段号 1 2 3 4 5 6 7
符号 a0 a0a2 a3 a1 a1a0 a0a0 a3a2
码字
a0 00 a1 01 a2 10 a3 11
C=7 段号所需码长,? ? 37
1 ?? lbl
m=4 信源符号所需码长,? ? 24
1 ?? lbl
00 00 10 11 01 01 00 00 00 11 10
信源序列编码序列：
000 000 010 010 010 110 110 110 001 001 010 000 110 111 0
二、段匹配码
? 平均码长：
? 当 n很长时：
? ? ? ?
n
lb mlb ccL )( ??
)(UHL ?
LZ78码是一种简单的通用编码，编码方法不需要
知道信源的统计概率分布，而且编码方法简单，
编译码速度快，又能达到最佳压缩编码效率
三,LZW算法
? LZW编码算法步骤：
1.串表初始化：将所有单个字符存入串表中，并给每个符
号赋一个码字值；
2.将第一个输入字符作为“前缀串” P；
3.每个新输入的字符作为扩展字符 S。
若 PS字符串不在串表中，输出 P对应的码字，将 PS存入
串表并分配一个码字值； S→P ；
若 PS已在串表中,PS→P ；
4.重复步骤 3，知道完成编码。
[例 3] 由三元字符 X,Y,Z组成的信源序列为：
S=XYXYZYXYXYXXXXXXX 求 LZW编码。
X
1
Y
2
Z
3
XY
4
YX
5
XYZ
6
ZY
7
YXY
8
YXYX
9
XX
10
字符串
码 字
XXX
11
XXXX
12
输入信源序列 X Y XY Z YX YXY X XX XXX
输出 LZW码字 1 2 4 3 5 8 1 10 11
编码表（串表）
LZW算法是 LZ78算法的使用修正形式，保留了 LZ码的自适应性
能，压缩效率大致相同，成为计算机文件压缩的标准算法。
且算法硬件实现容易。
本章重点内容
? 信息量、信息熵、互信息的概念及定义式。
? 克拉夫特不等式
? 无失真变长信源编码定理（香农第一定理）
? 主要的编码方法,Huffman码, 费诺码,香农 -
费诺码、算术码,MH码, LZ码 。
? 各种编码方法的平均码长和编码效率的计算。
本章难点
? 克拉夫特不等式,
表述了信源符号数与码字长度应满足什么条件才
能构成即时码。
? 唯一可译码有相同不等式存在 ----麦克米
伦不等式
? 这两个不等式都只是描述了可构造性，不
能作为判定的论据。
?
?
? ?
n
i
lim
1
1
? 唯一可译码的判定准则：
树图法,（即时码必为惟一可译码）
尾随后缀法,（尾随后缀集合 F中不含任一码字）
本章难点
0
10 11
00
10
01
0
11
1
0
100
110
011
101
0
1
11
1
例, C1={0,10,1100,1110,1011,1101}
F:{11,00,10,01,0,11,
1,100,110,011,101}
10
eg:1011001110...
例, C2={1,10,100,1000} 1
10
100
0
00
0? F={0,00}
C3={1,01,001,0001}
? F=?
