信息论编码报告算术编码.docx

信息论编码报告算术编码.docx

《信息论编码报告算术编码.docx》由会员分享，可在线阅读，更多相关《信息论编码报告算术编码.docx（12页珍藏版）》请在冰点文库上搜索。

信息论编码报告算术编码

基于Matlab的算术编码的研究

摘要

算术编码属信源编码信源编码又分为离散编码和持续编码，算术编码也属于离散编码。

本文对算术编码的编码理论和译码理论做了详细的分析，并依照理论知识在Matlab中搭建算术编码的系统，实现了对算术编码的整个进程的重现。

算术编码所需参数很少，不像哈弗曼编码那样需要一个专门大的码表和大的存储来存储计算进程的计算值。

可是算术编码的计算复杂性相对较大。

关键词：

算术编码、Matlab

1、课题研究背景及意义

在一个紧缩系统中,不管是有损紧缩仍是无损紧缩,编码往往是必需的环节。

算术编码在数据紧缩中,提供了一种有效去除冗余度的机制,是一种到目前为止编码效率最高的统计熵编码方式,它比闻名的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之间的二进制小数。

信息越长，编码表示它的距离越小，表示这一距离所需的二进制位越多。

例如算术编码对某条信息的符号序列输出为11，那么它表示小数，也即十进制数。

算术编码用到的两个大体参数：

符号的概率和它的编码距离。

信源符号的概率决定紧缩编码的效率，也决定编码进程中信源符号的距离，而这些距离包括在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从到,b从到,c从到。

如图2-1所示：

图2-1第一步区间划分

第一个字符b被编码时，b的

=，

=因此

公式2-3

公式2-4

依照概率分派比例划分b对应的区间[,]。

第二个字符c编码时利用新生成的范围[,]，c的

=，

=1，因此

公式2-5

公式2-4

划分的结果能够用图形表示，如图2-2所示:

图2-2第二步区间划分

对下一个字符c利用新生成的范围重复以上步骤，取得新的范围[,]

最后一个字符b，取得新的范围[,]

该区间就代表整个bccb序列。

在那个区间内随意选择一个容易变成二进制的数来代表该区间，例如，将它变成二进制，去掉前面没有太多意义的0和小数点，咱们能够输出0111，这确实是信息被紧缩后的结果，算术紧缩进程完成。

自适应算术编码的大体原理

在上一节讨论的算术编码中，咱们把信源的统计特性被看做是固定不变的，这在实际应用中显然不太实际。

为解决使编码技术适应信源统计特性转变的问题，前人提出了自适应算术编码方式，自适应算术编码在一次扫描中可完成两个进程，即概率模型的成立进程和扫描编码进程。

自适应算术编码在扫描符号序列前并非明白各符号的统计概率，这时假定每一个概率相等，并平均分派区间[0,1],然后在扫描符号序列的进程中不断调整各个符号的概率。

还以前面所举的例子为例:

abc三种字符的初始概率将为

=1/3，

=1/3，

=1/3以此概率分派来划分[0,1]区间，a从到，b从到，c从到。

下边咱们研究概率的自适应更新：

显现的字符序列为bccb；

（1）由于字符b的显现致使abc三种字符的概率分派发生了转变，调整后的概率分派为

=1/4，

=2/4，

=1/4以调整后的概率依照上一节的分析进行区间分派（以下步骤均依照新的概率和上一节的公式作相应得区间分派）。

（2）下一个字符c显现后，调整后的概率分派为

=1/5，

=2/5，

=2/5

（3）第三个字符c显现后，调整后的概率分派为

=1/6，

=2/6，

=3/6

（4）最后一个字符b显现后，调整后的概率分派为

=1/7，

=3/7，

=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）

假设C-P（a）>A（a）p（0），那么译码输出符号为1。

4、算术编码的性能分析

