一种基于RLE和LZW的优化比特文件压缩与解压缩方法

摘要

一种基于RLE和LZW的优化比特文件压缩与解压缩方法，通过对FPGA配置比特文件进行数据格式分析，抠出比特文件的头部控制字，从真实配置数据开始，采用游长为4的RLE编码进行初步压缩，再进行LZW压缩进一步提升压缩率。解压缩时为压缩的逆过程，先进行LZW解压缩还原出中间数据，再对不包含头部控制字的数据部分进行RLE解压缩，还原出原始的FPGA配置比特文件。该方法综合考虑了压缩/解压缩的时间和压缩率，与Xilinx自带的压缩工具比较，与单纯应用RLE算法，单纯应用LZW算法比较，实现了压缩率与压缩速度的双赢。解决了Xilinx先进型号FPGA配置比特文件过大的问题，节省了存储芯片的开销，为FPGA在轨重构技术提供了关键技术支撑。

权利要求

1.一种基于RLE和LZW的优化比特文件压缩方法，其特征在于：包括步骤如下：

步骤一：FPGA配置比特文件由多部分数据组成，包含头部控制字、数据和命令字，其中，数据和命令字格式都是以四字节为一个单位，抠除FPGA配置比特文件的头部控制字；

初始化RLE中的游长计数器；将RLE的游程长度根据步骤一所述比特文件数据特点设置为4；游长计数器，从1开始计数，即读取第一个字符串时计1，能够在遇到连续重复出现的字符串时每次加1，直到出现不同的字符串时，能够输出游长计数器的值，还原初值1；游长计数器的值为1-255，达到255时还原1；

初始化LZW的压缩字典，使字典包含所有可能的根，所述根为单一词条；LZW的压缩字典用于存储压缩过程中产生的词条，压缩字典的索引值为1-4096；

设置前缀pre_char，令当前前缀pre_char为空；

步骤二：设置字符串pre_string；将步骤一中抠除头部控制字的FPGA配置比特文件的第一个字符串赋给字符串pre_string；所述抠除头部控制字的FPGA配置比特文件为被压缩文件；

步骤三：将被压缩文件进行压缩，步骤如下：

(1)判断被压缩文件中是否有字符串需要压缩，如果没有字符串需要压缩，则先输出字符串pre_string，再输出游长计数器的值，进入步骤四；

(2)如果有字符串需要压缩，设置当前字符串current_string，令当前字符串current_string等于字符流中的下一个字符串；

(3)判断pre_string与current_string是否一致：如果pre_string与current_string一致，游长计数器加1，判断游长计数器值是否计到255；如果游长计数器值计到255，先输出pre_string，再输出游长计数器值，令游长计数器值为1，读取待压缩文件的未压缩的字符串给pre_string，返回步骤三

如果游长计数器值未计到255，返回步骤三；

如果pre_string与current_string不一致，输出pre_string，输出游长计数器值，将此时current_string赋给pre_string，返回步骤三；

步骤四：设定当前字符current_char，按照步骤三(1)输出顺序，将输出依次排列成新的字符流，读取该字符流中的第一个字符赋给current_char；

步骤五：判断pre_char与current_char依次排列组成的词条是否在字典中：如果在字典中，将pre_char与current_char依次排列组成的词条赋给pre_char；如果未在字典中，则输出当前前缀pre_char的码字，添加pre_char与current_char依次排列组成的词条到字典中，将current_char的值赋给pre_char；

步骤六：判断新的字符流中是否还有字符需要压缩，如果有字符需要压缩，将需要压缩的第一个字符赋给current_char，返回步骤五；如果没有字符需要压缩，输出当前前缀pre_char的码字，完成压缩。

2.根据权利要求1所述的一种基于RLE和LZW的优化比特文件压缩方法的解压缩方法，其特征在于：包括步骤如下：步骤一：初始化解压缩字典，使字典包含所有可能的根，所述根为单一词条；

步骤二：设置变量pw，读取待解压缩数据流中第一个码流，赋值给pw，以pw为索引查询解压缩字典，读取该索引对应的词条，设置字符串变量pre_char，将pw表示的索引对应的词条赋给pre_char，并输出pre_char；

