《本科毕业设计（论文）基于游程编码数据压缩算法设计与实现39888》由会员分享，可在线阅读，更多相关《本科毕业设计（论文）基于游程编码数据压缩算法设计与实现39888（82页珍藏版）》请在金锄头文库上搜索。
1、本科毕业设计（论文）基于游程编码数据压缩算法的设计与实现2013年6月 摘 要 本次毕业设计主要是针对于游程编码数据压缩算法的设计与实现，游程编码非常简单，编码、解码速度快，应用广泛。游程编码是针对于二元序列的一种编码方法，对于二值图像而言是一种编码方法，对连续的黑、白像素数(游程)以不同的码字进行编码。游程编码是一种简单的非破坏性资料压缩法，其好处是加压缩和解压缩都非常快。其方法是计算连续出现的资料长度压缩之，其缺点是对于不重复的资料反而加大容量。游程编码即需大量的缓冲和优质信道，所以对数据游程编码后在进一步的进行哈夫曼编码已达到更完善的数据压缩。哈夫曼编码使用变长编码表对源符号进行编码，其
2、中变长编码表是通过一种评估来源符号出现机率的方法得到的，出现机率高的字母使用较短的编码，反之出现机率低的则使用较长的编码，这便使编码之后的字符串的平均长度、期望值降低，从而达到无损压缩数据的目的。 本文主要介绍了信源编码的分类、获得最佳编码的方法、哈夫曼树的构建方法以及游程编码的原理和实现技术，对游程长度编码技术做了较为全面地研究。包括游程数据压缩、解压缩过程，并给出了流程图；哈夫曼数据压缩、解压缩过程，并给出流程图和结果图。 关键词游程编码 哈夫曼编码 压缩1 AbstractThis graduation design is mainly based on run-length codin
3、g data compression algorithm design and implementation of run-length coding is very simple, encoding and decoding speed, wide application. Run-length coding is a coding method for binary sequence, is a kind of coding method for binary image, the black and white pixels of continuous (run) in differen
4、t code code word. Run-length coding is a kind of simple nondestructive data compression method, the advantage is that of compression and decompression are very fast. Its method is to calculate a continuous length of data compression, the downside is to not repeat data instead of increasing capacity.
5、 Run-length coding is need a lot of buffer and channel, so the data after the run-length coding in further Huffman encoding has reached more .Source coding is mainly introduced in this paper the classification, the optimal method of coding, Huffman tree, construction methods, and the run-length codi
6、ng principle and implementation technology, the length of the run-length encoding technology is done more comprehensive research. Including the run-length data compression and decompression process, and gives the flow chart; Huffman data compression and decompression process, chart and flow chart is
7、 given and the results.KeywordsRun-length coding Huffman encoding The compression 1 目 录摘要IAbstractII第1章 绪论11.1 课题背景11.2选题目的、意义21.3主要内容2第2章 信源编码分类32.1 信源编码3 2.1.1信源编码简介3 2.1.2信源编码的理论基础3 2.1.3信源编码的分类及作用42.2最佳变长编码4 2.2.1香农编码方法5 2.2.2费诺编码方法6 2.2.3哈夫曼编码方法72.3游程编码15 2.3.1游程长度15 2.3.2游程编码算法15 2.3.3游程编码特点16
8、 2.3.4几种基于游程相关性的数据压缩方案162.4本章小结19第3章 游程编码以及哈夫曼编203.1 游程编码203.2哈夫曼编码过程233.3运行结果283.4本章小结30结论31参考文献33致谢35附录136附录241附录345附录450第2章 信源编码分类 第1章 绪论1.1 课题背景信息时代人们对使用计算机获取信息、处理信息的依赖性越来越高。多媒体计算机系统面临的是数值、文字、语言、音乐、图形、动画、静图像、电视视频图像等多种媒体承载的由模拟量转化成数字量信息的吞吐、存储和传输的问题。数字化了的视频和音频信号的数量之大是惊人的，与硬件技术所能提供的计算机存储资源和网络带宽之间有很大
9、差距1。这样，对多媒体信息的存储和传输造成了很大困难，成为阻碍人们有效获取和利用信息的一个瓶颈问题。多媒体信息使用的前提是进行有效的压缩。例如一段时间长度为1 min，图像尺寸为640480 pixete，每秒播放30帧的非压缩彩色24位真彩色视频的信息量为：64048033060：1658880000Bytes，约为1.6GB(未含音频信息的容量)，如果用650 MB的CD-R来存放，需要3张。由此可见，在视频信息的处理及应用过程中压缩及解压缩技术是十分必要的2。 数据压缩技术主要采用两种方法：一种是“保真率”较高的无损压缩法；另一种是以损失信息细节而换取较高压缩比的有损压缩法。无损压缩虽然
10、压缩比不是很高，但还原后的文件与原数据文件完全相同，从而保证了信息细节的不失真，常用的方法有统计式压缩法和字典式压缩法，统计式压缩法的编码方案主要是霍夫曼(Hufman)编码、算术编码(AC)和游程长度编码(RLC)2。其中，游程长度编码是一种十分简单的压缩方法，编码解码的速度也非常快，因此得到了广泛的应用。许多图形和视频文件，如BMP，.TIF及.AVI等，都采用了这种压缩方法，尤其适用于文本(文件)数据压缩，它主要是去除文本中的冗余字符或字节中的冗余位以达到减少数据文件所占的存储空间的目的6。飞速发展的数据压缩和图像编码技术，给多媒体数据传输和数据存储带来极大的快捷和便利。但在某些数据安全
11、性要求比较苛刻的领域，现在比较流行和压缩效果好的压缩算法几乎都属于有损范畴，对原始数据压缩处理后有不同程度的损伤，无法完全恢复，以至于不能满足技术要求，现有的无损压缩方法，如Huffman、LZ 系列、算术编码等压缩方法尽管在某些方面各有优点，但压缩效果比较差或者算法实现比较困难，因此十分有必要对无损压缩算法进行研究4。通过对游程编码(Run LengthEncoding,RLE)进行研究,结合哈夫曼编码。最后找到一种实现相对简单、压缩效果比较好的方法，即对游程编码后的数据在进一步的进行哈夫曼编码，采用该方法可以收到比较理想的效果。1.2选题目的、意义飞速发展的数据压缩和图像编码技术，给多媒体
12、数据传输和数据存储带来极大的快捷和便利。但在某些数据安全性要求比较苛刻的领域，现在比较流行和压缩效果好的压缩算法几乎都属于有损范畴，对原始数据压缩处理后有不同程度的损伤，无法完全恢复，以至于不能满足技术要求，现有的无损压缩方法，如Huffman、LZ 系列、算术编码等压缩方法尽管在某些方面各有优点，但压缩效果比较差或者算法实现比较困难，而游程编码却是一种是一种非常简单，且编码、解码速度很快编码方法。所以通过对于游程编码的研究能够比较快捷语简单的实现对于数据的无损压缩。1.3主要内容 本文主要介绍了信源编码中的几种最佳变长编码方法：香农（Shannon）、费诺（Fano）、哈夫曼（Huffman
13、）编码，以及这几种编码的编码过程。然后主要描述了哈夫曼编码方法以及如何构造哈夫曼树。然后详细的介绍了游程编码的编码算法以及游程编码的特点。画出游程编码哈夫曼编码的流程图，以及得出的结果图，最后做出总结。 第2章 信源编码分类2.1 信源编码 2.1.1信源编码简介 编码实质上就是对信源的原始符号按一定规则进行的一种变换。编码可分为信源编码和信道编码。由于信源符号之间存在分布不均匀和相关性，使得信源存在冗余度，信源编码的主要任务就是减少冗余，提高编码效率。具体的说就是针对信源输出符号序列的统计特性，寻找一定的方法把信源输出符号序列变换为最短码字序列的方法。信源编码的基本途径有两个：使序列中的各个
14、符号尽可能地相互独立，即解除相关性；使编码中各个符号出现的概率尽可能地相等，即概率均匀化。采用的一般方法是压缩每个信源符号的平均比特数或信源的码率。即同样多的信息用较少的码率传送,使单位时间内传送的平均信息量增加,从而提高通信的有效性3。 2.1.2信源编码的理论基础信源编码就是从信源符号到码符号的一种映射f，它把信源输出的符号ui变换成码元序列wi。 信源编码定义如图2-1：图2-1信源编码定义图信源编码理论是信息论的一个重要分支,其理论基础是信源编码的两个定理。 无失真信源编码定理：是离散信源/数字信号编码的基础； 限失真信源编码定理：是连续信源/模拟信号编码的基础。 2.1.3信源编码的
15、分类及作用信源编码的分类： 离散信源编码：独立信源编码,可做到无失真编码； 连续信源编码：独立信源编码,只能做到限失真信源编码； 相关信源编码：非独立信源编码。 编码的作用： 信源编码的作用之一是设法减少码元数目和降低码元速率，即通常所说的数据压缩：作用之二是将信源的模拟信号转化成数字信号，以实现模拟信号的数字化传输。 2.1.4信源编码的历史 最原始的信源编码就是莫尔斯电码，另外还有ASCII码和电报码都是信源编码。但现代通信应用中常见的信源编码方式有：Huffman编码、算术编码、L-Z编码，这三种都是无损编码，另外还有一些有损的编码方式。信源编码的目标就是使信源减少冗余，更加有效、经济地传输，最常见的应用形式就是压缩。另外，在数字电视领域，信源编码包括 通用的MPEG2编码和H.264（M
