无损高压缩率电路设计

朱 嘉，刘红侠

(西安电子科技大学 微电子学院，陕西 西安 710071)

随着世界进入数字时代，每分钟都有成百上千的视频、照片上传和下载，移动处理终端和服务器的数据带宽需求越来越高，导致多核片上系统设计的复杂度逐年升高，数据业务量以指数级增长。无损数据压缩技术在实时系统中对于存储空间的节省和系统运行的速度起到关键作用。无损压缩有很多算法，如游程编码，哈夫曼编码[1-2]，LZ77编码等[3-5]。基于不同应用要求，无损压缩实现的方法各有不同。

Deflate算法[1]是一种基于历史数据的字典查找，并且在编码过程按照熵原理是[6]不会丢失任何信息的压缩方式。该技术常以软件方式实现，方式配置灵活，但存在处理速度慢、资源消耗大等瓶颈，无法满足实时压缩处理需求。Deflate压缩算法的硬件实现，可以充分减少硬件数据通路数据量，增大数据实际传输带宽，以较小的芯片面积和压缩率损失为代价获得较高的压缩运算速度。因此该技术被国内外研究机构关注，并且无损压缩已经被定义在新的通信标准协议中[7]。笔者以提高压缩速率和压缩率为主要目标，兼顾芯片面积和功耗，使用4列双哈希并行匹配及变长压缩编码高速拼接实现压缩逻辑。最终将其应用于基带数据追踪模块，实现追踪数据实时压缩。

1 Deflate无损压缩技术

Deflate压缩算法是结合LZ77和哈夫曼编码算法的两级无损压缩算法，图1描述了这种算法的一般实现，数据首先经过第一级LZ77压缩，然后对其压缩结果再进行第二级哈夫曼编码压缩。

1.1 LZ77算法优化实现

LZ77[8]是一种通过一个副本反复替代原文本中重复出现的数据进行压缩,是一种基于字典查询的无损压缩。该算法将当前数据流与历史数据相匹配，找到一个匹配数据，记录该匹配数据的所在位置和匹配长度进行压缩编码。如果未匹配成功，则将原数据输出。重复这个过程，将所有输入进行编码。LZ77压缩最终输出结果由三元组：字符、距离、长度构成。图1是压缩电路结构图，虚线框内为LZ77压缩逻辑实现。

图1 压缩模块结构图

为了加速匹配重复字符，如图1所示，引入哈希逻辑实现快速索引。输入字符经哈希运算得出哈希地址，利用该哈希地址得到查询数据位置指针。哈希函数构造、链表维护及搜索匹配均影响着LZ77算法的效率，哈希表可利用较少位宽数据表征较多位宽数据，是压缩关键技术。因此，哈希逻辑在压缩模块实现得到关注。东南大学李冰等人提出了双哈希链表[9]，通过使用2种不同的哈希函数计算字符串前3字节的哈希值，降低伪匹配，提高匹配成功率。而笔者提出了4列双哈希并行匹配结构构建哈希链表如表1所示，输入数据经过哈希运算生成表1中第一列哈希地址，利用输入数据高位字节和另一哈希函数生成表1中哈希值[i]并记录对应指针[i]。因为哈希值存在多对一的关系，当计算哈希地址冲突时，根据哈希值[i]进行指针优先级选择，进行LZ77压缩算法距离计算。

4列双哈希计算电路如图2所示，图中Hi即哈希值[i]，Pi即指针[i]，i=1,2,3,4。设计哈希逻辑时，同时也要考虑整个压缩模块的时序，哈希函数处理的字节数对应的最小时间应为哈希处理数据传至历史数据比较逻辑的延迟。通过比较哈希表中哈希值可以在4组同样哈希地址的数据中选出最长的匹配数据。利用4列并行双哈希判断，可在匹配滑窗内增加匹配长度，双哈希计算也可降低伪匹配率；同时得益于硬件电路的4路并行比较，极大提升了压缩速度。图1中哈希表深度和历史数据存储大小影响着压缩电路的压缩率。在压缩电路原型验证阶段，分别测试了哈希表深度和历史数据存储大小对压缩率的影响。

表1 压缩索引哈希表

图2 4列双哈希计算电路

1.2 哈夫曼编码高速移位拼接

哈夫曼编码是一种基于频率统计的编码方式，哈夫曼编码分为动态哈夫曼编码和静态哈夫曼编码。因为资源限制，文中仍采用了带有前缀码的静态哈夫曼编码。

LZ77压缩结果由字符、距离、长度这三元组构成。如果按固定字节存储距离、长度，就会浪费存储空间。按照统计结果，距离越小的，出现的次数越多；而距离越大的，出现的次数越少。因此距离较小的值就应该用较少的数据位表示，距离较大则使用较多数据位表示。因此实时处理的数据长度会因当前压缩而长度不同。文中提出的移位拼接根据输出数据位宽确定输出寄存器的大小。式(1)即输出前一级寄存器大小的一般公式描述：

Reg_Length=Max_compress_data_length+Output_length-Min_compress_data_length

(1)