步骤三：设置变量cw，继续读取待解压缩数据中的下一个码流，赋值给cw，判断在字典中是否有cw表示的索引对应的词条，如果有cw表示的索引对应的词条，输出cw表示的索引对应的词条，即cw表示的索引对应的字符串数据，设置变量current_char，将cw表示的索引对应的字符串数据赋值给current_char，设置字符变量pc，将pre_char赋值给pc，设置字符变量cc，将current_char对应的词条的第一个字符赋给cc，将pc和cc依次排列组成的字符串添加到解压缩字典中；如果没有cw表示的索引对应的词条，将pre_char的值赋给pc，将current_char的第一个字符赋给cc，输出pc和cc依次排列组成的字符串数据，并添加pc和cc依次排列组成的字符串数据到字典中；

步骤四：判断待解压缩数据流中是否还有数据需要解压缩，如果还有数据需要解压缩，返回步骤三；如果没有数据需要解压缩，将步骤三的输出按输出顺序排列成新的字符串数据，识别新的字符串数据中的头部控制字；设置字符串head，将头部控制字赋值给head；

步骤五：设置字符串变量current_string，从去掉头部控制字的新的字符串数据中按照游长读取字符串赋值给current_string，然后再读取该字符串后的一个字符，即游长计数器的值，根据读取出的字符串和游长计数器的值还原出原始压缩数据；

步骤六：判断去掉头部控制字的新的字符串数据中是否还有待解压缩的数据，若有，则将待解压缩的数据代替去掉头部控制字的新的字符串数据，返回步骤五；若无，则将head与步骤五输出的数据依次排列得到原始数据，完成解压缩。

说明书

一种基于RLE和LZW的优化比特文件压缩与解压缩方法

技术领域

[0001] 本发明涉及一种基于RLE和LZW的优化比特文件压缩与解压缩方法，属于通信中比特文件压缩与解压缩技术领域。

背景技术

[0002] 随着星上应用复杂度的增加，对星上数据处理能力的要求也越来越高，采用的FPGA型号也随着应用复杂度的提升而不得不采用更高等级的器件。这些先进型号的FPGA由于功能的更为强大，所对应的比特文件也变得更大，配置一片V5130T的FPGA的比特文件较V4SX55增长了大约3倍左右，这就意味着应用一片V5FPGA需要过去3倍的存储资源来存储配置比特，这对星上有限的资源来说无疑是个问题，必须要采取一定的压缩方法来降低存储资源。而且必须满足以下要求：1)必须无损的还原比特文件，对比特流进行解压缩要求能够准确地恢复出原数据；2)压缩率要高，压缩解压缩时间要短。针对这个问题及以上两点要求，提出了一种基于RLE和LZW的优化比特文件压缩与解压缩方法，以实现高速高压缩率的比特文件压缩解压缩。

[0003] 数据压缩通常包括有损压缩和无损压缩两种。有损压缩是有失真的压缩，不可逆的，信息会受到损失。无损压缩是无失真的压缩，压缩过程中去除数据中的冗余度，解压后不丢失任何信息，与压缩前完全一致。无损压缩通常用于文本、程序、重要数据的压缩，它能保证完全地恢复原始数据。对比特流进行压缩要求能够准确地恢复出原数据，因此需要选用无损压缩技术对比特文件进行压缩和解压缩来解决配置比特数据的传输和存储问题。

[0004] 经典的无损压缩算法主要有：基于统计模式的算法，如香农编码、霍夫曼编码、算术编码等；基于字典模式的算法，如LZ系列算法；还有一些其它的算法，如游程编码、JPEG-LS算法、JPEG2000的DEM算法、BWT算法等。综合考虑设计复杂度和压缩效率，字典模式的算法较统计模式的算法更适合用于比特文件压缩。国内外目前针对比特文件压缩主要采用的压缩方法是字典式压缩或者采用游程编码技术压缩。Xilinx自己的压缩工具采用字典式的LZ77方法进行比特文件压缩。通过后面的实验数据可以看出，Xilinx压缩的比特文件压缩率并不高。

发明内容

[0005] 本发明解决的技术问题为：克服现有技术不足，提供一种基于RLE和LZW的优化比特文件压缩与解压缩方法，在快速压缩和高压缩率的要求下，本发明通过对比特文件数据结构进行分析，适应性的优化改进了RLE算法，并结合LZW方法进一步提升压缩率，设计了一种基于RLE和LZW的优化比特文件压缩/解压缩方法，该方法通过对比特文件数据结构的分析，创造性的根据比特文件特点优化了RLE算法；在应用优化RLE算法的基础上，为了进一步提升压缩率，创造性地将优化后的RLE算法并与LZW算法结合，应用于比特文件压缩解压缩。该方法节省了存储资源，提高了计算效率，压缩及解压缩的设计实现，验证了方法的正确性、有效性、高效性和可行性。

