基于FPGA的LZ4无损压缩算法优化设计

摘要

随着云计算和大数据产业的兴起，计算机系统对数据存储和传输速率要求越来越高，现有的无损压缩软件逐渐变得难以满足实时数据访问的速率需求。新一代LZ4算法得益于百兆字节每秒(Million Bits per second，MBps)级别的压缩速率，在高速压缩场合得到广泛的应用。专用硬件压缩电路能够充分利用硬件的并发性和实时性，提供较高的压缩率和压缩速率性能，并且，压缩过程不需要占用中央处理器(Central Processing Unit，CPU)的计算资源，对压缩率和压缩速率性能之间的折中只取决于电路结构。
　　本文提出了针对LZ4压缩率缺陷的优化方案。使用现场可编程门阵列(Field Programmable Gate Array，FPGA)设计并实现了字典缓冲器、并行匹配电路、字符串分割电路、并行编码器、校验电路和流水线控制器，共同组成LZ4压缩电路。为了进一步优化压缩率，提出了以半静态哈夫曼(Huffman)编码为基础的二级压缩方法，并使用FPGA设计了统计、排序、建树、码长优化、码表生成以及编码电路。此外，将LZ4电路和半静态Huffman编码电路进行级联，解决了LZ4压缩电路的压缩率与兼容性之间的矛盾。
　　本文所述的压缩电路在Xilinx KC705开发平台上进行测试。设定电路工作频率125MHz，使用卡尔加里语料库（Calgary Corpus）和坎特伯雷语料库(Canterbury Corpus)进行性能测试。结果表明，在兼容模式下，平均压缩率(52.76％和49.95％)和压缩速率（213.09MBps和217.93MBps）基本达到LZ4压缩软件的水平;在优化模式下，设置16千字节(Kilo Bytes，KB)的统计长度能够兼顾压缩率和压缩速率性能，平均压缩速率分别为18572MBps和17266MBps，平均压缩率(44.89％和42.60％)性能相对LZ4软件提升14％以上。在压缩速率损失较少的前提下，有效的提升了压缩率性能，体现LZ4电路可以灵活的在压缩率与压缩速率之间进行折中的优势。

目录

声明

摘要

第一章 绪论

1．1 课题背景与意义

1．2 国内外研究现状

1．3 研究内容与设计指标

1．3．2 设计指标

第二章 LZ4压缩和Huffman编码算法分析

2．1．1 LZ4压缩的关键步骤

2．1．2 LZ4压缩的输出格式

2．1．3 校验算法

2．2 Huffman编码算法分析

2．2．2 Huffman编码的分类

2．2．3 动态Huffman编码流程

2．2．4 动态Huffman编码的缺陷和优化方法

2．3 本章小结

第三章 LZ4算法的优化及压缩电路设计

3．1 LZ4无损压缩算法优化

3．2 LZ4压缩电路设计

3．2．1 总体架构

3．2．2 字典缓冲器

3．2．3 分割电路

3．2．4 匹配电路

3．2．5 编码电路

3．2．6 校验电路

3．2．7 流水线控制器

3．3 FPGA逻辑设计

3．4 本章小结

第四章 半静态Huffman编码电路设计

4．1 半静态Huffman编码方法

4．2 半静态Huffman编码电路设计

4．2．2 统计电路

4．2．3 排序电路

4．2．4 建树电路

4．2．5 码长优化电路

4．2．6 码表生成电路

4．2．7 编码电路

4．3 压缩电路级联

4．4 FPGA逻辑设计与仿真

4．5 本章小结

第五章 实验及结果分析

5．1 实验平台的搭建

5．1．1 硬件平台

5．1．2 软件平台

5．2 标准压缩测试文件

5．2．2 Canterbury语料库

5．3 压缩性能指标介绍

5．4 无损压缩电路功能

5．5 无损压缩电路性能

5．5．2 兼容模式压缩率

5．5．3 兼容模式压缩速率

5．5．4 优化模式压缩率

5．5．5 优化模式压缩速率

5．5．6 性能与设计指标对比

5．6 本章小结

第六章 总结与展望

6．1 总结

6．2 展望

参考文献

致谢

攻读硕士学位期间发表的论文和专利