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对 应区间的右端 点值
●●●●● ●●●● 2.4.2算术编码原理 ●●0 ●●● ●●●● ●计算小区间端点值的步骤 (1)给出信源符号对应的区间; (2)初始时,设S=(④代表空集),low(O)=0,high()=1, range(￠) (3)输入ur,根据公式计算序列Sur的左右端点值,依次下去, 直到全部信源序列对应的区间被确定为止
2.4.2 算术编码原理 ⚫ 计算小区间端点值的步骤 （1）给出信源符号对应的区间； （2）初始时，设S=Ø（Ø代表空集），low(Ø)=0，high(Ø)=1， range(Ø)=1 （3）输入ur，根据公式计算序列Sur的左右端点值，依次下去， 直到全部信源序列对应的区间被确定为止
●●●●● ●●●● 242算术编码原理 ●●0 ●●● ●●●● [例210设信源U「abc 0.50.250.1250.125 求信源序列S=abda对应的小区间 信源符号对应区间端点值信源序列对应区间端点值 符号概率 区间 信源序列ow high a 0.5[0,0.5) a 0.5 02505,075) ab 0.25 0.375 c0.125[075,0.875) abd03593750375 0.125[0.875,1) abda0.3593750.3671875
2.4.2 算术编码原理 ⚫ [例2-10]设信源 求信源序列S=abda对应的小区间 = 0.5 0.25 0.125 0.125 a b c d 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 ●●● ●●●● ●信源序列对应区间的划分 b d 0.5 0.750.875 ------= 一ac 0.25 0.375 0.5 aba abb b abd 0.25 --0.3593750375 a b d 0359375S=abda的编码671875 0.375 不同的信源序列分别对应不同的互不重叠的小区间,取小区间内的一个点 作为对应序列的编码。-即时码
2.4.2 算术编码原理 ⚫ 信源序列对应区间的划分 0.75 a b c d 0 0.5 0.875 1 aa ab ac ad 0 0.25 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算术编码原理 ●●0 ●●● ●●●● ●译码步骤: (1)判断码字落在哪个符号区间,翻译出1个符号; (2)将码字减去刚翻译出的符号的左端点值; (3)用刚翻译出的符合对应的区间的长度去除步骤2的结果, 判断此值落在哪个符号区间,翻译出一个新符号 (4)反复步骤(2)(3)直至全部信源序列被翻译完为止
2.4.2 算术编码原理 ⚫ 译码步骤： （1）判断码字落在哪个符号区间，翻译出1个符号； （2）将码字减去刚翻译出的符号的左端点值； （3）用刚翻译出的符合对应的区间的长度去除步骤2的结果， 判断此值落在哪个符号区间，翻译出一个新符号； （4）反复步骤（2）（3）直至全部信源序列被翻译完为止
●●●●● ●●●● 2.4.2算术编码原理 ●●0 ●●● ●●●● b d 0.5 0.750.875 aa Had 0.25 0.375 0.5 aba abc -abd 0.25 03593750375 d 0.359375 0.3671875 0.375 0.359375∈[0,0.5)a (0.358875-0)/0.50.71875∈[0.5,0.75b (0.718750.5)/0.250.875∈[0.875,1d (0.8750.875)/025=0∈[0,0.5a
2.4.2 算术编码原理 0.75 a b c d 0 0.5 0.875 1 aa ab ac ad 0 0.25 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 (0.875 0.875)/0.12 5 0 [0,0.5) a (0.71875-0.5)/0.250.875 [0.875,1) d (0.359 375 -0)/0.5 0.71875 [0.5,0.75) b 0.359 375 [0,0.5) a − = → = → = → →