[0006] 本发明解决的技术方案为：一种基于RLE和LZW的优化比特文件压缩方法，包括步骤如下：

[0007] 步骤一：FPGA配置比特文件由多部分数据组成，包含头部控制字、数据和命令字，其中，数据和命令字格式都是以四字节为一个单位，抠除FPGA配置比特文件的头部控制字；

[0008] 初始化RLE中的游长计数器；将RLE的游程长度根据步骤一所述比特文件数据特点设置为4；

[0009] 初始化LZW的压缩字典，使字典包含所有可能的根，所述根为单一词条；

[0010] 设置前缀pre_char，令当前前缀pre_char为空；

[0011] 步骤二：设置字符串pre_string；将步骤一中抠除头部控制字的FPGA配置比特文件的第一个字符串赋给字符串pre_string；所述抠除头部控制字的FPGA配置比特文件为被压缩文件；

[0012] 步骤三：将被压缩文件进行压缩，步骤如下：

[0013] (1)判断被压缩文件中是否有字符串需要压缩，如果没有字符串需要压缩，则先输出字符串pre_string，再输出游长计数器的值，进入步骤四；

[0014] (2)如果有字符串需要压缩，设置当前字符串current_string，令当前字符串current_string等于字符流中的下一个字符串；

[0015] (3)判断pre_string与current_string是否一致：如果pre_string与current_string一致，游长计数器加1，判断游长计数器值是否计到255；如果游长计数器值计到255，先输出pre_string，再输出游长计数器值，令游长计数器值为1，

[0016] 读取待压缩文件的未压缩的字符串给pre_string，返回步骤三

[0017] 如果游长计数器值未计到255，返回步骤三；

[0018] 如果pre_string与current_string不一致，输出pre_string，输出游长计数器值，将此时current_string赋给pre_string，返回步骤三；

[0019] 步骤四：设定当前字符current_char，按照步骤三(1)输出顺序，将输出依次排列成新的字符流，读取该字符流中的第一个字符赋给current_char；

[0020] 步骤五：判断pre_char与current_char依次排列组成的词条是否在字典中：如果在字典中，将pre_char与current_char依次排列组成的词条赋给pre_char；如果未在字典中，则输出当前前缀pre_char的码字，添加pre_char与current_char依次排列组成的词条到字典中，将current_char的值赋给pre_char；

[0021] 步骤六：判断新的字符流中是否还有字符需要压缩，如果有字符需要压缩，将需要压缩的第一个字符赋给current_char，返回步骤五；如果没有字符需要压缩，输出当前前缀pre_char的码字，完成压缩。

[0022] LZW的压缩字典用于存储压缩过程中产生的词条。

[0023] 游长计数器，从1开始计数，即读取第一个字符串时计1，能够在遇到连续重复出现的字符串时每次加1，直到出现不同的字符串时，能够输出游长计数器的值，还原初值1；游长计数器的值为1-255，达到255时还原1。

[0024] 初始化LZW的压缩字典的索引值为1-4096。

[0025] 一种基于RLE和LZW的优化比特文件解压缩方法，包括步骤如下：

[0026] 步骤一：初始化解压缩字典，使字典包含所有可能的根，所述根为单一词条；

[0027] 步骤二：设置变量pw，读取待解压缩数据流中第一个码流，赋值给pw，以pw为索引查询解压缩字典，读取该索引对应的词条，设置字符串变量pre_char，将pw表示的索引对应的词条赋给pre_char，并输出pre_char；

[0028] 步骤三：设置变量cw，继续读取待解压缩数据中的下一个码流，赋值给cw，判断在字典中是否有cw表示的索引对应的词条，如果有cw表示的索引对应的词条，输出cw表示的索引对应的词条，即cw表示的索引对应的字符串数据，设置变量current_char，将cw表示的索引对应的字符串数据赋值给current_char，设置字符变量pc，将pre_char赋值给pc，设置字符变量cc，将current_char对应的词条的第一个字符赋给cc，将pc和cc依次排列组成的字符串添加到解压缩字典中；如果没有cw表示的索引对应的词条，将pre_char的值赋给pc，将current_char的第一个字符赋给cc，输出pc和cc依次排列组成的字符串数据，并添加pc和cc依次排列组成的字符串数据到字典中；

