7.5算术编码 算术编码( Arithmetic Coding)的概念最早由 J. Rissanen在1976年引入,与 Huffman编码不同,算术编 码是一种有记忆非分组编码方法,它用某个实数区间来表 示若干被编码的信息,用该实数区间对应的二进制码作为 编码输出。算术码的编码过程,实际上就是依据字符的发 生概率对码区间的分割过程,我们举例说明算术编码的原 理 设信源符号集为{a,b,c,d},其概率分布为 0.2,0.2,0.4,0.2}。 1)若对该信源进行 Huffman编码,可得其平均码长 为L=2.0bit/字符。 (2)若信源发出序列{b,c,a,b,d},算术编码过程如 下 2021年2月20日 数字图象处理演示稿纪玉波制作
2021年2月20日 数字图象处理演示稿 纪玉波制作 (C) 1 7.5算术编码 算术编码 (Arithmetic Coding) 的 概 念 最 早 由 J.Rissanen在1976年引入，与Huffman编码不同，算术编 码是一种有记忆非分组编码方法，它用某个实数区间来表 示若干被编码的信息，用该实数区间对应的二进制码作为 编码输出。算术码的编码过程，实际上就是依据字符的发 生概率对码区间的分割过程，我们举例说明算术编码的原 理。 设 信 源 符 号 集 为 {a,b,c,d}, 其 概 率 分 布 为 {0.2,0.2,0.4,0.2}。 （1）若对该信源进行Huffman编码，可得其平均码长 为L=2.0bit/字符。 （2）若信源发出序列{b,c,a,b,d}，算术编码过程如 下：
各数据符号在半封闭实数区间[0,1)内按概率进行赋值范 围设定为 a=[0.0,0.2),b=[0.2,0.4),C=[0.4,0.8),d=[0.8,1.0) 第一个信源符号为“b〃,取值区间变为[0.2,0.4)。 第二个信源符号“c〃,对取值区间[0.2,0.4)进行划分找 出对应于“c〃的区间,计算新的取值区间范围。 起始值=取值区间左端 +取值区间长度×当前符号的赋值区间左端 结束值=取值区间左端 取值区间长度×当前符号的赋值区间右端 计算得出新的取值区间为 0.2+0.2×0.4,0.2+0.2×0.8)=[0.28,0.36) 依次类推,第三个符符号“a",编码后的取值区间为 [0.28,0.296)。最终划分结果见下表 2021年2月20日 数字图象处理演示稿纪玉波制作
2021年2月20日 数字图象处理演示稿 纪玉波制作 (C) 2 各数据符号在半封闭实数区间［0,1)内按概率进行赋值范 围设定为 a=[0.0,0.2),b=[0.2,0.4),c=[0.4,0.8),d=[0.8,1.0) 第一个信源符号为“b” ，取值区间变为[0.2,0.4)。 第二个信源符号“ c” ，对取值区间[0.2,0.4)进行划分找 出对应于“ c”的区间，计算新的取值区间范围。 起始值=取值区间左端 +取值区间长度×当前符号的赋值区间左端 结束值=取值区间左端 +取值区间长度×当前符号的赋值区间右端 计算得出新的取值区间为 [0.2+0.2×0.4,0.2+0.2×0.8)= [0.28,0.36) 依次类推，第三个符符号“ a” ，编码后的取值区间为 [0.28,0.296)。最终划分结果见下表
码区间划分结果 数据流 编码区间 区间长度 [0.2,0.4) 0.2 bcabd [0.28,0.36) 0.08 [0.28,0.296) 0.016 [0.2832,0.2864) 0.0032 [0.28576,0.2864) 0.00064 2021年2月20日 数字图象处理演示稿纪玉波制作
2021 年 2 月20 日 数字图象处理演示稿 纪玉波制作 (C) 3
至此,信源序列{ bcabd}已被映射为一个实数区间 [0.28576,0.2864),或者说在[0.28576,0.2864)内 的任何一个实数均代表该序列。 例子 消息“ BILL GATES〃会有一个如下的概率分布 字符概率 空格1/10 A1/10 B1/10 E1/10 G1/10 I1/10 L2/10 1/10 T1/10 2021年2月20日 数字图象处理演示稿纪玉波制作
2021年2月20日 数字图象处理演示稿 纪玉波制作 (C) 4 至此，信源序列{bcabd}已被映射为一个实数区间 [0.28576,0.2864)，或者说在[0.28576,0.2864)内 的任何一个实数均代表该序列。 例子 消息“BILL GATES”会有一个如下的概率分布： 字符 概率 空格 1/10 A 1/10 B 1/10 E 1/10 G 1/10 I 1/10 L 2/10 S 1/10 T 1/10
用到的九个字符的符号集给出数值范围如下: 字符 概率 范围 空格 1/10 0.00≤r<0.10 1/100.10≤r<0.20 ABEGIL 1/100.20≤r<0.30 1/10 0.30≤r<0.40 1/10 0.40≤r<0.50 1/10 0.50≤r<0.60 2/10 0.60≤r<0.80 1/100.80≤r<0.90 1/10 0.90≤r<1.00 2021年2月20日 数字图象处理演示稿纪玉波制作
2021年2月20日 数字图象处理演示稿 纪玉波制作 (C) 5 用到的九个字符的符号集给出数值范围如下： 字符 概率 范围 空格 1/10 0.00≤r＜0.10 A 1/10 0.10≤r＜0.20 B 1/10 0.20≤r＜0.30 E 1/10 0.30≤r＜0.40 G 1/10 0.40≤r＜0.50 I 1/10 0.50≤r＜0.60 L 2/10 0.60≤r＜0.80 S 1/10 0.80≤r＜0.90 T 1/10 0.90≤r＜1.00