信息论基础第三章~第七章.doc

3.4 算术码 香农—费诺码 在3.2节中我们证明了码长取为时满足克莱夫特不等式，因此可用来构造唯一可译码。本节要介绍一种利用累积分布函数来分配码字的构造编码方法，通常称为香农—费诺方法。设信源随机变量X取值于字符集，不失一般性，设对所有 有定义累积分布函数 和修正的累积分布函数 我们称为的步长。 这两个函数计算示意图见图3.4.1. 图3.4.1 香农---费诺码的累积分布函数 因为所有字母都有正概率, 因此当时有。如果知道了 就可以找到对应的，这就提示我们可以用作为的码字，比如用的二进小数表示。但通常是实数，它未必能用有限多位二进制小数来表出，那么能否用近似表示呢? 如用的二进制小数表示中前位来近似表示，我们把它记为 ,则它和的差距应满足以下不等式. 比如取 时有 因此位于对应的步长之内，可见用比特来描述足够了。也就是说如果（其中），则可取作为的码字。 事实上，每一个码字对应的区间长度为，区间的左端点位于对应的步长的左半部（即小的那一半），而右端点位于步长顶端的下方，这说明整个区间全部落在累积分布函数中对应的步长之内，从而对应不同码字的区间是不相交的，因此此码是即时码。 因为码字长 则码的平均码长为 比理论的最做优值---信源熵H(X)只多2个比特。 以下我们举2个例子来说明这种编码方法。 在3.3节中讨论哈夫曼码时，我们曾提到要进一步提高编码效率，需对长的信源序列来编码，这对香农---费诺码也是对的，即对信源输出的长符号列用香农---费诺方法进行编码，这种编码称算术码。其基本方法是要找一个计算的概率分布和累积分布函数的快速算法，然后用香农---费诺方法对进行编码。实际上就是用区间中的一个数的二进制数字表示作为的码字。由于对不同的，这样的区间是不相交的，因此它们对应的码字也不同，但这样选取的码字集不能保证一定是即时码。如果利用四舍五入到比特来表示，可以保证得到即时码。 以下我们介绍一个简化的计算程序来理解算术码编译码的基本要点，不失一般性，我们仅考虑二进信源，即信源字母集为。我们要对长的信源字母列进行编码。 1）先对所有，计算概率； 2）在上建立一个字典序，对，称，如果在第一个满足的第个分量上，这个条件等价于，也等价于它们对应的二进小数。 我们用表示中在字典序下第个长向量。 3）用一个二叉树来表示（见图3.4.2）,A为根结点，每个对应第层上一个结点，从根结点到该结点的路上经过的边上的符号就是，如图中B代表，C代表，显然按字典如果，其充要条件是对应之结点在对应的结点的右边，如上。 图3.4.2 算术码的树图 4）计算，即要计算树上在结点左边的的所有之概率和，用表示由对应的中间结点以下的子树（例见图中为结点以下之子树）. 这个子树的概率为 于是 假设为无记忆信源,服从公共分布为贝努里分布,.则(参见图3.4.3) 图3.4.3 计算F(1011010)示意图 假设对应的已计算，则易计算 或 5）译码时仍利用树图逐层进行判决，假设从收到的码字可计算出对应的，先从根结点开始比较和。 (i)如，则从0往下的子树在左边，于是第一位译出，反之若，则译出。 (ii)如已译出，则继续比较和，如，则译出，否则译出。 依此类推，直到译出最后一个为止。 注1 上述过程第一步要计算之概率，在某些情况下是不难计算的，比如当信源是无记忆时， 如果信源是平稳马氏信源时， 注2 香农---费诺编码方法和算术码均可推广到D进信源和D进码字的情形。算术编码已用于二值图像的压缩标准。 3.4.2 自适应算术码 在前面讨论的算术码中，信源的统计特性是看作固定不变的。为解决使编码技术适应信源统计特性变化的问题，Rissanen和Pasco提出了自适应算术编码方法，后又经Witten, Neal和Cleary改进，该算法是通过上文对下文消息的预测分布来调整并适应信源统计特性的变化。以下简单介绍这个算法。 该信源取值于字母表 并高最后一个字母表示“停止传输信息”。设信源发出信号为 ，用条件分布 表示前个信源信号为条件下，第个信源信号为的预测分布。而接收端用同样的程序产生相同的预测概率分布，并用于解释收到的信息，即译码。 我们用二进制字符串来表示[0, 1]区间，如区间 [0.25, 0.50]的二进制数表示为[0.01, 0.1]，可用二进制字符串01表示；长一些的字符串01101表示二进区间[0.01101, 0.01110]，由于该字符串前2个数字为01，因此该区间是[0.01, 0.10]的子区间。 同算术码类似，用信源的累积概率分布将区间分成个子区间，如区间，简记为，区间的长度等于。每个区间又可按以下的条件累积分布分割成越来越细的子区间： 这样，