[0029] 步骤四：判断待解压缩数据流中是否还有数据需要解压缩，如果还有数据需要解压缩，返回步骤三；如果没有数据需要解压缩，将步骤三的输出按输出顺序排列成新的字符串数据，识别新的字符串数据中的头部控制字；设置字符串head，将头部控制字赋值给head；

[0030] 步骤五：设置字符串变量current_string，从去掉头部控制字的新的字符串数据中按照游长读取字符串赋值给current_string，然后再读取该字符串后的一个字符，即游长计数器的值，根据读取出的字符串和游长计数器的值还原出原始压缩数据；

[0031] 步骤六：判断去掉头部控制字的新的字符串数据中是否还有待解压缩的数据，若有，则将待解压缩的数据代替去掉头部控制字的新的字符串数据，返回步骤五；，若无，则将head与步骤五输出的数据依次排列得到原始数据，完成解压缩。

[0032] 本发明与现有技术相比的优点在于：

[0033] (1)在快速压缩和高压缩率的要求下，本发明通过对比特文件数据结构进行分析，适应性的优化改进了RLE算法，并结合LZW方法进一步提升压缩率，设计了一种基于RLE和LZW的优化比特文件压缩/解压缩方法。该方法通过对比特文件数据结构的分析，创造性的根据比特文件特点优化了RLE算法；在应用优化RLE算法的基础上，为了进一步提升压缩率，创造性地将优化后的RLE算法并与LZW算法结合，应用于比特文件压缩解压缩。该方法节省了存储资源，提高了计算效率，压缩及解压缩的设计实现，验证了方法的正确性、有效性、高效性和可行性。

[0034] (2)本发明通过对比特文件结构以及RLE和LZW算法分析，针对比特文件设计了一种基于RLE和LZW的优化比特文件压缩以及解压缩技术方法，创造性的根据比特文件特点优化了RLE算法，为了进一步提升压缩率，创造性地将优化后的RLE算法并与LZW算法结合，应用于比特文件压缩解压缩，在保证一定压缩率的基础上节省了压缩时间和大量的存储资源，通过相应解压缩程序设计验证了压缩方法的正确性、高效性和可行性。

附图说明

[0035] 图1为本发明基本数码结构；

[0036] 图2为本发明一种基于RLE和LZW的优化比特文件压缩算法流程图；

[0037] 图3为本发明一种基于RLE和LZW的优化比特文件解压缩算法流程图；

[0038] 图4为不同压缩算法压缩率比较示意图。

具体实施方式

[0039] 本发明的基本思路为：一种基于RLE和LZW的优化比特文件压缩与解压缩方法，通过对FPGA配置比特文件进行数据格式分析，抠出比特文件的头部控制字，从真实配置数据开始，采用游长为4的RLE编码进行初步压缩，再进行LZW压缩进一步提升压缩率。解压缩时为压缩的逆过程，先进行LZW解压缩还原出中间数据，再对不包含头部控制字的数据部分进行RLE解压缩，还原出原始的FPGA配置比特文件。该方法综合考虑了压缩/解压缩的时间和压缩率，与Xilinx自带的压缩工具比较，与单纯应用RLE算法，单纯应用LZW算法比较，实现了压缩率与压缩速度的双赢。解决了Xilinx先进型号FPGA配置比特文件过大的问题，节省了存储芯片的开销，为FPGA在轨重构技术提供了关键技术支撑。

[0040] 下面结合附图和具体实施例对本发明做进一步详细描述。

[0041] 游程编码(RLE)又称为行程编码，是一种相对简单的数据压缩技术。游程指的是由信源符号或信号样值构成的数据流中各个字符连续重复而形成字符串的长度，又称游程长度或游长。游程编码就是将这种字符序列映射成串的字符串的长度和串的位置的标志序列，当给定了行程串的字符、串的位置和长度，就能够恢复出原始数据流。数据流的基本数码结构如图1所示，其中标识码根据具体使用而定，也可以省略。

[0042] 根据游程编码的数据流基本结构可知，只有游程长度大于3时，游程编码才具有数据压缩的功能。游程编码的效率取决于信源符号的重复率，重复率越高，游长越长，其压缩效果越明显。游程压缩逻辑和硬件实现简单，且速度很快。在实际工程中有时将游程编码和其它编码方法一起混合使用，能获得更好的压缩效果。