式(1)表示当输出数据在当前时钟周期不足端口输出位宽，则在下一个时钟周期需要存储的最大值为当前输出位宽减去压缩数据最小值，加上下一个时钟周期压缩数据长度最大值。例如文中所计算距离哈夫曼编码的硬件输出端口为18位，最短压缩编码输出位宽为9,而压缩数据最长为23位，因此根据式(1)输出缓存寄存器位宽为Reg_length=18-9+23=32。

图3所示为高速移位拼接电路实现，因为压缩数据位宽随编码长度变化而变化，当拼接数据位宽超过输出数据位宽时，需要两个时钟周期处理，所以图3中多路选择器选择信号是当前选择信号和延迟一拍选择信号选择输出数据。整个移位拼接电路实现分为3部分：(1)第一个时钟周期，任意位宽数据输入，不需要移位。(2)中间压缩数据要使用图3所示移位拼接电路，将数据移至相应的位置与未输出数据进行相或拼接存储存入寄存器，输出。(3)最后一个压缩数据不能达到输出位宽，则以0填充输出。对于LZ77输出中长度同样采用该电路实现拼接输出。最后将整个数据按ZIP包格式输出。

图3 高速移位拼接电路

2 压缩电路测试结果

压缩电路分别由前硅功能验证、FPGA原型[10-11]验证和后硅性能验证进行了完备验证测试。

2.1 标准测试向量

目前被广泛采用的标准压缩测试向量分别是Calgary Corpus, Canterbury Corpus和Silesia Corpus[12-14]。该标准测试源由英文文本，程序源代码，图像及二进制文件组成，能够对压缩实现进行有效评测。文中分别从三组标准测试源选取了与追踪数据属性接近的测试数据进行测试，图4，图5横坐标即标准测试源样本名称。

图4 不同匹配长度下压缩电路压缩性能测试

2.2 测试结果

设计中，固定哈希表(1KB)大小及历史存储器深度(2KB)，针对不同最大匹配长度，利用标准数据源进行测试评估。测试结果如图4(a)，增大最大匹配长度，硬件额外开销增加，压缩率提升并不明显，平均提升不到10%。图4(b)是使用不同最大匹配长度，硬件的压缩速度。随着匹配长度的增加，历史存储器访问次数增加，数据匹配所需时间增长，使得压缩速率有所下降，最大压缩速率衰减超过32%。相较于文献[9]硬件设计，文中压缩实现压缩率有所提升，平均压缩速度是其6倍。

图5(a)是固定匹配长度时(256)和历史数据存储(2KB)大小，哈希表深度分别为128和256，不同测试源对应的压缩。测试结果表明，哈希表深度的增加，提高3.84%平均压缩率。图5(b)是固定匹配长度(256)和哈希表深度(128)，历史数据存储大小分别是1KB和2KB，不同测试源对应的压缩率，历史存储器增大1倍，平均压缩率提高1.34%。在同等条件下，增加哈希表深度比增加历史存储深度能更加有效地提升压缩率。

图5 不同存储尺寸下压缩电路压缩率测试

文中设计硬件实现如下，64位输入数据端口，128位输出数据端口，最大匹配长度256，哈希表深度256，历史数据存储1 KB，工作时钟频率200MHz,采用TSMC 28 nm工艺，面积为0.022 mm2，占芯片总面积不到0.5%。与无损压缩软件实现相比，文中所提硬件压缩模块压缩速度有极大提升。以Calgary Corpus为测试源进行压缩率及压缩速率测试，与文献中软硬件测试结果进行比较，结果如表2所示，其中硬件1是文献[9]硬件设计。硬件2是文中硬件设计。硬件2压缩电路实现其平均压缩速度达1 031 Mbps，是文献[9]中PC软件平台压缩速率的50倍，笔记本平台压缩速率的57倍，硬件的6倍。与文献[4]中Silesia测试源测试结果相比，文中设计硬件平均压缩速率是其9倍。

表2 测试源压缩结果比较

因为当前软件算法中使用了动态哈夫曼编码，所以表2中压缩算法软件实现的压缩率很高，动态统计地哈夫曼编码可以较大地提升压缩效率。对于硬件实现，动态哈夫曼编码需要消耗大量存储空间，并且有效统计概率计算也会降低压缩速度。故当前deflate算法硬件实现在满足压缩率指标下，实现了实时压缩，能够满足各类实时系统要求。

3 结束语

笔者基于专用硬件平台，实现了deflate压缩算法,使用了4列双哈希并行匹配，采用静态哈夫曼编码方案，通过硬件流水设计提高了匹配速度，提升了压缩速率。测试结果表明：

(1) 4列双哈希并行匹配，有效提高了匹配效率和匹配长度，提高了压缩率。

(2) 使用高速移位拼接设计，提出了变长数据处理的一般方法，提高了压缩数据拼接输出效率。

(3) 研究影响压缩率及压缩速率的参数：匹配长度，哈希表深度及历史数据存储大小，针对性能及面积要求，实现压缩逻辑。

(4) 文中所实现压缩电路，压缩平均速率达1 031 Mbit/s，可满足实时硬件系统压缩要求，该模块已应用于基带芯片数据追踪模块。