文档介绍：算术编码
Huffman编码更适合于大消息集信源,对于小消息集信源使用算术编码和游程编码压缩效果更好。
主要内容:
积累概率的递推公式
算术编码原理
算术编码的码长
递推公式的应用
不做乘法的算术编码
积累概率的递推公式
信源符号积累概率
设信源
信源符号积累概率:
积累概率的递推公式
信源序列积累概率传递公式
设独立信源序列
信源序列S添加一个新的信源符号ur后所得新序列Sur的积累概率。
信源序列S的概率。
信源符号ur的积累概率。
信源序列S添加一个新的信源符号ur后所得新序列Sur的概率。
信源符号ur的概率。
信源序列的积累概率F(S)与信源符号的积累概率一样,可用[0,1)区间内的个点来表示,因此积累概率F(S)将区间[0,1)分成许多不同的小区间,他们互不重叠,序列S的概率p(S)就是两点间小区间的长度。小区间内的一个点可用来表示序列的概率。
算术编码原理
基本思路:
把信源序列的积累概率映射到[0,1)区间上,使每个序列对应该区间内的一点,这些点把区间[0,1)分成许多不同的小区间,这些小区间的长度等于对应序列的概率,在小区间内取一个浮点小数,使其长度与该序列的概率相匹配。
算术编码的主要任务是计算信源序列对应的小区间。
算术编码原理
小区间划分的递推计算公式
小区间左端点递推公式:
小区间右端点递推公式:
新序列Sur对应区间的左端点值。
信源序列S对应区间的左端点值。
信源序列S对应区间的宽度值。
信源符号ur对应区间的左端点值。
新序列Sur对应区间的右端点值。
信源序列S对应区间的左端点值。
信源序列S对应区间的宽度值。
信源符号ur对应区间的右端点值。
算术编码原理
计算小区间端点值的步骤
(1)给出信源符号对应的区间;
(2)初始时,设S=Ø(Ø代表空集),low(Ø)=0,high(Ø)=1, range(Ø)=1
(3)输入ur,根据公式计算序列Sur的左右端点值,依次下去,直到全部信源序列对应的区间被确定为止。
算术编码原理
[例2-10]设信源
求信源序列S=abda对应的小区间
信源符号对应区间端点值
符号
概率
区间
a
[0, )
b
[, )
c
[, )
d
[, 1)
信源序列对应区间端点值
信源序列
low
high
a
0
ab
abd
375
abda
375
187 5
算术编码原理
信源序列对应区间的划分
a
b
c
d
0
1
aa
ab
ac
ad
0
aba
abb
abc
abd
375
a
b
c
d
375
187 5
不同的信源序列分别对应不同的互不重叠的小区间,取小区间内的一个点作为对应序列的编码。--------即时码
S=abda的编码
算术编码原理
译码步骤:
(1)判断码字落在哪个符号区间,翻译出1个符号;
(2)将码字减去刚翻译出的符号的左端点值;
(3)用刚翻译出的符合对应的区间的长度去除步骤2的结果,判断此值落在哪个符号区间,翻译出一个新符号;
(4)反复步骤(2)(3)直至全部信源序列被翻译完为止。
算术编码原理
a
b
c
d
0
1
aa
ab
ac
ad
0
aba
abb
abc
abd
375
a
b
c
d
375
187 5