[0043] 由游程编码的原理可以知道，只有当被压缩样本重复率比较高的时候游程编码的压缩效果才会较好。分析比特文件的架构，首先每个比特文件都有自己的头部信息，这部分信息样本的重复率非常低，相对于整个比特文件而言，头部信息的所占的比特位非常少，故在对比特文件进行压缩时，抠出头部信息位，仅对头部信息后面的数据进行压缩，这样一定程度上提升了压缩速度和压缩率。抠出头部信息后，剩余的比特文件仍是有一定规律的，那就是不管是命令字还是数据都是以4个字节为一个单位的，这样应用游程编码对比特文件压缩的游长选取为4字节是最合适的，选取小于4字节的话会增加更多的游长信息在压缩后的文件中，会降低压缩率；选取大于4字节的话，样本的重复率会降低，在压缩后的文件中会增加标识码信息，降低压缩率。在实现了优化RLE压缩算法后，通过实验也证实了分析结果。

[0044] 改进游程编码由于压缩过程不需要存储，没有计算，所以压缩速度很快，但是受限于比特文件复杂度和压缩算法本身，压缩率并不是特别高。故在此优化RLE算法的基础上进一步结合LZW算法对压缩后的数据进行进一步的处理来提升压缩率。

[0045] LZW算法由Terry Welch在1984年提出，它是LZ78的改进算法，与LZ78算法相比，去掉了标识的第二个字段。LZW算法是基于字典模式的压缩算法，不依赖于信源的概率分布，是一种面向通用数据、易于实现的无损数据压缩算法。LZW算法不依赖于任何数据格式，具有很大的应用范围，并且编码速度快，逻辑简单而且具有自适应的功能，特别有利于硬件实现同时具有很高的实时性。

[0046] LZW算法首先将字母表中的所有字符初始化到字典中，通常使用8位字符，因此在输入数据之前就已经占用了字典的前256项，即0～255。因为字典已经被初始化，所以输入的下一个字符总能在字典中找到。实际中字典编码就是对8位字符集的扩充，用来表示数据中出现的字符串，新增的字典编码可用9位、10位、11位、12位甚至更多位来表示。例如若每个字符串用9位表示，可以有512个不同的9位代码。这就是说，转换表有512个字符串，其中256个表项用来存放已定义的字符，剩下256个用来存放(前缀，字符串)。

[0047] LZW算法的编码原理如下：首先需要初始化字典，将前256项分给0～255，然后每读入一个字符pre_char，均必须先在字典中进行查找。如果字典中已经有该字符，则更新当前字符为pre_char，并且将当前字符pre_char作为前缀，继续读入下一字符current_char作为尾字符，组成一个字符串“pre_char，current_char”，并再次在字典中查找“pre_char，current_char”。如果字典中没有，则输出字符pre_char位置码，并将“pre_char，current_char”添加到字典中，然后将current_char作为前缀。重复以上步骤，直到所有编码完成。

[0048] LZW的解码算法是编码的逆过程，同样的表现为一种基于字典的自适应的算法，一边生成字典，一边解码输出。

[0049] 综上所述，本发明提出了一种基于RLE和LZW的优化比特文件压缩方法，包括步骤如下：

[0050] 步骤一：FPGA配置比特文件由多部分数据组成，主要包含头部控制字、数据和命令字，其中，数据和命令字格式都是以四字节为一个单位，抠除FPGA配置比特文件的头部控制字；

[0051] 初始化RLE中的游长计数器为1；将RLE的游程长度根据步骤一所述比特文件数据特点设置为4；

[0052] 初始化LZW的压缩字典为4096行*32列，使字典包含所有可能的根，所述根为单一词条，即初始化后的字典第0到255行的第一列数据为0-255；

[0053] 设置前缀pre_char，令当前前缀pre_char为空；

[0054] 步骤二：设置字符串pre_string；将步骤一中抠除头部控制字的FPGA配置比特文件的第一个字符串赋给字符串pre_string；所述抠除头部控制字的FPGA配置比特文件为被压缩文件；

[0055] 步骤三：

[0056] (1)判断被压缩文件中是否有字符串需要压缩，如果没有字符串需要压缩，则先输出字符串pre_string，再输出游长计数器的值，进入步骤四；

