算术编码资料.ppt

算术编码 提纲 背景 编码 解码 改进 实现 分析 背景 早在1948年香农提出信息论的时候，就提出了算术编码的思想。但是经过多年研究，许多学者认为算术编码是无法实现的，因为算术编码要求进行无限精度的实数运算，而计算机只能进行有限精度的运算。随着研究的深入，终于在1987年Ian H. Witten、Radford M. Neal和John G. Cleary发表了一篇论文，提出了一种基于二进制整数运算的算术编码实现算法。 编码 算术编码将整个要编码的数据映射到一个位于区间[0,1)中的一个小数。 算术编码在编码时，从初始区间[0,1)开始；按照编码符号的概率将当前区间划分成多个子区间；根据当前输入符号选择对应的子区间，并将该子区间作为下次编码的当前区间；重复这一过程，直到所有符号都编码完毕，最后从最终的子区间中选择任意小数作为编码结果。 编码举例 编码举例 首先，初始区间是[0,1)； ABC三个符号的初始概率都是1/3，按照这个概率将当前区间[0,1)划分为三个子区间； 第一个输入的符号是 B，所以选择与 B 对应的子区间[0.3333,0.6667)，并且作为编码C时的当前区间； 更新符号概率，继续划分区间、选择子区间，直到最后输入符号B编码完毕； 最终得到的子区间是[0.6390,0.6501)，从中选择任意一个小数，如0.6400，作为编码结果。 编码过程 已知编码符号序列及其各符号概率，输入符号序列（它是编码符号序列的一个子集）和初始区间[low, high) = [0,1)。 （1）计算当前区间大小： （2）计算新的子区间： （3）输出编码结果。 解码 算术编码进行解码时仅输入一个小数。解码前首先需要对初始区间[0,1)，按照初始时的符号概率进行划分；观察输入的小数位于哪个子区间，输出对应符号， 选择对应的子区间；然后继续对选择的子区间进行划分，重复这个过程，直到所有符号都解码完毕。整个解码过程相当于编码过程的逆运算。 解码举例 在上面的例子中，编码得到的小数是0.6400，因此解码输入的小数就是0.6400。 首先，初始区间是[0,1)； 初始符号概率都是1/3，按照这个概率划分区间； 小数0.6400位于区间[0.3333,0.6667)，与之对应的符号是B，即第一个解码符号，选择[0.3333,0.6667) 作为下一次解码的当前区间； 更新符号概率，划分区间、选择子区间，直至最后一个符号 B 解码出来。 解码过程 需要说明的是，计算机是根据输入的数值、当前区间的下限和累计频率之和，计算出一个估计出来的累计概率从而确定当前解码符号的。 累计概率通过下面的公式计算： 改进 前面讲的是最基本的算术编码，通过它只是让大家明白算术编码的基本思想。实际上，前面描述的编解码过程，在计算机上是很难实现的。因为区间可以无限制地划分下去，而且总能找到落在这一区间的一个小数，但是计算机做不到；所以在实现的时候，需要做一些改进，使得它可以在计算机上实现。 整数运算 在前面描述的编解码过程中，区间的上下限都是小于1的小数。如果省略0和小数点，仅使用小数的尾数表示小数，那么实际上原来的区间上下限就变成了一个无限大的整数。更进一步地，如果仅使用无限整数的部分高位表示这个无限整数，并在用这些进行整数运算，那么就可以用整数来模拟原来的实数运算。 整数运算举例 仍以前面的例子为例，使用区间[3333,6667)表示区间[0.3333,0.6667)，输出6400表示0.6400。整数运算的区间变化如下： 整数运算举例 解码的时候也进行整数运算。解码过程如下表所示： 正规化 上面的整数运算实际上也是无法实现的。由前面整数运算编码区间的变化可以看出，随着编码的进行区间范围会越来越小，最后区间范围会趋向于 0；如果输入符号序列很长，那么区间范围为 0 时就无法继续编码。因此需要使用正规化操作来解决这一问题。 正规化就是当区间上下限满足一定条件时，将一定位数从区间中移出，同时对区间进行放大。其作用是在有限区间上模拟无限运算。 正规化举例 因为实现算法的时候用的是二进制整数，所以下面也以二进制整数为例进行说明。编码过程中区间变化的可能情况： 情况1: 情况2: 正规化举例 因此可以将最高位移出区间并输出。可以通过将区间的下限左移1位，将区间的