基于游程编码数据压缩算法的设计与实现毕业论文.doc

基于游程编码数据压缩算法的设计与实现毕业论文 目 录摘要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 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 课题背景信息时代人们对使用计算机获取信息、处理信息的依赖性越来越高。多媒体计算机系统面临的是数值、文字、语言、音乐、图形、动画、静图像、电视视频图像等多种媒体承载的由模拟量转化成数字量信息的吞吐、存储和传输的问题。数字化了的视频和音频信号的数量之大是惊人的，与硬件技术所能提供的计算机存储资源和网络带宽之间有很大差距1。这样，对多媒体信息的存储和传输造成了很大困难，成为阻碍人们有效获取和利用信息的一个瓶颈问题。多媒体信息使用的前提是进行有效的压缩。例如一段时间长度为1 min，图像尺寸为640480 pixete，每秒播放30帧的非压缩彩色24位真彩色视频的信息量为：64048033060：1658880000Bytes，约为1.6GB(未含音频信息的容量)，如果用650 MB的CD-R来存放，需要3张。由此可见，在视频信息的处理及应用过程中压缩及解压缩技术是十分必要的2。 数据压缩技术主要采用两种方法：一种是“保真率”较高的无损压缩法；另一种是以损失信息细节而换取较高压缩比的有损压缩法。无损压缩虽然压缩比不是很高，但还原后的文件与原数据文件完全相同，从而保证了信息细节的不失真，常用的方法有统计式压缩法和字典式压缩法，统计式压缩法的编码方案主要是霍夫曼(Hufman)编码、算术编码(AC)和游程长度编码(RLC)2。其中，游程长度编码是一种十分简单的压缩方法，编码解码的速度也非常快，因此得到了广泛的应用。许多图形和视频文件，如BMP，.TIF及.AVI等，都采用了这种压缩方法，尤其适用于文本(文件)数据压缩，它主要是去除文本中的冗余字符或字节中的冗余位以达到减少数据文件所占的存储空间的目的6。飞速发展的数据压缩和图像编码技术，给多媒体数据传输和数据存储带来极大的快捷和便利。但在某些数据安全性要求比较苛刻的领域，现在比较流行和压缩效果好的压缩算法几乎都属于有损范畴，对原始数据压缩处理后有不同程度的损伤，无法完全恢复，以至于不能满足技术要求，现有的无损压缩方法，如Huffman、LZ 系列、算术编码等压缩方法尽管在某些方面各有优点，但压缩效果比较差或者算法实现比较困难，因此十分有必要对无损压缩算法进行研究4。通过对游程编码(Run LengthEncoding,RLE)进行研究,结合哈夫曼编码。最后找到一种实现相对简单、压缩效果比较好的方法，即对游程编码后的数据在进一步的进行哈夫曼编码，采用该方法可以收到比较理想的效果。1.2选题目的、意义飞速发展的数据压缩和图像编码技术，给多媒体数据传输和数据存储带来极大的快捷和便利。但在某些数据安全性要求比较苛刻的领域，现在比较流行和压缩效果好的压缩算法几乎都属于有损范畴，对原始数据压缩处理后有不同程度的损伤，无法完全恢复，以至于不能满足技术要求，现有的无损压缩方法，如Huffman、LZ 系列、算术编码等压缩方法尽管在某些方面各有优点，但压缩效果比较差或者算法实现比较困难，而游程编码却是一种是一种非常简单，且编码、解码速度很快编码方法。所以通过对于游程编码的研究能够比较快捷语简单的实现对于数据的无损压缩。1.3主要内容 本文主要介绍了信源编码中的几种最佳变长编码方法：香农（Shannon）、费诺（Fano）、哈夫曼（Huffman）编码，以及这几种编码的编码过程。然后主要描述了哈夫曼编码方法以及如何构造哈夫曼树。然后详细的介绍了游程编码的编码算法以及游程编码的特点。画出游程编码哈夫曼编码的流程图，以及得出的结果图，最后做出总结。 第2章 信源编码分类2.1 信源编码 2.1.1信源编码简介 编码实质上就是对信源的原始符号按一定规则进行的一种变换。编码可分为信源编码和信道编码。由于信源符号之间存在分布不均匀和相关性，使得信源存在冗余度，信源编码的主要任务就是减少冗余，提高编码效率。具体的说就是针对信源输出符号序列的统计特性，寻找一定的方法把信源输出符号序列变换为最短码字序列的方法。信源编码的基本途径有两个：使序列中的各个符号尽可能地相互独立，即解除相关性；使编码中各个符号出现的概率尽可能地相等，即概率均匀化。采用的一般方法是压缩每个信源符号的平均比特数或信源的码率。即同样多的信息用较少的码率传送,使单位时间内传送的平均信息量增加,从而提高通信的有效性3。 2.1.2信源编码的理论基础信源编码就是从信源符号到码符号的一种映射f，它把信源输出的符号ui变换成码元序列wi。 信源编码定义如图2-1：图2-1信源编码定义图信源编码理论是信息论的一个重要分支,其理论基础是信源编码的两个定理。 无失真信源编码定理：是离散信源/数字信号编码的基础； 限失真信源编码定理：是连续信源/模拟信号编码的基础。 2.1.3信源编码的分类及作用信源编码的分类： 离散信源编码：独立信源编码,可做到无失真编码； 连续信源编码：独立信源编码,只能做到限失真信源编码； 相关信源编码：非独立信源编码。 编码的作用： 信源编码的作用之一是设法减少码元数目和降低码元速率，即通常所说的数据压缩：作用之二是将信源的模拟信号转化成数字信号，以实现模拟信号的数字化传输。 2.1.4信源编码的历史 最原始的信源编码就是莫尔斯电码，另外还有ASCII码和电报码都是信源编码。但现代通信应用中常见的信源编码方式有：Huffman编码、算术编码、L-Z编码，这三种都是无损编码，另外还有一些有损的编码方式。信源编码的目标就是使信源减少冗余，更加有效、经济地传输，最常见的应用形式就是压缩。另外，在数字电视领域，信源编码包括 通用的MPEG2编码和H.264（MPEGPart10 AVC）编码等 相应地，信道编码是为了对抗信道中的噪音和衰减，通过增加冗余，如校验码等，来提高抗干扰能力以及纠错能力4。2.2最佳变长编码凡是能载荷一定的信息量，且码字的平均长度最短，可分离的变长码的码字称为最佳变长码。为此必须将概率大的信息符号编以短的码字，概率小的符号编以长的码字，使得平均码字长度最短。能获得最佳编码的方法主要有：香农（Shannon）、费诺（Fano）、哈夫曼（Huffman）编码等。2.2.1香农编码方法 香农第一定理指出了平均码长与信源之间的关系，同时也指出了可以通过编码使平均码长达到极限值，这是一个很重要的极限定理。如何构造这种码？香农第一定理指出，选择每个码字的长度Ki满足下式 I(xi)KI(xi)+1, （2-1）就可以得到这种码。这种编码方法就是香农编码。 香农编码法冗余度稍大，实用性不大，但有重要的理论意义。编码步骤如下：1）将信源消息符号按其出现的概率大小依次排列 p（x1）p（x2）p（xn） （2-2）2）确定满足下列不等式整数码长Ki： -log2p(xi)Ki-log2p(xi)+1 （2-3）3)为了编成唯一可译码，计算第i个消息的累加概率 Pi=p(xk) （2-4）4)将累加概率Pi变成二进制数。5)取Pi二进制数的小数点后Ki位即为该消息符号的二进制码字。设信源共7个符号消息，其概率和累加概率如表2-1，则其香农编码过程如表2-1。所以信源符号的平均码长为： （2-5） 平均信息传输率即编码效率为： （2-6） 表2-1 香农编码过程信源消息符号Ai符号概率P(Ai）累加概率Pi-logp(Ai)码字长度Ki码字A1A2A3A4A5A6A00.0100.20.390.570.740.890.992.342.412.482.562.743.346.663333347000001011100101111011111102.2.2费诺编码方法费诺编码，它编码后的费诺码要比香农码的平均码长小，消息传输速率大，编码效率高，但它属于概率匹配编码它不是最佳的编码方法。费诺编码步骤：（1） 将信源消息符号按其出现的概率大小依次排列： 。（2）将依次排列的信源符号按概率值分为两大组，使两个组的概率之和近似相同，并对各组赋予一个二进制码元“0”和“1”。（3）将每一大组的信源符号再分为两组，使划分后的两个组的概率之和近似相同，并对各组赋予一个二进制符号“0”和“1”。（4）如此重复，直至每个组只剩下一个信源符号为止。 (5) 信源符号所对应的码字即为费诺码。对表2-1中信源消息进行费诺编码，则编码过程如表2-2。则该费诺编码的平均码长：（2-7）信息传输速率（2-8）表2-2费诺编码过程消息符号Ai消息概率P（Ai）第一次分组第二次分组第三次分组第四次分组二元码字码长KiA10.2000002A20.19100103A30.1810113A40.1710102A50.15101103A60.101011104A70.01111114显然费诺码要比上述香农码的平均码长小，消息传输速率大，说明编码效率高。2.2.3哈夫曼编码方法 哈夫曼编码是一种常见的压缩方法。它的基本原理是按照信号出现概率大小顺序排列信源信号，并设法按逆序分配码字字长，使编码的码字是可辨识的。哈夫曼编码步骤：（1） 首先把信源中的消息出现的频率从小到大排列。（2） 每一次选出频率最小的两个值，作为二叉树的两个叶子节点，将和作为它们的根节点，这两个叶子节点不再参与比较，新的根节点参与比较。（3） 重复(2)，直到最后得到和为1的根节点。（4） 将形成的二叉树的左节点标0，右节点标1。把从最上面的根节点到最下面的叶子节点途中遇到的0，1序列串起来，就得到了各个符号的编码。对表2-1中的信源数据进行哈夫曼编码，编码过程如表2-3。表2-3哈夫曼编码过程信源符号Ai概率p(Ai)编码过程码字Wi码长KiA10.20 0.26 0.35 0.39 0.61 0 1 102A20.19 0.20 0.26 0.35 0 0.39 1112A30.18 0.19 0.20 0 0.26 10003A40.17 0.18 0 0.19 10013A50.15 0 0.17 10103A60.100 101104A70.01101114该哈夫曼码的平均码长为（2-9）信息传输速率 （2-10） 由此可见，哈夫曼编码的平均码长最小，消息传输速率最大，编码效率最高。哈夫曼编码是用概率匹配方法进行信源编码。他有两个明显的特点：一是哈夫曼码的编码方法保证了概率大的符号对应于短码，概率小的符号对应于长吗，充分利用了短码；二是缩减信源的最后两个码字总是最后一位不同，从而保证哈夫曼编码是即时码6。 哈弗曼编码几乎是所有压缩算法的基础，其实这个算法并不复杂，简单的理解就是，如何用更短的bit来编码数据。 我们知道普通的编码都是定长的，比如常用的ASCII编码,每个字符都是8个bit:字符编码A00101001B00101010C00101011.这样，计算机就能很方便的把由0和1组成的数据流解析成原始信息，但我们知道，在很多情况下，数据文件中的字符出现的概率是不均匀的，比如在一篇英语文章中，字母“E”出现的频率最高，“Z”最低，如果我们使用不定长的bit编码，频率高的字母用比较短的编码表示，频率低的字母用长的编码表示，岂不是可以大大缩小文件的空间吗? 但这就要求编码要符合“前缀编码”的要求，即较短的编码不能是任何较长的编码的前缀，这样解析的时候才不会混淆，比如下面的编码方法就符合前缀原则：字符编码A0B10C110D1110E11110.根据这个码表，下面一段数据就可以唯一解析成原始信息了： 1110010101110110111100010 DABBDCEAAB要生成这种编码，最方便的就是用二叉树，考察一下下面这个树图2-2二叉树图 把要编码的字符放在二叉树的叶子上，所有的左节点是0，右节点是1，从根浏览到叶子上，因为字符只能出现在树叶上，任何一个字符的路径都不会是另一字符路径的前缀路径，符合前缀原则编码就可以得到字符编码A00B010C011D10E11 现在我们可以开始考虑压缩的问题，如果有一篇只包含这五个字符的文章，而这几个字符的出现的次数如下： A: 6次 B : 15次 C: 2次 D : 9次 E: 1次用过用定长的编码，每个字符3bit，这篇文章总长度为： 3*6 + 3*15 + 3*2 + 3*9 + 3*1 = 99 （2-11）而用上面用二叉树生成的编码，总长度为: 2*6 + 3*15 + 2*2 + 2*9 + 2*1 = 80 （2-12）显然，这颗树还可以进一步优化，使得编码更短，比如下面的编码 图2-3二叉树图 生成的数据长度为： 3*6 + 1*15 + 4*2 + 2*9 + 4*1 = 63 (2-13) 可以看出，构造更优的二叉树，原则就是权重越大的叶子，距离根应该越近，而我们的终级目标是生成“最优”的二叉树，最优二叉树必须符合下面两个条件：所有上层节点都大于等于下层节点。某节点，设其较大的子节点为，较小的子节点为，下的任一层的所有节点都应大于等于下的该层的所有节点。 上面这个例子是比较简单的，实际的文件中，一个字节有256种可能的取值，所以二叉树的叶子节点多达256个，最终的树形可能非常复杂，但有一种非常精巧的算法可以快速地建起一棵最优二叉树，这种算法由D.Huffman（戴?哈夫曼）提出，下面我们先来介绍哈弗曼算法的步骤，然后再来证明通过这么简单的步骤得出的树形确实是一棵最优二叉树。 哈夫曼算法的步骤是这样的：从各个节点中找出最小的两个节点，给它们建一个父节点，值为这两个节点之和。然后从节点序列中去除这两个节点，加入它们的父节点到序列中。重复上面两个步骤，直到节点序列中只剩下唯一一个节点。这时一棵最优二叉树就已经建成了，它的根就是剩下的这个节点。 比如上面的例子，哈弗曼树建立的过程如下:1) 列出原始的节点数据： 图2-4原始节点2) 将最小的两个节点C和E结合起来：图2-5C和E结合3) 再将新的节点和A组合起来 图2-6新节点结合图 4) 再将D节点加入 图2-7新节点结合图5) 如此循环，最终得到一个最优二叉树 图2-8最优二叉树图生成的数据文件长度为： 3*6 + 1*15 + 4*2 + 2*9 + 4*1 = 63 下面我们用逆推法来证明对于各种不同的节点序列，用哈弗曼算法建立起来的树总是一棵最优二叉树：当这个过程中的节点序列只有两个节点时（比如前例中的15和18），肯定是一棵最优二叉树，一个编码为0，另一个编码为1，无法再进一步优化。然后往前步进，节点序列中不断地减少一个节点，增加两个节点，在步进过程中将始终保持是一棵最优二叉树，这是因为:按照哈弗曼树的建立过程，新增的两个节点是当前节点序列中最小的两个，其他的任何两个节点的父节点都大于（或等于）这两个节点的父节点，只要前一步是最优二叉树，其他的任何两个节点的父节点就一定都处在它们的父节点的上层或同层，所以这两个节点一定处在当前二叉树的最低一层。这两个新增的节点是最小的，所以无法和其他上层节点对换。符合我们前面说的最优二叉树的第一个条件。只要前一步是最优二叉树，由于这两个新增的节点是最小的，即使同层有其他节点，也无法和同层其他节点重新结合，产生比它们的父节点更小的上层节点来和同层的其他节点对换。它们的父节点小于其他节点的父节点，它们又小于其他所有节点，只要前一步符合最优二叉树的第二个条件，到这一步仍将符合。 这样一步步逆推下去，在这个过程中哈弗曼树每一步都始终保持着是一棵最优二叉树。2.3游程编码2.3.1游程长度 游程长度RL(Run-Length)，简称游程或游长，指的是由字符(或信号取样值)构成的数据流中各个字符重复出现而形成的字符的长度。如果给出了形成串的字符，串的长度以及串的位置，就能恢复出原来的数据流，游程长度编码(RLC)就是用二进制码字给出这些信息的一类方法。2.3.2游程编码算法 游程编码的基本原理是：用一个符号值或串长代替具有相同值的连续符号（连续符号构成了一段连续的“游程”，游程编码因此而得名），使符号长度少于原始数据的长度。只在各行或者各列数据的代码发生变化时，一次记录该代码及相同代码重复的个数，从而实现数据的压缩。 在二元序列中，只有两种符号，即“0”和“1”，这些符号可连续出现，连“0”这一段称为“0”游程，连“1”这一段称为“1”游程。它们的长度分别称为游程长度L(0)和L(l)。“0”游程和“l”游程总是交替出现的。如果规定二元序列是以“0”开始，第一个游程是“0”游程，第二个必为“1”游程，第三个又是“0”游程等等。对于随机的二元序列，各游程长度将是随机变量，其取值可为1，2，3，直到无限。 将任何(二元)序列变换成一一对应的游程长度序列，再按哈夫曼编码或其他方法处理以达到压缩码率的目的9。2.3.3游程编码特点 游程编码仍是变长码，有其固有的缺点，及需要大量的缓冲和优质的信道。此外，编程长度可以从一直到无限，这在码字的选择和码表的建立方面都有困难，实际应用是尚需采用某些措施来改进。 一般情况下游程长度越长，其概率越小，这在以前的计算中也可以看见，而且将随着长度的增大渐进向零。对于小概率的码字，其长度为达到概率匹配或较长，损失不会太大，也就是对平均码字长度影响较小。再按哈夫曼编码或其他方法处理以达到压缩码率的目的。2.3.4几种基于游程相关性的数据压缩方案1）共前缀码 共前缀码编码时也是按照一定规律用尽量短的码字来表示游程形式的初始测试数据，但该编码压缩方案进一步考虑了相邻游程之间存在的联系。如果相邻游程的长度在同一组，则它们对应码字的前缀是相同的即共前缀，可以用一个标志位来表示这些相邻游程除第一个游程以外的其他游程的前缀，这样数据压缩率得以进一步提高。同组共前缀码的前缀和后缀的位数相同，前缀和后缀相加对应的十进制数比对应的游程长度多2，也就是说跟FDR 码相比，相同的码字所表示的游程长度少2，使压缩效果受到一些影响，因此对初始测试数据进行无关位(dont cares bit)填充时，要尽量时这种影响降到最低。所谓无关位是指无论它们的取值是0 还是1 都不会影响测试结果。不过由此也可看出待测试数据的游程长度加上2 所对应的FDR 码就是相应的共前缀码，若这两个相差为2 的游程长度在同一组内，则码字长度并没有增加，不会影响压缩效果。 共前缀码的前缀都是以1 开始，以0 结束的数字串，所以当相邻游程长度在同一组时，可以用数字0 来表示后面游程的码字前缀，后缀则不变，这样码字的长度进一步缩短。下面给出一个共前缀编码的实例：编码前的初始测试数据： 000000001 1 0000001 000000000000010000000000000001（47 位）；编码后的码字：110100 1000 110010 11100001 00011（29 位）。可见数据串00000000000001 和0000000000000001 的游程长度分别为13 和15，都在第三组，前缀都为1110，所以后一游程的码字前缀用标志位0 表示，其码字为0 0011。2）共游程码 前面介绍的共前缀码是利用游程长度同组的前缀相同，用标志位0 加码字后缀来表示后面的游程，从而进一步压缩初始测试数据。共游程码（Sharing Run Length Code，SRLC）与共前缀码的编码方案类似，该方案注意到初始测试数据中有的相邻游程是相同的，于是就用一个标志位来表示后面的相同游程，所以该方案被称为共游程码。显然该编码方案的数据压缩率比共前缀码高一些，不考虑相邻游程的长度相同的前提下，编码方法与共前缀码相同。对共游程码编码方案，如果有若干相邻游程相同，则后面的一个或多个相同游程都可以用唯一的标志位来代替，从而大大减少了编码码字的长度，即进一步提高了测试数据压缩率。共游程码的前缀都是以“1”开头以“0”结尾的数字串，没有以“0”开头的前缀，所以可以用数字0 来作为相邻相同游程的标志位，即后面相邻相同游程的码字只有1 位。显然相邻相同游程的长度越长，测试数据压缩率就越高。由于初始测试数据中存在着大量的无关位，可以有意识的对它们进行赋值填充，以增加长度相同的相邻游程的数量，从而降低码字的长度。例如数据串00000000000x 000000000001，其中的x 是无关位，如果把它填充为0则该数据串是一个长度为23 的0 游程，由编码码表可知其对应的码字为11101011（8 位）；如果把无关位赋值为1，则数据串变成了两个长度都为11的相邻0 游程，其对应的码字为110111 0（7 位），使码字的长度减少了1 位，提高了数据压缩效果。3）共前缀连续长度码共前缀连续长度码（Co- Prefixal Run Length codes，CPRL）也考虑了相邻游程的相关性。如果相邻游程的长度在同一组内，则同组的后面的相邻游程的前缀可以省略，则编码后码字的前缀越长，则压缩效果越明显。由于初始测试数据集中存在大量的无关位，可以适当的对这些无关位进行赋值填充，增加0 游程的长度，这些游程长度在同组的概率很高。该编码方案为了增加0 游程的长度，对填充后的测试数据采取了差分处理，即把测试数据等长划分并进行异或逻辑运算。通过对ISCAS- 89 基准电路硬故障测试集的分析对不同的电路各组共前缀次数的分布不均匀，因此CPRL码引入了一个参变量M,M 表示确定的组号，M 取值不同，编码结果就不同。但对于具体的编码，M 是事先确定好的常数，显然M 的取值范围在1 和最大组号之间。 CPRL 码的具体编码方法如下：若待编码的0 游程长度所在的组号M,则直接用FDR 码字表示CPRL 码字，原因是组号小的码字前缀位数也短；若待编码的0 游程长度所在的组号M，且相邻游程长度在同一组内，则后面的游程CPRL码字由该游程长度对应的FDR 码字省略前缀，并在剩下的码字后缀后面加上一个标志位0 组成，同组相邻的第一个游程的CPRL 码字由对应的FDR 码字加上标志位1 组成；若待编码的0 游程长度所在的组号M，且相邻游程长度不在同一组内，则各游程的CPRL 码字由对应的FDR 码字加一位标志位组成。下面给出一个CPRL 码的编码实例：（参变量M=1）编码前的初始测试数据：0000001 0000001 0000111 0010111 1010010；对应的差分测试数据： 0000001 0000000 0000110 0010000 1000101（35位）；差分后的测试数据对应的FDR 码：110000 110101 00 1001 1010 1001 01（28 位）；对应的CPRL 码字：1100001 1010 00 10011 101 010 01（26 位）。2.4本章小结 本章主要介绍了信源编码中的几种最佳信源变长编码:香农（Shannon）、费诺（Fano）、哈夫曼（Huffman）编码，以及这几种编码的编码过程,然后主要介绍了哈夫曼树的构成步骤，以及游程编码的算法和编码特点。73 第3章 游程编码以及哈弗曼编码 第3章 游程编码以及哈夫曼编3.1 游程编码 游程编码是针对于二元序列的压缩编码方法，在二元序列中，只有两种符号，即“0”游程和“1”游程，“0”游程和“l”游程总是交替出现的。如果规定二元序列是以“0”开始，第一个游程是“0”游程，第二个必为“1”游程，第三个又是“0”游程等等。而对二元序列游程编码主要是针对于每个游程长度以及总共有多少个游程。我在c语言编码过程中主要针对这两方面进行编码，即通过对“0”、“1”的变换次数来确定二元序列中总共有多少个游程；然后在确定每一个游程中游程的长度。两者综合即实现对于二元序列的游程编码。 用游程编码压缩数据时，首先要计算每次连续相同字符的个数，然后将每次连续相同的字符及个数保存起来。这种压缩数据的方法, 连续相同的字符及出现连续相同的次数越多，压缩比就越大，反之，压缩比就越小。数据压缩算法流程如下： 1) 打开源数据文件和压缩后的数据文件； 2) 从源数据文件中读取字符, 并把它放入一个寄存器中，然后再循环读取后面的字符，并与寄存器中的字符相比较。如果相等，则计数器加1，否则，把寄存器中的字符和计数器中数写入压缩数据文件中，然后再把寄存器中字符不相等的字符放入寄存器中，并把计数器置1。游程编码数据压缩算法流程图如图3-1：数据解码算法流程如下： 1) 打开压缩数据文件和恢复文件； 2) 从压缩文件中循环读出字符和该字符连续的个数, 在恢复文件中连续写入从压缩文件中读出的字符, 写的次数等于该字符连续的个数:。游程编码数据解压缩算法流程图3-2图3-1游程编码数据压缩算法游程图图3-2游程编码数据解码流程图3.2哈夫曼编码过程 哈夫曼编码是一种常见的压缩方法。它的基本原理是按照信号出现概率大小顺序排列信源信号，并设法按逆序分配码字字长，使编码的码字是可辨识的。 要完成哈夫曼的编码需要首先建立哈夫曼树，之后对所有字符根据权重进行编码，最后再对文件内容进行编码。 建立哈夫曼树的思想。首先定义适合哈夫曼树的节点类型，需要定义的有当前节点的字符，当前节点的左子、右子和父亲指针。在建立哈夫曼树之前还需要对出现的字符和权重进行统计和记录，并且定义一个可以筛选出最小权重的函数。 初始化树节点之后开始建立哈夫曼树。先在所有可能出现的字符中筛选出当前权重最小的两个字符，将这两个字符分别作为新节点的左子和右子建立一个小的二叉树，并将两个字符的权重之和赋值给新节点，将新二叉树放入筛选字符中，再将筛选过的两个字符从筛选列表中淘汰掉。依次对列表中剩下的字符进行权重最小的筛选，直到根节点（如果编码表共有N个字符，则2*N-1就为最终根节点）为止，也就是当筛选列表为空的时候，哈夫曼树即建立完成。对于哈夫曼编码树来说，由于哈夫曼编码是前缀码，所以所有要编码的字符最终都将是这颗树的叶子节点，而其它节点并没有真正的字符意义。即当哈夫曼编码树建立之后，对树的所有叶子节点进行打印可知道是否有字符遗漏或多余。 建立哈夫曼树的流程图如图3-3：图3-3构建哈夫曼树流程图 构建完哈夫曼树后，根据建立哈夫曼树建立哈夫曼码表。建立编码表时要根据每个出现的字符的权重对建立的哈夫曼树的每个叶子节点进行编码。编码时要从叶子节点出发向根节点进行逆向编码。判断如果当前节点为左子则对其编码0，如果当前节点为右子则对其编码1。以此类推进行编码直到根节点为止。此时的编码是逆向的，所以需要将码值逆向存储。依次对每一个叶子节点进行编码操作，即可得到当前哈夫曼树的编码表。 构建哈夫曼编码表的算法流程图如图3-4：图3.3构建哈夫曼编码表的算法流程图有了码表就可以进行编码了。首先需要建立一个原始文件，在文件中输入需要编码的内容。之后将文件打开，将其中的内容存储到字符串中以便程序编码调用。开始对需要编码的字符进行编码，将字符逐一读取与刚刚建立的编码表中的每个叶子节点代表的字符进行比较，找出相同的对象，并将当前节点的编码打印到屏幕，并将编码存入到新建的密码文件当中。编码流程图如图3.4：图3.4编码算法流程图在解码时先打开密码文件，将之前编码后得到的密文内容存储到字符串中以便解码调用。开始对密文的字符串进行解码，树索引从根节点开始走，当密文中的当前字符是0的时候，则索引走向左子节点；当是1的时候，则走向右子节点。以此类推，一直走到叶子节点为止，则当前叶子节点所代表的字符即为前一段密文的解码结果，。再对下一个字符依次从根节点开始解码，如此循环对每一段密文进行解码直到解码结束。将解码打印到屏幕，并将解码结果存入到新的解码文件当中。在解码之前，还应该先确认之前是否建立了哈夫曼树并且是否构建了编码表。不过由于本次将a到z都进行了编码，所以此步省略了，因为编码表是唯一的。需要的时候可以在Encoder 函数中先进行判定。图3.5解码算法流程图3.3运行结果对于二元序列：00011100001111100011111111110000000000000111110000000000000即（3,0）（3,1)（4,0）（5,1）(3,0)(10,1)(13,0)(5,1)(13,0)编码图：解码图：进行完编码后的平均码长为： （3-1)信息传输速率： （3-2） 压缩前二元序列长度为49，进行游程编码后序列长度为36，再进行哈夫曼编码后序列长度为29。即总的压缩效率为59%，而游程压缩效率为80%。所以进行两次编码后的压缩效率比单一一次的游程编码的压缩效率高很多。这次的仿真只是对于一段很短的二元序列，而且各游程长度也很短，所以还不能过很好的体现出游程编码的压缩效率。但对于二值图像序列的就能够很好的体现出游程编码的压缩效率，然后在进行哈夫曼编码就能够很好的体现出这种方法的压缩效率。3.4本章小结游程编码是一种简单的快捷的编码方法，能够有效的对二元序列进行无损压缩，一般情况下，游程长度越大，其概率越小，而且随着长度的增大逐渐趋向零。对于小概率的码字，其长度未达到概率匹配或较长，损失不会太大，也就对平均码字长度影响较小，这样就可以对长游程不严格按哈夫曼码步骤进行。哈夫曼码是用概率匹配方法进行信源编码。它有两明显的个特点：一是哈夫曼编码方法保证了概率大的符号对应于短码，概率小的符号对应于长码，充分利用了短码；一是缩减信源的最后两个码字总是最后一位不同，从而保证哈夫曼编码是即时码。哈夫曼变长码的效率是相当高的，它可以单个信源符号编码或用L较小的信源序列编码，对编码器的设计来说也简单的多。但应当注意要达到很高的效率仍然需要按长序列来计算，这样才能使平均码字长度降低。参考文献 结论游程编码是图像压缩的基本算法，因此对于二元相关信源数据编码研究变得尤为重要。为此，本人对游程编码压缩原理做了深入的学习，并结合哈夫曼编码把其应用到二元相关信源数据的压缩。经过这段时间的学习与实践，我对二元相关信源游程编码与信号编码的发展及现状有了更深刻的认识，意识到数据压缩与解压对于信息时代的巨大影响及其潜在的经济效益，并对Microcsoft Visual C+软件有了进一步的了解。经过这一段的学习，我想我对于知识的猎取是有限的，关键是我学会了如何用认真、严谨的学习态度去面对工作，如何用自学的方法来处理问题，如何把书籍和网上查找到的信息运用到实践中去。二元相关游程编码一般不直接应用与多灰度图像，但比较适于二值图像的编码，例如传真图像的编码等。为了达到较好的压缩效果，二值图像游程编码需和其它一些编码混合使用。本文中我才用游程编码和哈夫曼编码混合使用。游程压缩作为数据压缩技术的一个分支，理论浅显，走过半个多世纪的离散余弦变换理论在数据压缩领域至今不衰；近来，小波变换理论更使数据压缩技术登峰造极，图像压缩的JPEG2000标准是小波理论傲视群雄。可以预见，新的数学理论将不断为数据压缩技术输入新鲜血液，因此数学理论决不可偏废。最后，给出一点使用无损压缩算法的建议。由于每种无损压缩都有自己的适用范围，压缩比受不失真要求的限制，真正意义上高压缩比的通用无损压缩算法目前哈有待继续研究。因此在选用算法之前需要对图像数据进行分析，使用时根据数据表现出的特点，利用算法的思想，灵活使用算法是提高压缩比的有效手段。 参考文献1王增辉， 雷加.一种变游程编码的测试数据压缩方法.理论与方法.2009.52许川佩，董祥健.一种交替游程编码的SOC测试数据压缩方法.计算机工程与应用.2010，46（25）3刘娟，詹文法，黄忠.基于交替变游程编码的测试数据压缩方法.安庆师范学院学报.2011.54詹文法，梁华国，时峰，黄正峰，欧阳一鸣.一种共游程的测试数据压缩方案.计算机研究与发展.20085彭喜元，俞洋.基于变游程编码的测试数据压缩算法.电子学报.2007.26于翔。数据压缩技术分析。青海大学学报.2002.87祝本明，刘桂华。一种改进的游程编码算法.西南科技大学学报.2007.98Michal Stabno，Robert Wrembel.RHL:Bitmap compression technique based on run-length and Huffman encoding.Information Systems.20099Cristiano M. Agulhari, Ivanil S. Bonatti, Pedro L.D. Peres.An Adaptive Run Length Encoding method for the compression ofelectrocardiograms.Medical Engineering & Physics.201310马宁 ,朱福萌 ,尹志军, 蒋林辉.改进游程编码在天气雷达数据压缩中的应用.解放军理工大学学报.200411谭红.一种基于游程编码的显存压缩算法.电子工程师.2007.312Bo Ye , QianZhao , DuoZhou , XiaohuaWang , MinLuo .Test data compression using alternating variable run-length code .INTEGRATION, the VLSI journal .201113商进，张礼勇.一种双游程编码的测试数据压缩方案.哈尔滨理工大学学报.2010.814方建平,郝跃,刘红侠,李康.应用混合游程编码的SOC 测试数据压缩方法.电子学报.2005.11致谢 致谢本设计的完成是在我们的导师许成谦老师的细心指导下进行的。在每次设计遇到问题时老师不辞辛苦的讲解才使得我的设计顺利的进行。从设计的选题到资料的搜集直至最后设计的修改的整个过程中，花费了许老师很多的宝贵时间和精力，在此向导师表示衷心地感谢！导师严谨的治学态度，开拓进取的精神和高度的责任心都将使学生受益终生！ 还要感谢和我同一设计小组的几位同学，是你们在我平时设计中和我一起探讨问题，并指出我设计上的误区，使我能及时的发现问题把设计顺利的进行下去，没有你们的帮助我不可能这样顺利地结稿，在此表示深深谢意。附录 附录1燕 山 大 学本科毕业设计（论文）开题报告课题名称： 基于游程编码数据压缩算法设计与实现学院（系）： 电子工程系 年级专业： 09通信工程 学生姓名： 李悦 指导教师： 许成谦 完成日期： 2013年3月27日 1、 选题的依据： 飞速发展的数据压缩和图像编码技术，给多媒体数据传输和数据存储带来极大的快捷和便利。但在某些数据安全性要求比较苛刻的领域，现在比较流行和压缩效果好的压缩算法几乎都属于有损范畴，对原始数据压缩处理后有不同程度的损伤，无法完全恢复，以至于不能满足技术要求，现有的无损压缩方法，如Huffman、LZ 系列、算术编码等压缩方法尽管在某些方面各有优点，但压缩效果比较差或者算法实现比较困难，因此十分有必要对无损压缩算法进行研究。通过对游程编码(Run LengthEncoding,RLE)进行研究,最后提出一种实现相对简单、压缩效果比较好的算法，采用该算法可以收到比较理想的效果，基本克服由于RLE自身特点而引起的数据扩张的现象。 目前已提出的比较有效的测试压缩编码算法主要有3大类：（1）基于统计的编码压缩算法，如哈夫曼（Huffman）编码、VIHC编码；（2）基于游程（run-length coding）的编码压缩算法，如Golomb编码、FDR（Frequency-directed run-length）编码算法、Variable-Tail算法、交替游程算法（alternating run-length）；（3）基于字典的编码算法，如Fixed-Length-Index-Dictionary算法、CDCR（combining dictionary coding and LFSR reseeding）。在以上编码方法中，基于游程的编码压缩算法的效果是较好的，而且这种压缩算法的解压电路是不依赖于测试向量集的，这一点在待测电路重新设计或测试向量集合发生修改的情况下特别有用1。 基于游程编码中的各种编码:（1）Golomb码和FDR码都是基于测试集中0 个数多于1 个数的事实而对连续的0 进行编码，并未把连续的0 和1 都进