[0057] (2)如果有字符串需要压缩，设置当前字符串current_string，令当前字符串current_string等于字符流中的下一个字符串；

[0058] (3)判断pre_string与current_string是否一致：如果pre_string与current_string一致，游长计数器加1，判断游长计数器值是否计到255；如果游长计数器值计到255，先输出pre_string，再输出游长计数器值，令游长计数器值为1，

[0059] 读取待压缩文件的未压缩的字符串给pre_string，返回步骤三

[0060] 如果游长计数器值未计到255，返回步骤三；

[0061] 如果pre_string与current_string不一致，输出pre_string，输出游长计数器值，将此时current_string赋给pre_string，返回步骤三；

[0062] 步骤四：(1)设定当前字符current_char，

[0063] (2)按照步骤三(1)输出顺序，将输出依次排列成新的字符流，读取该字符流中的第一个字符赋给current_char；为了提高压缩速度，该步骤可以在步骤三有数据输出时同时启动进行，读取步骤三输出的第一个字符给current_char，然后进行后续步骤；

[0064] 步骤五：判断pre_char与current_char依次排列组成的词条是否在字典中：如果是在字典中，将pre_char与current_char依次排列组成的词条付给pre_char；如果未在字典中，则输出当前前缀pre_char的码字，添加pre_char与current_char依次排列组成的词条到字典中，将current_char的值赋给pre_char；

[0065] 步骤六：判断新的字符流中是否还有字符需要压缩，如果有字符需要压缩，将需要压缩的第一个字符付给current_char，返回步骤五；如果没有字符需要压缩，输出当前前缀pre_char的码字，完成压缩。

[0066] LZW的压缩字典用于存储压缩过程中产生的词条。

[0067] 游长计数器，从1开始计数，即读取第一个字符串时计1，能够在遇到连续重复出现的字符串时每次加1，直到出现不同的字符串时，能够输出游长计数器的值，还原为初值1；游长计数器的值为1-255。

[0068] 初始化LZW的压缩字典的索引值为1-4096。

[0069] 结合上述优化比特文件压缩算法及程序设计思路，一种基于RLE和LZW的优化比特文件压缩算法流程如图2所示。

[0070] 在完成了压缩后，相对应于压缩技术处理后的数据，解压缩是压缩的逆过程既可以实现还原出原始数据，可以需要采用LZW算法还原出优化RLE压缩的数据，再进行优化RLE解压缩还原出最初的原始数据。解压缩与压缩思路相逆。

[0071] 下面给出一种优选的具体解压缩方法流程如图3所示，本发明优选的一种基于RLE和LZW的优化比特文件解压缩方法包括步骤如下：

[0072] 步骤一：初始化解压缩字典为4096行*32列，使字典包含所有可能的根，所述根为单一词条，即初始化后的字典第0到255行的第一列数据为0-255；

[0073] 步骤二：设置变量pw，读取待解压缩数据流中第一个码流，赋值给pw，以pw为索引查询字典，读取该索引对应的词条，设置字符串变量pre_char，将pw表示的索引对应的词条赋给pre_char，并输出pre_char；如pw为10，查询索引为10的字典中字符串数据，赋值为pre_char；

[0074] 步骤三：设置变量cw，继续读取待解压缩数据中的下一个码流，赋值给cw，判断在字典中是否有cw表示的索引对应的词条，如果有cw表示的索引对应的词条，输出cw表示的索引对应的字符串数据(输出cw表示的索引对应的词条，即cw表示的索引对应的字符串数据)，设置变量current_char，将cw表示的索引对应的字符串数据赋值给current_char，设置字符变量pc，将pre_char赋值给pc，设置字符变量，将current_char对应的词条的第一个字符赋给cc，将pc和cc依次排列组成的字符串添加到解压缩字典中；如果没有cw表示的索引对应的词条，将pre_char的值赋给pc，将current_char的第一个字符赋给cc，输出pc和cc依次排列组成的字符串数据，并添加pc和cc依次排列组成的字符串数据到字典中；如待解压缩数据为“9 18 300…..4095”，则读取第一个pw值9，输出字典第9条表示的字符串“9 256 256….256”给pre_char，并输出“9”；继续读取cw值18，该值在初始化的字典中，输出字典第18条表示的字符串“18 256 256….256”给current_char，并输出“18”，添加“9 18 
256….256”到字典中，该词条索引为257；继续读取cw值300，该值不在初始化的字典中，输出“18 18”，添加“18 18 256….256”到字典中，依次类推，直到所有数据处理完成。

