第13讲 算术编码(1).doc

第13讲 算术编码（1）1. 简介（brief）算术编码是一种无损数据压缩方法，是图像压缩的主要算法之一，由IBM的信息论学家J. Rissanen于1976年发明。同霍夫曼码一样，算术码也属于概率匹配码。不同的是，算术编码不是分组码，而是全序列编码，将整个数据编码为一个大于等于0小于1的二进制数值。尽管霍夫曼码是最优的分组码，算术码与霍夫曼码相比具有如下两个优点：（1）不使用码本，避免了码本太大对于压缩效果的影响；（2）编码效率是可变的，随着数据长度增大而增大，并逐渐收敛于最大值1。因此，算术编码的效率将随着数据长度增大而超过任何霍夫曼编码，具有渐近最优性。算术码的编码和译码算法中主要使用加法和乘法这两种算术运算。2. 直观思想所有的方法和灵感来自于人的直觉，算术码的发明也是这样的。算术码的直观想法是，对全概率区间0,1)进行划分，为每个信源序列确定一个唯一的子区间，使得该子区间的长度恰好等于该信源序列的概率，然后在该子区间中取一个尽可能短的二进制数作为码字。这里我们先介绍构造各信源序列的概率区间的直观想法。假设一个离散无记忆信源有三个信源符号a1，a2，a3，概率分别为p(a1)，p(a2)和p(a3)。首先将0,1)划分为3个半闭半开的子区间I(a1)，I(a2)和I(a3)，其长度分别为p(a1)，p(a2)和p(a3)。对这些区间继续按照同样的长度比例继续划分，可以确定所有长度为2的信源序列的概率区间。例如，I(a1)划分为I(a1 a1)，I(a1a2)和I(a1a3)。显然，这3个子区间的长度分别为对应序列的概率，即p(a1 a1)，p(a1a2)和p(a1a3)。按照类似的方式继续划分，可以得到所有信源序列的概率区间。以全概率区间0,1)为根，所有的这些概率区间组成一棵树。读者可以看出，任意两个区间若非直系必不相交。概率区间树I(a1 a2)0,1)I(a2)I(a3)I(a1)I(a1 a3)I(a1 a1)3. 累积概率为了严格地表达上述直观思想，我们引入累积概率这个概念。首先，让我们一起回顾离散数学中的标准序概念。以下设a1, a1, ,aK是离散无记忆信源的符号表。根据其中的符号次序，定义符号串之间的标准序如下：（1）相同长度的序列之间像字典那样排序；（2）长度小的长度大的。定义1.（累积概率） 信源符号ak的累积概率定义为 信源序列S的累积概率定义为注意，S的累积概率值中不含p(S)。命题2.累积概率的递推公式证明：因为所考虑的信源是无记忆的，所以根据定义， 证毕4. 信源序列的概率区间定义3. 对于任何信源序列S，记I(S)=F(S), F(S)+p(S)，称为S的概率区间，记为I(S)。提问：对于任何n，所有长度为n的信源序列的区间相互之间是什么关系？它们与0,1)是什么关系？命题4. 设s1与s2是两个信源序列。若s1是s2的前缀，则若s1和s2互相不是对方的前缀，则。证明1）设s1是s2的前缀。根据命题1中累积概率的递推公式，可知 从而。2）设s1和s2互相不是对方的前缀，且s1和s2是等长的。不妨设s1s2。根据定义，从而 。3）设s1和s2互相不是对方的前缀，且s1和s2是不等长的。则根据（1）与（2）的结论，可知 。 证毕5. 算术码的编码方法设Sa是信源序列，其中a是一个信源符号，对Sa进行编码如下。算法1. 算术编码第1步 计算概率p(Sa)，并表示为二进制展开式。 第2步 计算累积概率F(Sa) ，并表示为二进制展开式。第3步 计算码长第4步 计算码字其中F(Sa)，p(Sa)都是二进制实数。注： 表示对实数近似到小数点后第n位，并且舍去后面的尾数。注：在电子线路中，小数点与前面的0是不用表示出来的。注：第3步中，由于p(Sa)是二进制数值，无需进行对数计算，直接可得结果。例如，例1. 设某二元无记忆信源的符号概率分布为p(0)=1/4，p(1)=3/4试对信源序列11101进行算术编码。解：算术编码过程如下表所示，其中有四点说明。（1） 概率与累积概率采用二进制表示。（2） a是当前处理的输入符号，初始值为空符号。（3） S是前面处理过的输入串，初始值为空符号。（4） 我们约定，空符号的概率与累积概率分别为1和0。ap(Sa) p(S)F(a)F(Sa)F(Sa)+p(Sa)码字10.110.010.011.0010.10010.10010.01111.000010.0110110.0110110.1001011.00000000.000110110.00.1001010.101011110.1010.00010100010.00000110110.10011010110.10101111000.10EOF码长=5F(Sa)+p(Sa)/2=0.101001001110.10100编码的实时性算术编码能够实时（real-time）进行，也就是编码器的输出与输入基本同步，根据至多常数个输入符号就可以确定并输出1个或者不超过某常数个码符号。6. 唯一可译性对于例1中的信源，算术编码不是唯一可译的。例如，在下表中，信源序列1和11的码字是相同的，信源序列1110与11101的码字也是相同。ap(Sa)码长 p(S)F(a)F(Sa)码字10.1120.010.010.1010.100120.10010.01110.1010.01101130.0110110.1001010.11000.0001101150.00.1001010.1010010.000101000150.00000110110.10011010110.10100原因在于，信源符号1的概率大于0.5，使得以1结尾的串与其最大真前缀二者的码长相同，而所用的累积概率又很接近，导致二者的码字相同。我们将证明，当信源符号的概率都不大于0.5时，其算术编码是唯一可译的。定理5. 设S是离散信源的一个序列，C是该序列的算术码字。则 证明 根据算术码的编码方法，其中，从而。于是我们有证毕 定理6. 设离散无记忆信源的每个符号的发生概率都0.5，则该信源的算术码是唯一可译的。证明 由于算术编码是序列编码，根据定义，只需证明它是单射。根据算术码的编码方法可知，信源序列的码字是该序列的累积概率区间中的一个数值。因此，若两个信源序列的概率区间不相交，则二者的码字是不同的。根据命题4，仅当一个序列是另外一个的前缀时，它们的概率区间才相交。令s，sa是两个信源序列。由于p(a) 0.5，故。因此，sa的码字长度比s的码字长度大，从而二者的码字是不同的。 证毕 讨论：如何解决概率大于0.5的问题？对扩展信源进行算术编码解决上述问题的一个简