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

基于Matlab的算术编码的研究 摘要 算术编码属信源编码信源编码又分为离散编码和连续编码，算术编码也属于离散编码。本文对算术编码的编码理论和译码理论做了详细的分析，并根据理论知识在Matlab中搭建算术编码的系统，实现了对算术编码的整个过程的重现。算术编码所需参数很少，不像哈弗曼编码那样需要一个很大的码表以及大的存储来存储计算过程的计算值。但是算术编码的计算复杂性相对较大。 关键词：算术编码、Matlab 课题研究背景及意义 在一个压缩系统中,无论是有损压缩还是无损压缩,编码往往是必须的环节。算术编码在数据压缩中,提供了一种有效去除冗余度的机制,是一种到目前为止编码效率最高的统计熵编码方法,它比著名的Huffman编码效率提高10%左右,但是由于其编码复杂性和实现技术的限制以及一些专利权的限制,所以并不像Huffman编码那样应用广泛。国外对算术编码的研究较多,取得了许多重要的应用,但大多都有专利保护,如JPEG,JPEG2000,JBIG中均采用了算术编码;国内的研究相对较少,应用不是很广泛,至今了解的人还不是很多。 其实在 Shannon 最早提出信息论后不久，Elias 就提出了基本的算术编码的想法，1987 年 Witten 等人在文献中提出了算术编码在数据压缩方面的应用，指出其比 Huffman 编码具有更好的压缩效率，它能够在不要求概率分布形式的情况下表现出良好的性质，这使得算术编码在数据压缩方面得到广泛应用及研究。但是另一方面，包括 Huffman 编码在内的早期编码模式都是采用固定的码字来表示每一个需要编码的符号，而从加密的角度来看这些算法都是使用简单的字母替换，即用一个符号或字符串替换另一个符号或字符串，所以都很容易被破解，不能提供真正意义上的数据安全。相反，算术编码并不是采用固定码字来表示每个符号，它的压缩模式是将一段消息用一个[0,1)的真子集（子区间）来表示，而这个区间被初始化为[0,1)，并且每编码一个符号区间就缩小一次。使每一个新区间都能唯一地表示一段消息。它可以根据所使用的模型，保证用一段无限逼近信息熵的比特数来传输消息。 算术编码基本思想 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。依据下列公式得到新的区间： 公式2-1 公式2-2 公式中表示新的区间下限，表示新的区间上限，表示编码字符分配的间隔低端，表示编码字符分配的间隔高端。 下面举例说明算术编码的编码过程: 某条信息中可能出现的字符仅有abc三种，出现的概率分别为：=1/6，=1/3，=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的=0.1667，=0.5因此 公式2-3 公式2-4 按照概率分配比例划分b对应的区间[0.1667,0.5]。 第二个字符c编码时使用新生成的范围[0.1667,0.5]，c的=0.5，=1，因此 公式2-5