24算术编码 ●●●●● ●●●● ●●0 ●●● ●●●● Huffman编码更适合于大消息集信源,对于小消息集信源 使用算术编码和游程编码压缩效果更好。 主要内容 >积累概率的递推公式 >算术编码原理 算术编码的码长 >递推公式的应用 不做乘法的算术编码
2.4 算术编码 Huffman编码更适合于大消息集信源，对于小消息集信源 使用算术编码和游程编码压缩效果更好。 主要内容： ➢积累概率的递推公式 ➢算术编码原理 ➢算术编码的码长 ➢递推公式的应用 ➢不做乘法的算术编码
●●●●● ●●●● 241积累概率的递推公式 ●●0 ●●● ●●●● ●信源符号积累概率 设信源 U P」|p(u)p(u2)…p(u k 信源符号积累概率:F(4)=∑p() F(l1)=0F(2)=p(1 F(l2)=p(l1)+p(2) p(1)=F(1+1)-F(1)
2.4.1 积累概率的递推公式 ⚫ 信源符号积累概率 = p(u ) p(u ) p(u ) u u u P U 1 2 n 1 2 n 设信源 信源符号积累概率： − = = 1 1 ( ) ( ) k i F uk p ui F(u1 ) = 0 ( ) ( ) F u2 = p u1 ( ) ( ) ( ) F u3 = p u1 + p u2 ( ) ( ) ( ) p ui = F ui+1 − F ui
●●●●● ●●●● 241积累概率的递推公式 ●●0 ●●● ●●●● ●信源序列积累概率传递公式 设独立信源序列S k S.∈ ESu, )=F(S)+P F(u) 信源序列s添加一 信信源符号ur的 信源 信源符号ur 禕宿辦累概率F擰信源符号的积累概率一样,可用 新悔刺个点来表示,因此积累概率F(S将区间[) 许多不同的小区间,他们互不重叠,序列S的概率p(S) 就是两点间小区间的长度。小区间内的一个点可用来表示 序列的概率
2.4.1 积累概率的递推公式 ⚫ 信源序列积累概率传递公式 设独立信源序列 = = + = ( ) ( ) ( ) ( ) ( ) ( ) ( ) , , , , , , , 1 2 1 2 r r r r k n m p Su p S p u F Su F S p S F u S s s s s u u u 信源序列S添加一 个新的信源符号ur 后所得新序列Sur 的积累概率。 信源序列S的 概率。 信源符号ur的 积累概率。 信源序列S添加一 个新的信源符号ur 后所得新序列Sur 的概率。 信源符号ur 信源序列的积累概率F(S) 的概率。 与信源符号的积累概率一样，可用 [0,1)区间内的个点来表示，因此积累概率F(S)将区间[0,1) 分成许多不同的小区间，他们互不重叠，序列S的概率p(S) 就是两点间小区间的长度。小区间内的一个点可用来表示 序列的概率
●●●●● ●●●● 2.4.2算术编码原理 ●●0 ●●● ●●●● ●基本思路: 把信源序列的积累概率映射到[0,1区间上,使每个序列对 应该区间内的一点,这些点把区间[0,1)分成许多不同的小 区间,这些小区间的长度等于对应序列的概率,在小区间 内取一个浮点小数,使其长度与该序列的概率相匹配。 算术编码的主要任务是计算信源序列对应的小区间
2.4.2 算术编码原理 ⚫ 基本思路： 把信源序列的积累概率映射到[0,1)区间上，使每个序列对 应该区间内的一点，这些点把区间[0,1)分成许多不同的小 区间，这些小区间的长度等于对应序列的概率，在小区间 内取一个浮点小数，使其长度与该序列的概率相匹配。 算术编码的主要任务是计算信源序列对应的小区间
●●●●● ●●●● 2.4.2算术编码原理 ●●0 ●●● ●●●● ●小区间划分的递推计算公式 小区间左端点递推公式: low, )=low(s)+range()xlow(u, 大燃上×乐人 新序列Sur信源序列S对(信源序列S对(信源符号u对 应区间的左应区间的左端应区间的宽度应区间的左端gh(4) 点。 。 新序列Su信源序列s对信源序列S对信源符号u对 应区间的应区间的左端应区间的宽度应区间的右端 点值。(点值 值 点值
2.4.2 算术编码原理 ⚫ 小区间划分的递推计算公式 小区间左端点递推公式： ( ) ( ) ( ) ( ) r ur low Su = low S +range S low 小区间右端点递推公式： ( ) ( ) ( ) ( ) r S high ur high Su = low S + range 新序列Sur对 应区间的左端 点值。 信源序列S对 应区间的左端 点值。 信源序列S对 应区间的宽度 值。 信源符号ur对 应区间的左端 点值。 新序列Sur对 应区间的右端 点值。 信源序列S对 应区间的左端 点值。 信源序列S对 应区间的宽度 值。 信源符号ur对 应区间的右端 点值