信息论编码报告---算术编码

基于Matlab的算术编码的研究摘要算术编码属信源编码信源编码又分为离散编码和连续编码，算术编码也属于离散编码。本文对算术编码的编码理论和译码理论做了详细的分析，并根据理论知识在Matlab中搭建算术编码的系统，实现了对算术编码的整个过程的重现。算术编码所需参数很少，不像哈弗曼编码那样需要一个很大的码表以及大的存储来存储计算过程的计算值。但是算术编码的计算复杂性相对较大。关键词：算术编码、Matlab1、课题研究背景及意义在一个压缩系统中,无论是有损压缩还是无损压缩,编码往往是必须的环节。算术编码在数据压缩中,提供了一种有效去除冗余度的机制,是一种到目前为止编码效率最高的统计熵编码方法,它比著名的Huffman编码效率提高10%左右,但是由于其编码复杂性和实现技术的限制以及一些专利权的限制,所以并不像Huffman编码那样应用广泛。国外对算术编码的研究较多,取得了许多重要的应用,但大多都有专利保护,如JPEG,JPEG2000,JBIG中均采用了算术编码;国内的研究相对较少,应用不是很广泛,至今了解的人还不是很多。其实在Shannon最早提出信息论后不久，Elias就提出了基本的算术编码的想法，1987年Witten等人在文献中提出了算术编码在数据压缩方面的应用，指出其比Huffman编码具有更好的压缩效率，它能够在不要求概率分布形式的情况下表现出良好的性质，这使得算术编码在数据压缩方面得到广泛应用及研究。但是另一方面，包括Huffman编码在内的早期编码模式都是采用固定的码字来表示每一个需要编码的符号，而从加密的角度来看这些算法都是使用简单的字母替换，即用一个符号或字符串替换另一个符号或字符串，所以都很容易被破解，不能提供真正意义上的数据安全。相反，算术编码并不是采用固定码字来表示每个符号，它的压缩模式是将一段消息用一个[0,1)的真子集（子区间）来表示，而这个区间被初始化为[0,1)，并且每编码一个符号区间就缩小一次。使每一个新区间都能唯一地表示一段消息。它可以根据所使用的模型，保证用一段无限逼近信息熵的比特数来传输消息。2、算术编码基本思想2．1算术编码基本思想算术编码是60年代提出提出一种编码概念，一直到1976年才有其实用技术的相关介绍，它的基本原理是：将待编码的信息数据看作是多个符号组成的符号序列，将被编码信息数据的符号序列表示成实数0和1之间的一个间隔（Interval）。无论信息有多长，其输出仅仅是一个数，而且是一个介于0和1之间的二进制小数。信息越长，编码表示它的间隔越小，表示这一间隔所需的二进制位越多。例如算术编码对某条信息的符号序列输出为1010001111，那么它表示小数0.1010001111，也即十进制数0.64。算术编码用到的两个基本参数：符号的概率和它的编码间隔。信源符号的概率决定压缩编码的效率，也决定编码过程中信源符号的间隔，而这些间隔包含在0到1之间，编码过程中的间隔决定符号压缩后的输出。给定事件序列的算术编码步骤如下：（1）编码器在开始时将“当前间隔”[L,H]设置为[0,1]；（2）对每一个事件编码器按步骤（a）和（b）进行处理：（a）编码键当前间隔分为子间隔每一个事件一个；（b）一个子间隔的大小与下一个将出现的事件的概率成比例，编码器选择的子间隔对应于下一个确切发生的事件，并使它成为新的当前间隔。（3）最后输出的“当前间隔”的下边界就是给定事件序列的算术编码。在传输任何信息之前的信息完整范围是[0,1]，当一个符号被处理时，这一范围就依据分配给这一符号的那部分变窄。初始的区间是[0,1]，区间长度（以下用变量R表示）为1，区间上限（以下用变量H表示）为1，下限（以下用变量L表示）为0。依据下列公式得到新的区间：0newiLRLL公式2-10inewHRLH公式2-2公式中newL表示新的区间下限，newH表示新的区间上限，0iL表示编码字符分配的间隔低端，0iH表示编码字符分配的间隔高端。下面举例说明算术编码的编码过程:某条信息中可能出现的字符仅有abc三种，出现的概率分别为：aP=1/6，bP=1/3，cP=1/2。要压缩的信息序列为bccb。将[0,1]区间按照概率的比例分配给三个字符，即a从0.0000到0.1667,b从0.1667到0.5,c从0.5到1.0000。如图2-1所示：图2-1第一步区间划分第一个字符b被编码时，b的0iL=0.1667，0iH=0.5因此16667.016667.0*10newL公式2-35.05.0*10newH公式2-4按照概率分配比例划分b对应的区间[0.1667,0.5]。第二个字符c编码时使用新生成的范围[0.1667,0.5]，c的0iL=0.5，0iH=1，因此3333.05.0*3333.016667.0newL公式2-566667.05.0*116667.0newH公式2-4划分的结果可以用图形表示，如图2-2所示:图2-2第二步区间划分对下一个字符c使用新生成的范围重复以上步骤，得到新的范围[0.4167,0.5]最后一个字符b，得到新的范围[0.4306,0.4584]该区间就代表整个bccb序列。在这个区间内随便选择一个容易变成二进制的数来代表该区间，例如0.4375，将它变成二进制0.0111，去掉前面没有太多意义的0和小数点，我们可以输出0111，这就是信息被压缩后的结果，算术压缩过程完成。2.2自适应算术编码的基本原理在上一节讨论的算术编码中，我们把信源的统计特性被看作是固定不变的，这在实际应用中显然不太实际。为解决使编码技术适应信源统计特性变化的问题，前人提出了自适应算术编码方法，自适应算术编码在一次扫描中可完成两个过程，即概率模型的建立过程和扫描编码过程。自适应算术编码在扫描符号序列前并不知道各符号的统计概率，这时假定每个概率相等，并平均分配区间[0,1],然后在扫描符号序列的过程中不断调整各个符号的概率。还以前面所举的例子为例:abc三种字符的初始概率将为aP=1/3，bP=1/3，cP=1/3以此概率分配来划分[0,1]区间，a从0.0000到0.3333，b从0.3333到0.6667，c从0.6667到1.0000。下边我们研究概率的自适应更新：出现的字符序列为bccb；（1）由于字符b的出现导致abc三种字符的概率分配发生了变化，调整后的概率分配为aP=1/4，bP=2/4，cP=1/4以调整后的概率根据上一节的分析进行区间分配（以下步骤均根据新的概率和上一节的公式作相应得区间分配）。（2）下一个字符c出现后，调整后的概率分配为aP=1/5，bP=2/5，cP=2/5（3）第三个字符c出现后，调整后的概率分配为aP=1/6，bP=2/6，cP=3/6（4）最后一个字符b出现后，调整后的概率分配为aP=1/7，bP=3/7，cP=3/7根据以上步骤完成编码。类似的，译码时，每译出一个字符便进行一次概率分配的更新，以调整后的概率分配进行下一步区间划分。重复操作，完成译码。自适应算术编码方式通常无需先定义概率模型，假定所有字符的初始概率相等，均为1/N(N为字符种类数)，然后根据字符出现的情况进行自适应概率更新。随着编(译)码过程的进行，概率分配将逐渐趋于信源的实际概率分布。这种方法对于无法进行概率统计的信源比较合适。3、算术编码的译码思想算术编码的译码过程其实就是编码过程的逆过程，先根据编码所得码字确定一个码字所在的范围，再将原本的[0，1）继续按信源分布概率减小，继续将累积概率和划分的区间进行对比，从而得出第二个码字，以此类推，从而不断得出原来的码字。以二进制编码为例，每一步比较C-P(a)与A(a)p(0),这里a为前面已译出的序列串，A(a)是序列串a对应的宽度，P(a)是序列a的累积概率值，即为a对应区间的下界值，A(a)p(0)是此区间内下一个输入为’0’所占的子区间宽度。译码规定为:若C-P(a)A(a)p(0)，则译码输出符号为0；若C-P(a)A(a)p(0)，则译码输出符号为1。4、算术编码的性能分析算术编码过程中产生的编码值都统一分布在半开区间[0,1)之间，而这是算术编码达到最优压缩效率的必要条件，但并非是充分条件。编码最后的结果可以在最后的编码区间[low,high)之间，选择任意一个数值来表示，这个值的长度（比特数）可以任意长，当然这个值也可以用比特数最少的值来表示，如下式所示NlB2minlogbits公式4-1下面我们详细介绍满足第二种选择以达到最优压缩的充分条件。首先，我们需要知道的是一个压缩文件仍然存在冗余，包括：①把最终编码值v保存为整数字节所需多余的比特数；②需要一个固定或者可变长度的比特数来表示已经编码的符号个数；③一些记录概率的信息（包括每个符号的概率P以及累积概率Cum_freq）。假设这些所有的冗余可以用一个正数比特σ表示，可以从式(4-1)推出，若编码一个字符串S，编码每个符号平均所用的比特数应满足下面的不等式：NlBN2slogbits/符号公式4-2其中，NkkNapl1)(，即可得：NapBNkk12s)(logbits/符号公式4-3另外，我们定义E{·}表示期望值（平均值）的运算符，所以编码每个符号所需的比特数的期望值为：NUHNmpmpBEBNkMm)()(log)(1102s—公式4-4又因为编码每个符号所需的平均码字长度不能小于熵值)(UH，所以有下式成立：NUHBUH)()(公式4-5同时，可以从中看出)(}{limUHBN公式4-6也就是说，算术编码确实能达到最优压缩效率。这里我们可能会问为什么算术编码的每一步都是以区间的形式表示，而不是单个的编码值。其实这是因为算术编码的最优性不仅体现在输出二元符号，而且对于多元符号来说也是能够满足的，因此我们可以在最终的编码区间中为不同的输出符号选择最优的编码值。5、算术编码的Matlab实现与分析5．1总体框架设计根据算术编码的原理进行程序设计，主要分成以下几个模块进行设计包括：符号累计概率的计算，计算编码区间，对小数进行二进制转换，输出编码结果，判断是否译码，译码输出。流程如图5-1所示：开始符号概率累加开始编码，计算编码区间输出编码结果是否译码译码并输出结果结束否是图5-1程序流程5．2模块设计5.2.1算术编码码字长度的确定编码码字的长度主要是由信源符号概率矩阵P和被编码的信源序列M决定，由两者决定该信源序列的发生概率p(S)，然后求出它的比特信息量，通过向上取整以确定码字长度l。5.2.2算术编码码字长度的确定由上一节中的对算术编码理论的详细分析中，可知只需求得各个信源符号的积累概率，并根据式（2-1）和式（2-2）,每输入一个信源符号，存储器a1和a2的内容就按照这两个式子更新一次，直至信源符号输入完毕，就可将计算区间的中间值作为该序列的码字输出。此时存储器的输出的码字为十进制小数形式，若要转为二进制码字则需要一个转换函数dectobin。在5.2.3中将介绍这一函数。5.2.3小数十进制转换为二进制该函数的目的是将十进制小数以二进制的形式来表示，作为算术编码的码字。二进制的比特数由人为确定。根据十进制小数的性质与二进制之间的关系，将十进制的小数部分乘以2，若超过1则输出1，再减去1继续做下一位的运算，否则输出0且直接做下一位的运算，直到二进制的长度为l。至此十进制小数到二进制的转换完成。5.2.4算术编码译码模块该模块的目的是将信源序列经算术编码后转成的码字重新还原成符号序列，验证能否正确地恢复所发送的信息。译码过程是上述编码过程的逆过程，关键是要确定码字落在哪一个空间以确定相应的符号序列。根据递推公式的相反过程译出每个符号。首先计算积累概率，先译码出发送的信源序列的第一个符号，利用递减，找出第一个大于0的点，就是第一个符号，要求第二个符号的话必须去掉第一个符号的积累概率，再除以第一个符号的发送概率，以此求得落在哪个区间来确定发送的第二个符号，以此类推，直至求出