[0075] 步骤四：判断待解压缩数据流中是否还有数据需要解压缩，如果还有数据需要解压缩，返回步骤三；如果没有数据需要解压缩，将步骤三的输出按输出顺序排列成新的字符串数据，识别新的字符串数据中的头部控制字；设置字符串head，将头部控制字赋值给head(如新的字符串数据为“头部控制字AA AA AA AA 02 BB BB BB BB 01 CC CC CC CC 09……DD DD DD DD 03”，将头部控制字赋给head，对“AA AA AA AA 02 BB BB BB BB 01 CC CC CC CC 09……DD DD DD DD 03”进行后续解压缩)；

[0076] 步骤五：设置字符串变量current_string，从去掉头部控制字的新的字符串数据中按照游长读取字符串赋值给current_string，然后再读取该字符串后的一个字符，即游长计数器的值，根据读取出的字符串和游长计数器的值还原出原始压缩数据；如字符串“AA BB CC DD 02”，读取current_string为“AA BB CC DD”，游长为2，还原后的数据为“AA BB CC DD AA BB CC DD”；

[0077] 步骤六：判断去掉头部控制字的新的字符串数据中是否还有待解压缩的数据，若有，则将带压缩的数据代替去掉头部控制字的新的字符串数据，返回步骤五；若无，则将head与步骤五输出的数据依次排列得到原始数据，完成解压缩。如带解压缩数据还有“AA AA AA AA 02 BB BB BB BB 01 CC CC CC CC 09……DD DD DD DD 03”,先读取“AA AA AA AA”，根据“02”，还原数据为“AA AA AA AA AA AA AA AA”；再读取“BB BB BB BB”，根据“01”，还原数据为“BB BB BB BB”，依次读完所有数据，直到读取“DD DD DD DD”，根据“03”，还原数据为“DD DD DD DD DD DD DD DD DD DD DD DD”(与头部控制字拼接完成完整原始数据解压缩为“头部控制字AA AA AA AA AA AA AA AA BB BB BB BB……DD DD DD DD DD DD DD DD DD DD DD DD”)。

[0078] 6、变量current_char作为索引号，解压缩字典中相应的字符串数据。

[0079] 相对应于压缩技术处理后的数据，解压缩技术首先需要采用LZW算法还原出优化RLE压缩的数据，再进行优化RLE解压缩还原出最初的原始数据。算法设计思路与压缩算法类似，具体解压缩算法流程如图3所示。

[0080] 压缩和解压缩程序设计完成后，采用五种不同资源利用率的比特文件进行了压缩率测试和解压缩还原试验，还原后的数据与原始数据一致，验证了算法实现的正确性。压缩率大小如下表所示：

[0081] 表1压缩试验数据

[0082]

[0083] 图形化显示实验结果如图4所示，从实验结果可以看出：

[0084] 随着资源的增加，所有压缩方法的压缩率都在下降；对于资源使用非常少的数据(1％)，我们开发的三种方法压缩率都在95％以上，Xilinx的压缩率只有85％；

[0085] 对于资源使用非常多的数据(99％)，Xilinx的压缩方法压缩率只比优化RLE的压缩率略高，但还是远低于LZW以及优化RLE_LZW压缩方法；

[0086] 对于资源稍多的数据(20％、56％、81％)，LZW压缩方法的压缩率与其他三种方法比较是最高的(百分之七八十)，Xilinx的压缩率是最低的(只能达到百分之二三十)；

[0087] RLE_LZW优化压缩方法，对于资源使用率较高的比特压缩率略低于LZW，差别不是很大，但在压缩时间上较LZW方法提升了许多，这是由于待压缩数据先经过优化RLE算法压缩，再送到LZW压缩时数据量较未压缩数据已经减少了很多。优化RLE算法本身不耗时，而LZW算法本身由于数据需要与字典进行逐一比较，而字典本身又是动态更新的，所以非常耗时。RLE_LZW优化算法较单纯的LZW算法损失的压缩率是由于优化RLE算法处理后的压缩数据复杂度较原始数据增加，导致压缩率受到了一点影响。但是，综合考虑压缩时间与压缩率，一种基于RLE和LZW的优化比特文件压缩与解压缩技术是最优的。