基于FPGA的LZO实时无损压缩的硬件设计.doc

《基于FPGA的LZO实时无损压缩的硬件设计.doc》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、基于FPGA的LZO实时无损压缩的硬件设计　　本文通过对多种压缩算法作进一步研究对比后发现，LZO压缩算法是一种被称为实时无损压缩的算法，LZO压缩算法在保证实时压缩速率的优点的同时提供适中的压缩率。如图1（A）给出了Linux操作系统下常见开源压缩算法的压缩速率的测试结果，LZO压缩算法速率极快;如图1（B）给出了Gzip压缩算法和LZO压缩算法的压缩率测试结构，从图中可以看出，LZO压缩算法可以提供平均约50%的压缩率。　　　　　　1LZO压缩算法基本原理分析　　1.1基于FPGA的LZO实时无损压缩的硬件设计　　本文通过对多种压缩算法作进一步研

2、究对比后发现，LZO压缩算法是一种被称为实时无损压缩的算法，LZO压缩算法在保证实时压缩速率的优点的同时提供适中的压缩率。如图1（A）给出了Linux操作系统下常见开源压缩算法的压缩速率的测试结果，LZO压缩算法速率极快;如图1（B）给出了Gzip压缩算法和LZO压缩算法的压缩率测试结构，从图中可以看出，LZO压缩算法可以提供平均约50%的压缩率。　　　　　　1LZO压缩算法基本原理分析　　1.1LZO压缩算法压缩原理　　LZO压缩算法采用（重复长度L，指回距离D）代替当前已经在历史字符串中出现过的字符串，其中，重复长度是指，后出现的字符串与先出现的

3、字符串中连续相同部分的长度;指回距离是指，先后两个相同字符串之间相隔的距离（每个字节为一个单位）;如果没出现过（定义为新字符），则首先输出新字符的个数，再输出新字符。例如，待处理的字符串为“ABCDEFGHABCDEFJKLM”，压缩算法逐个处理字符，处理ABCDEFGH时没发现重复字符;处理到ABCDEF时发现这些字符在历史字符串中已经出现过，计算重复长度为6，指回距离（当前A离历史A的距离）为8，则用（6，8）代替ABCDEF;处理到JKLM时没发现重复字符，字符串到此处理完毕，则整个字符串被压缩成：（08）hABCDEFGH（6，8）（04）h

4、JKLM，其中h表示16进制。　　1.2LZO压缩算法编码　　LZO压缩后的数据需要经过特定的格式进行编码，如图2所示，LZO压缩算法这样做的目的有两方面：调整LZO压缩率，使得LZO适合压缩重复长度短，但指回距离较长的数据;使得解压缩过程更加简单，解压缩速度更快，且不需要额外的内存。　　　　　　2LZO压缩算法硬件设计与加速方案　　2.1LZO压缩算法硬件结构　　如图3（A）给出了一种LZO压缩算法的硬件结构，其中输入缓存模块：用于缓存DMA传输的待压缩数据，为高速缓存模块提供数据源用以进行压缩操作;高速缓存模块：临时缓存待压缩数据，为LZSS压缩

5、模块提供待压缩数据，初始化时提前写入一定量的数据;LZSS模块：对待压缩数据进行压缩处理;字典模块：存储压缩过程中产生的压缩信息，例如历史字符串的索引信息，这样便可为后续数据压缩提供历史字符串信息;LZO编码模块：对LZSS压缩后的数据按照LZO编码格式进行编码，并将编码数据组包成固定长度的数据包，方便总线通讯;输出缓存模块：缓存编码后的数据，为DMA读操作提供压缩后的数据源;Avalon总线接口：按照Avalon总线规范对LZO压缩算法模块进行封装，为后续集成SOPC提供准备。　　　　2.2LZO压缩算法硬件加速方案　　（1）分离双端口RAM　　为

6、了加速LZO压缩算法字符串的比对过程，本文提出如图3（B）所示的分离双端口RAM的结构，图中的多路选择器1用于将待压缩数据交替式写入双端口RAM1和双端口RAM2之一中，多路选择器2用于将读取的数据交替式输出。例如，现有字符ABCDEFGHIJ要存入双端口RAM中，具体如下：ABCD通过多路选择器1被写入RAM1中的data1处，EFGH通过多路选择器1被写入RAM2中的data2处，IJ通过多路选择1被写入data3，此时LZO压缩算法模块需要读取字符串BCDE，则在读取RAM1中data1处的BCD的同时读取RAM2中data2处的E，即给RAM

7、1读地址的同时可以给RAM2读地址，这样同一时刻可以读2处地址对应的内容。相比于一般性双端口RAM结构，本结构可以实现一次完成读取操作。做进一步扩展可得出如下结论：若RAM的宽度为W，则读取字符数在2W以内时，采用分离双端口RAM结构可以一次完成读取操作;则读取字符数在2~2W以内时，采用一般性双端口RAM结构可能要读两次。当然，不仅RAM的宽度可以增加，RAM的个数也可以增加，当RAM的宽度和RAM个数越大时，完成读操作只需一次的可能性就越大。　　（2）块标记　　LZO压缩算法在压缩每个数据块之前都要对字典模块进行初始化为0的操作，即对RAM进行写

8、0操作，然而写0操作会耗费若干个周期。若字典模块深度为16K，即RAM的深度为16K，当进行写0操作时至少花