算术编码进程中产生的编码值都统一散布在半开区间[0,1）之间，而这是算术编码达到最优紧缩效率的必要条件，但并非是充分条件。

编码最后的结果能够在最后的编码区间[low,high）之间，选择任意一个数值来表示，那个值的长度（比特数）能够任意长，固然那个值也能够用比特数最少的值来表示，如下式所示

bits公式4-1

下面咱们详细介绍知足第二种选择以达到最优紧缩的充分条件。

第一，咱们需要明白的是一个紧缩文件仍然存在冗余，包括：

①把最终编码值v保留为整数字节所需多余的比特数；②需要一个固定或可变长度的比特数来表示已经编码的符号个数；③一些记录概率的信息（包括每一个符号的概率P和积存概率Cum_freq）。

假设这些所有的冗余能够用一个正数比特σ表示，能够从式（4-1）推出，假设编码一个字符串S，编码每一个符号平均所用的比特数应知足下面的不等式：

bits/符号公式4-2

其中，

，即可得：

bits/符号公式4-3

另外，咱们概念E{·}表示期望值（平均值）的运算符，因此编码每一个符号所需的比特数的期望值为：

公式4-4

又因为编码每一个符号所需的平均码字长度不能小于熵值

，因此有下式成立：

公式4-5

同时，能够从中看出

公式4-6

也确实是说，算术编码确实能达到最优紧缩效率。

那个地址咱们可能会问什么缘故算术编码的每一步都是以区间的形式表示，而不是单个的编码值。

其实这是因为算术编码的最优性不仅体此刻输出二元符号，而且关于多元符号来讲也是能够知足的，因此咱们能够在最终的编码区间中为不同的输出符号选择最优的编码值。

5、算术编码的Matlab实现与分析

5．1整体框架设计

依照算术编码的原理进行程序设计，要紧分成以下几个模块进行设计包括：

符号累计概率的计算，计算编码区间，对小数进行二进制转换，输出编码结果，判定是不是译码，译码输出。

流程如图5-1所示：

图5-1程序流程

5．2模块设计

算术编码码字长度的确信

编码码字的长度主若是由信源符号概率矩阵P和被编码的信源序列M决定，由二者决定该信源序列的发生概率p（S），然后求出它的比特信息量，通过向上取整以确信码字长度l。

算术编码码字长度的确信

由上一节中的对算术编码理论的详细分析中，可知只需求得各个信源符号的积存概率，并依照式（2-1）和式（2-2）,每输入一个信源符号，存储器a1和a2的内容就依照这两个式子更新一次，直至信源符号输入完毕，就可将计算区间的中间值作为该序列的码字输出。

现在存储器的输出的码字为十进制小数形式，假设要转为二进制码字那么需要一个转换函数dectobin。

在中将介绍这一函数。

小数十进制转换为二进制

该函数的目的是将十进制小数以二进制的形式来表示，作为算术编码的码字。

二进制的比特数由人为确信。

依照十进制小数的性质与二进制之间的关系，将十进制的小数部份乘以2，假设超过1那么输出1，再减去1继续做下一名的运算，不然输出0且直接做下一名的运算，直到二进制的长度为l。

至此十进制小数到二进制的转换完成。

算术编码译码模块

该模块的目的是将信源序列经算术编码后转成的码字从头还原成符号序列，验证可否正确地恢复所发送的信息。

译码进程是上述编码进程的逆进程，关键是要确信码字落在哪个空间以确信相应的符号序列。

依照递推公式的相反进程译出每一个符号。

第一计算积存概率，先译码动身送的信源序列的第一个符号，利用递减，找出第一个大于0的点，确实是第一个符号，要求第二个符号的话必需去掉第一个符号的积存概率，再除以第一个符号的发送概率，以此求得落在哪个区间来确信发送的第二个符号，以此类推，直至求动身送序列的长度n的所有译码。

5．3程序实现与分析

假设一组信源有六个符号及其散布概率pa=;pb=;pc=;pd=;pe=;pf=发送的输入码字为‘abce’，算术编解码系统的运行结果如图5-2所示。

由该图可知，发送该序列的码字长度为12，即需要12比特的信息量来表示该序列。

算术编码的码字为000000111001。

算术译码结果为‘abce’与发送序列完全相同，说明该系统设计正确。

假设散布概率维持不变，发送的输入码字为‘abceddf’,其运行结果如图5-3所示。

由该图可知，发送该序列的码字长度为21，算术编码的码字为00000000，译码结果与发送序列完全相同，说明该系统设计正确。

图5-2程序运行结果

图5-3运行结果

6、心得体会

通过查找相关资料，然后进行算术编码理论研究和程序设计，尽管设计的程序存在封装性不高，过于简单的缺点，可是在这进程中，我收成颇丰，第一对算术编码的原理、进展和应用有了系统的熟悉，第二深切了解了Matlab编程方式，有了必然的编程基础。

固然，整个程序过于粗糙，没有进行优化，希望往后能够更正这一缺点，完善系统。

参考文献

［1］韦彬，游彬，万福等．算术编码理论及误差分析研究［J］．舰船电子工程，2011，（12）：

69～71

［2］王大星，朱鹤鸣．关于算术编码教学的几点注记［J］．滁州学院学报．2011，（13）：

97～99

［3］徐苏珊，马国强，徐建建．算术熵编码CABAC［J］．电子测量技术．2005，（4）：

6～7

［4］毛文娟，王成立，张孝三．算术编码在图像紧缩系统中的应用［J］．信息技术．2005，（10）：

47～50

［5］赵瑾，苏淑华．算术编码与赫夫曼编码的比较［J］．福建电脑．2005，（7）：

37～38

［6］曾伟．基于JPEG2000的高速二进制算术编码器研究［D］．［硕士学位论文］．西安电子科技大学．2020

［7］董文辉，戴琼海．算术编码算法在新紧缩标准中的应用［J］．数字电视．2005，（19）：

27～31

［8］石增硕．H_264中基于内容匹配的自适应二进制算术编码［D］．［硕士学位论文］．西安电子科技大学．2007

［9］安向明，张丹，邹红．基于上下文自适应算术编码的设计与实现［J］．电脑学习，2020，（6）：

107-108．

［10］曹雪虹，张宗橙．信息论与编码[M]．北京：

清华大学出版社，2004．