文档介绍：通用编码
一、分段编码(LZ码)
二、匹配编码
三、LZW算法
一、分段编码(LZ码)
分段规则:
使连着的信源符号尽可能少,但不能出现重复段。
yj=yiur (j>i)
两个数可用一个数Nj (第j段段的码字)来表示
Nj=mi+r
特点:编码与符号概率无关。编码效率比较高。
一、分段编码(LZ码)
第j段码长公式:
编码步骤:
,取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
信源序列码字:
001 100 011 000 110 000 001 000 111 0
二、段匹配码(LZ78算法)
编码步骤:
,
若组成二元码,段号所需码长
每个信源符号所需码长:
[例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 段号所需码长:
m=4 信源符号所需码长:
00 00 10 11 01 01 00 00 00 11 10
信源序列编码序列:
000 00
0 010 010
010 11
0 110 1
10 001 00
1 010 000
110 111 0
二、段匹配码
平均码长:
当n很长时:
LZ78码是一种简单的通用编码,编码方法不需要知道信源的统计概率分布,而且编码方法简单,编译码速度快,又能达到最佳压缩编码效率
三、LZW算法
LZW编码算法步骤:
:将所有单个字符存入串表中,并给每个符号赋一个码字值;
“前缀串”P;
。
若PS字符串不在串表中,输出P对应的码字,将PS存入串表并分配一个码字值;S→P;
若PS已在串表中,PS→P;
,知道完成编码。
[例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码。
各种编码方法的平均码长和编码效率的计算。