算术编码原理分析与实现

《算术编码原理分析与实现》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、算术编码原理分析与实现http://kulasuki115.blogcn.com/diary,201492702.shtml 前言人类已进入信息时代，信息时代的重要特征是信息的数字化，人们越来越依靠计算机获取和利用信息，这就需要对信息的表示、存储、传输和处理等关键技术进行研究。我们要把数值、文字、语言、声音、图像、图形、视频和动画等多种媒体转化成计算机所能处理的数字信息，但数字化后的视频和音频等媒体信息的数据量是非常大的。因此，数字化信息的数据量很大，这样大的数据量，无疑给存储器的存储容量、通信干线的信道传输率以及计算机的速度都提出了很高的要求。这个问题是多媒体技

2、术发展中的一个非常棘手的瓶颈问题。要解决这一问题，单纯用扩大存储器容量、增加通信干线的传输率的办法是不现实的，采用数据压缩技术才是行之有效的方法。通过数据压缩手段减少信息数据量，以压缩形式存储和传输，既节约了存储空间，又提高了通信干线的传输效率。数据压缩技术的研究受到人们越来越多的关注，从基本的无损压缩到语音，图像和视频信号等信号的有损压缩，数据压缩在人们的日常生活中发挥着越来越重要的作用。根据解码后数据与原始数据是否完全一致进行分类，数据压缩方法一般分为两类：①无损压缩，即解码图像与原始图像严格相同，压缩比大约在2：1－5：1之间，如霍夫曼编码，算术编码等；②有

3、损编码，即还原图像与原始图像存在一定的误差，但视觉效果一般可以接受，压缩比可以从几倍到上百倍，如：PCM编码，预测编码、变换编码等。算术编码作为一种高效的数据编码方法在文本，图像，音频：等压缩中有广泛的应用。它是一种到目前为止编码效率最高的统计熵编码方法,它比著名的Huffman  编码效率提高10 %左右。在这篇论文中我们就来分析一下算术编码的原理，以及它与Huffman 编码的区别,它的发展前景等，最后运用Visual C++来具体实现一个简单的算术编码器。   算术编码原理分析与实现第一章：选题背景1.1  算术编码的发展史1948 年， Shannon 在

4、提出信息熵理论的同时，也给出了一种简单的编码方法—— Shannon 编码。Shannon提出将信源符号依其出现的概率进行降序排列，用符号序列累计概率的二进制作为对信源的编码，并从理论上论证的了它的优越性。 1952 年， R. M. Fano 又进一步提出了 Fano 编码。这些早期的编码方法揭示了变长编码的基本规律，也确实可以取得一定的压缩效果，但离真正实用的压缩算法还相去甚远。第一个实用的编码方法是由 D. A. Huffman  在 1952 年的论文“最小冗余度代码的构造方法（ A Method for the Construction of Minim

5、um Redundancy Codes ）”中提出的。直到今天，许多《数据结构》教材在讨论二叉树时仍要提及这种被后人称为 Huffman  编码的方法。 Huffman  编码在计算机界是如此著名，以至于连编码的发明过程本身也成了人们津津乐道的话题。据说， 1952 年时，年轻的 Huffman  还是麻省理工学院的一名学生，他为了向老师证明自己可以不参加某门功课的期末考试，才设计了这个看似简单，但却影响深远的编码方法。 Huffman  编码效率高，运算速度快，实现方式灵活，从 20 世纪 60 年代至今，在数据压缩领域得到了广泛的应用。例如，早期 UNIX 系

6、统上一个不太为现代人熟知的压缩程序 COMPACT 实际就是 Huffman  0 阶自适应编码的具体实现。1960年伊莱亚斯（ Peter Elias）发现无需排序，只要编、解码端使用相同的符号顺序即可，并提出了算术编码的概念。 伊莱亚斯 没有公布他的发现，因为他知道算术编码在数学上虽然成立，但不可能在实际中实现。1976年，帕斯科（R.Pasco）和 瑞萨尼恩（J.Rissanen）分别用定长的寄存器实现了有限精度的算术编码。 20 世纪 80 年代初， Huffman  编码又出现在 CP/M 和 DOS 系统中，其代表程序叫 SQ 。今天，在许多知名的压缩

7、工具和压缩算法（如 WinRAR 、 gzip 和 JPEG ）里，都有 Huffman  编码的身影。不过， Huffman编码所得的编码长度只是对信息熵计算结果的一种近似，还无法真正逼近信息熵的极限。正因为如此，现代压缩技术通常只将 Huffman视作最终的编码手段，而非数据压缩算法的全部。 科学家们一直没有放弃向信息熵极限挑战的理想。 1968 年前后， P. Elias 发展了 Shannon 和 Fano 的编码方法，构造出从数学角度看来更为完美的 Shannon-Fano-Elias 编码。沿着这一编码方法的思路， 1976 年， J. Rissane

8、n 提出了