为了适应公司新战略的发展，保障停车场安保新项目的正常、顺利开展，特制定安保从业人员的业务技能及个人素质的培训计划c语言算术编码报告实验报告书信息论与编码实验算术编解码1课程名称：实验名称：2345基于Matlab的算术编码的研究摘要算术编码属信源编码信源编码又分为离散编码和连续编码，算术编码也属于离散编码。本文对算术编码的编码理论和译码理论做了详细的分析，并根据理论知识在Matlab中搭建算术编码的系统，实现了对算术编码的整个过程的重现。算术编码所需参数很少，不像哈弗曼编码那样需要一个很大的码表以及大的存储来存储计算过程的计算值。但是算术编码的计算复杂性相对较大。关键词：算术编码、Matlab1、课题研究背景及意义在一个压缩系统中,无论是有损压缩还是无损压缩,编码往往是必须的环节。算术编码在数据压缩中,提供了一种有效去除冗余度的机制,是一种到目前为止编码效率最高的统计熵编码方法,它比著名的Huffman编码效率提高10%左右,但是由于其编码复杂性和实现技术的限制以及一些专利权的限制,所以并不像Huffman编码那样应用广泛。国外对算术编码的研究较多,取得了许多重要的应用,但大多都有专利保护,如JPEG,JPEGXX,JBIG中均采用了算术编码;国内的研究相对较少,应用不是很广泛,至今了解的人还不是很多。其实在Shannon最早提出信息论后不久，Elias就提出了基本的算术编码的想法，1987年Witten等人在文献中提出了算术编码在数据压缩方面的应用，指出其比Huffman编码具有更好的压缩效率，它能够在不要求概率分布形式的情况下表现出良好的性质，这使得算术编码在数据压缩方面得到广泛应用及研究。但是另一方面，包括Huffman编码在内的早期编码模式都是采用固定的码字来表示每一个需要编码的符号，而从加密的角度来看这些算法都是使用简单的字母替换，即用一个符号或字符串替换另一个符号或字符串，所以都很容易被破解，不能提供真正意义上的数据安全。相反，算术编码并不是采用固定码字来表示每个符号，它的压缩模式是将一段消息用一个0,1)的真子集来表示，而这个区间被初始化为0,1)，并且每编码一个符号区间就缩小一次。使每一个新区间都能唯一地表示一段消息。它可以根据所使用的模型，保证用一段无限逼近信息熵的比特数来传输消息。2、算术编码基本思想21算术编码基本思想算术编码是60年代提出提出一种编码概念，一直到1976年才有其实用技术的相关介绍，它的基本原理是：将待编码的信息数据看作是多个符号组成的符号序列，将被编码信息数据的符号序列表示成实数0和1之间的一个间隔。无论信息有多长，其输出仅仅是一个数，而且是一个介于0和1之间的二进制小数。信息越长，编码表示它的间隔越小，表示这一间隔所需的二进制位越多。例如算术编码对某条信息的符号序列输出为，那么它表示小数，也即十进制数。算术编码用到的两个基本参数：符号的概率和它的编码间隔。信源符号的概率决定压缩编码的效率，也决定编码过程中信源符号的间隔，而这些间隔包含在0到1之间，编码过程中的间隔决定符号压缩后的输出。给定事件序列的算术编码步骤如下：编码器在开始时将“当前间隔”L,H设置为0,1；对每一个事件编码器按步骤和进行处理：编码键当前间隔分为子间隔每一个事件一个；一个子间隔的大小与下一个将出现的事件的概率成比例，编码器选择的子间隔对应于下一个确切发生的事件，并使它成为新的当前间隔。最后输出的“当前间隔”的下边界就是给定事件序列的算术编码。在传输任何信息之前的信息完整范围是0,1，当一个符号被处理时，这一范围就依据分配给这一符号的那部分变窄。初始的区间是0,1，区间长度为1，区间上限为1，下限为0。依据下列公式得到新的区间：Lnew?L?R?Li0公式2-1Hnew?L?R?Hi0公式2-2公式中Lnew表示新的区间下限，Hnew表示新的区间上限，Li0表示编码字符分配的间隔低端，Hi0表示编码字符分配的间隔高端。下面举例说明算术编码的编码过程:某条信息中可能出现的字符仅有abc三种，出现的概率分别为：Pa=1/6，Pb=1/3，Pc=1/2。要压缩的信息序列为bccb。将0,1区间按照概率的比例分配给三个字符，即a从到,b从到,c从到。如图2-1所示：图2-1第一步区间划分第一个字符b被编码时，b的Li0=，Hi0=因此Lnew?0?1*?公式2-3Hnew?0?1*?公式2-4按照概率分配比例划分b对应的区间,。第二个字符c编码时使用新生成的范围,，c的Li0=，Hi0=1，因此Lnew?*?公式2-5Hnew?1*?公式2-4划分的结果可以用图形表示，如图2-2所示:图2-2第二步区间划分对下一个字符c使用新生成的范围重复以上步骤，得到新的范围,最后一个字符b，得到新的范围,该区间就代表整个bccb序列。在这个区间内随便选择一个容易变成二进制的数来代表该区间，例如，将它变成二进制，去掉前面没有太多意义的0和小数点，我们可以输出0111，这就是信息被压缩后的结果，算术压缩过程完成。自适应算术编码的基本原理在上一节讨论的算术编码中，我们把信源的统计特性被看作是固定不变的，这在实际应用中显然不太实际。为解决使编码技术适应信源统计特性变化的问题，前人提出了自适应算术编码方法，自适应算术编码在一次扫描中可完成两个过程，即概率模型的建立过程和扫描编码过程。自适应算术编码在扫描符号序列前并不知道各符号的统计概率，这时假定每个概率相等，并平均分配区间0,1,然后在扫描符号序列的过程中不断调整各个符号的概率。还以前面所举的例子为例:abc三种字符的初始概率将为Pa=1/3，Pb=1/3，Pc=1/3以此概率分配来划分0,1区间，a从到，b从到，c从到。下边我们研究概率的自适应更新：出现的字符序列为bccb；由于字符b的出现导致abc三种字符的概率分配发生了变化，调整后的概率分配为Pa=1/4，Pb=2/4，Pc=1/4以调整后的概率根据上一节的分析进行区间分配。下一个字符c出现后，调整后的概率分配为Pa=1/5，Pb=2/5，Pc=2/5第三个字符c出现后，调整后的概率分配为Pa=1/6，Pb=2/6，Pc=3/6最后一个字符b出现后，调整后的概率分配为Pa=1/7，Pb=3/7，Pc=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)，则译码输出符号为1。4、算术编码的性能分析算术编码过程中产生的编码值都统一分布在半开区间0,1)之间，而这是算术编码达到最优压缩效率的必要条件，但并非是充分条件。编码最后的结果可以在最后的编码区间low,high)之间，选择任意一个数值来表示，这个值的长度可以任意长，当然这个值也可以用比特数最少的值来表示，如下式所示Bmi?n?lo2lNgbits公式4-1下面我们详细介绍满足第二种选择以达到最优压缩的充分条件。首先，我们需要知道的是一个压缩文件仍然存在冗余，包括：把最终编码值v保存为整数字节所需多余的比特数；需要一个固定或者可变长度的比特数来表示已经编码的符号个数；一些记录概率的信息。假设这些所有的冗余可以用一个正数比特表示，可以从式(4-1)推出，若编码一个字符串S，编码每个符号平均所用的比特数应满足下面的不等式：Bs?N?log2lNNbits/符号公式4-2其中，lN?p(ak)，即可得：k?1Bs?log2p(ak)k?1NNbits/符号公式4-3另外，我们定义E表示期望值的运算符，所以编码每个符号所需的比特数的期望值为：B?E?Bs?p(m)log2p(m)k?1m?0NM?1N?H(U)?N公式4-4又因为编码每个符号所需的平均码字长度不能小于熵值H(U)，所以有下式成立：H(U)?B?H(U)?同时，可以从中看出limB?H(U)公式4-6N?N公式4-5也就是说，算术编码确实能达到最优压缩效率。这里我们可能会问为什么算术编码的每一步都是以区间的形式表示，而不是单个的编码值。其实这是因为算术编码的最优性不仅体现在输出二元符号，而且对于多元符号来说也是能够满足的，因此我们可以在最终的编码区间中为不同的输出符号选择最优的编码值。5、算术编码的Matlab实现与分析51总体框架设计根据算术编码的原理进行程序设计，主要分成以下几个模块进行设计包括：符号累计概率的计算，计算编码区间，对小数进行二进制转换，输出编码结果，判断是否译码，译码输出。流程如图5-1所示：重庆交通大学学生实验报告实验课程名称开课实验室数学实验室学院理学院年级09专业班信息2班学生姓名zhouhoufei学号开课时间学年第实验一、唯一可译码判断准则已知：信源符号个数r、码字集合C。算法：1.考察C中所有的码字，若Wi是Wj的前缀，则将相应的后缀作为一个尾随后缀码放入集合F0中；2.考察C和Fi两个集合，若Wi?C是Wj?Fi的前缀或Wi?Fi是Wj?C的前缀，则将相应的后缀作为尾随后缀放入集合Fi?1中；?F即为码C的尾随后缀集合；ii4.若F中出现了C中的元素，则算法终止，返回假；否则，若F中没有出现新的元素，则返回真。要求：1.允许使用的编程语言：C、C+、Basic、Pascal、Fortran、Java、Perl、Tk/Tcl.2.输入：任意的一个码字。码字个数和每个具体的码字在运行时键盘输入。3.输出：判决。4.源程序格式整齐清晰，注意简单明了。源代码如下：#include#include#include#includeclassmaziprivate:char*ma;public:mazi();char*get_mazi();set_mazi(char*a);mazi();mazi:mazi()/、初始化码字ma=NULL;char*mazi:get_mazi()returnma;/、