一种基于阵列配置加速比模型的无损压缩算法

徐金甫; 刘露; 李伟; 王周闯; 杨宇航

doi:10.11999/JEIT170900

一种基于阵列配置加速比模型的无损压缩算法

doi: 10.11999/JEIT170900

1.
(解放军信息工程大学郑州 450001) ②(复旦大学专用集成电路与系统国家重点实验室上海 201203)

基金项目:

国家自然科学基金(61404175)

计量
- 文章访问数: 1238
- HTML全文浏览量: 124
- PDF下载量: 121
- 被引次数: 0
出版历程
- 收稿日期: 2017-09-22
- 修回日期: 2018-04-13
- 刊出日期: 2018-06-19

A New Lossless Compression Algorithm Based on Array Configuration Speedup Model

1.
(The PLA Information Engineering University, Zhengzhou 450001, China)

Funds:

The National Natural Science Foundation of China (61404175)

摘要

摘要: 针对现有压缩算法通过增加复杂度来降低压缩率，获得信息高效传输的问题。该文提出阵列配置加速比模型，证明低压缩率不一定能提高传输效率，并找到影响信息传输效率的因子，即解压模块吞吐率和数据块压缩率。将影响因子与配置信息特征结合，设计了一种新的无损压缩算法，并硬件实现了解压模块，吞吐率可达到16.1 Gbps。采用AES, A5-1和SM4对无损压缩算法进行测试，然后与主流无损压缩算法LZW, Huffman, LPAQ1和Arithmetic对比。结果表明，整体压缩率相当，但该文压缩算法产生的数据块压缩率经过优化，不仅能满足加速需求，且具有高吞吐率的解压性能；该文无损压缩算法获得的配置加速比，比硬件吞吐率理想情况下的LPAQl, Arithmetic, Huffman, LZW算法分别高8%, 9%, 10%, 22%左右。
- 阵列 /
- 配置加速比 /
- 无损压缩 /
- 吞吐率 /
- 压缩率
Abstract: In order to obtain efficient information transmission, the existing compression algorithms reduce the compression ratio by increasing complexity. In view of this problem, an array configuration speedup model is proposed in this paper. It is proved that low compression ratio may not improve the transmission efficiency and the factors, decompression module throughput and data block compression rate which affect the efficiency of information transmission, are found. Combined the influencing factors with the configuration information, a new lossless compression method is designed and the decompression hardware circuit is implemented, whose throughput can reach 16.1 Gbps. The lossless compression algorithm is tested using AES, A5-1 and SM4. Compared with the mainstream lossless compression algorithms LZW, Huffman, LPAQ1 and Arithmetic, the results show that the overall compression ratio is equivalent. However, the compression ratio of data block generated by the compression algorithm is optimized, which can not only meet the demand of acceleration, but also possesses high throughput decompression performance. The configuration speedup ratio obtained by lossless compression algorithm is about 8%, 9%, 10% and 22% higher than LPAQl, Arithmetic, Huffman, and LZW with ideal hardware throughput.
- Array /
- Configuration speedup /
- Lossless compression /
- Throughput /
- Compression ratio

HTML全文

参考文献(33)

张海斌, 朱苏磊, 徐明亮. 基于可编程逻辑阵列的索贝尔边缘检测算法的两种实现方案[J]. 上海师范大学学报(自然科学版), 2017, 46(2): 247-253. doi: 10.3969/J.ISSN.1000-5137. 2017.02.013.

ZHANG Haibin, ZHU Sulei, and XU Mingliang. Two kinds of implementations of sobel edge detection algorithm based on field programmable gate array[J]. Journal of Shanghai Normal University (Natural Science Edition), 2017, 46(2): 247-253. doi: 10.3969/J.ISSN.1000-5137.2017.02.013.

冯晓, 李伟, 戴紫彬, 等. 面向分组密码的可重构异构多核并行处理架构[J]. 电子学报, 2017, 45(6): 1311-1320. doi: 10.3969/j.issn.0372-2112.2017.06.005.

FENG Xiao, LI Wei, DAI Zibin, et al. Reconfigurable asymmetrical multi-core architecture for block cipher[J]. Acta Electronica Sinica, 2017, 45(6): 1311-1320. doi: 10.3969/ j.issn.0372-2112.2017.06.005.

肖艺, 鲁华祥, 陈刚, 等. 基于仿生学的多层自适应容错重构阵列研究[J]. 仪器仪表学报, 2016, 37(2): 437-445. doi: 10.3969/j.issn.0254-3087.2016.02.026.

XIAO Yi, LU Huaxiang, CHEN Gang, et al. Bio-inspired method to develop the multi-layer and self-adaptive reconfigurable array[J]. Journal of Instrumentation, 2016, 37(2): 437-445. doi: 10.3969/j.issn.0254-3087.2016.02.026.

DHAOUI F, MCCOLLUM J, HAWLEY F, et al. Non-volatile programmable memory cell and array for programmable logic array[P]. US, US7838944, 2010.

陈锐, 杨海钢, 王飞, 等. 基于自路由互连网络的粗粒度可重构阵列结构[J]. 电子与信息学报, 2014, 36(9): 2251-2257. doi: 10.3724/SP.J.1146.2013.01646.

CHEN Rui, YANG Haigang, WANG Fei, et al. Coarse- grained reconfigurable array based on self-routing interconnection network[J]. Journal of Electronics Information Technology, 2014, 36(9): 2251-2257. doi: 10.3724 /SP.J.1146.2013.01646.

许霞, 马光思, 鱼涛. LZW无损压缩算法的研究与改进[J]. 计算机技术与发展, 2009, 19(4): 125-127. doi: 10.3969/j.issn. 1673-629X.2009.04.036.

XU Xia, MA Guangsi, and YU Tao. Research and improvement on LZW lossless compression algorithm[J]. Computer Technology and Development, 2009, 19(4): 125-127. doi: 10.3969/j.issn.1673-629X.2009.04.036.

鄢海舟, 胥布工, 石东江, 等. 无损压缩算法LZW前缀编码优化及应用[J]. 计算机工程, 2017, 43(3): 299-303. doi: 10.3969/j.issn.1000-3428.2017.03.050.

YAN Haizhou, XU Bugong, SHI Dongjiang, et al. Prefix encoding optimization and application of lossless compression algorithm LZW[J]. Computer Engineering, 2017, 43(3): 299-303. doi: 10.3969/j.issn.1000-3428.2017.03.050.

徐勇, 李珂, 冯国平, 等. 一种FPGA在轨重构配置数据压缩算法[J]. 航天器工程, 2015, 24(6): 75-78. doi: 10.3969/j.issn. 1673-8748.2015.06.013.

XU Yong, LI Ke, FENG Guoping, et al. Configuration data compression algorithm for FPGA on-orbit reconfiguration[J]. Spacecraft Engineering, 2015, 24(6): 75-78. doi: 10.3969/j.issn. 1673-8748.2015.06.013.

蔡明, 乔文孝, 鞠晓东, 等. 一种新的数据无损压缩编码方法[J]. 电子与信息学报, 2014, 36(4): 1008-1012. doi: 10.3724/ SP.J.1146.2013.00863.

CAI Ming, QIAO Wenxiao, JU Xiaodong, et al. A new coding method for lossless data compression[J]. Journal of Electronics Information Technology, 2014, 36(4): 1008-1012. doi: 10.3724/SP.J.1146.2013.00863.

杨国为, 涂序彦, 庞杰. 基于虚拟信源的无损数据压缩方法研究[J]. 电子学报, 2003, 31(5): 728-731. doi: 10.3321/j.issn: 0372-2112.2003.05.023.

YANG Guowei, TU Xuyan, and PANG Jie. The research of lossless data compression based on a virtual information source[J]. Acta Electronica Sinica, 2003, 31(5): 728-731. doi: 10.3321/j.issn:0372-2112.2003.05.023.

WANG Zhisheng, LIN Jun, and WANG Zhongfeng. An efficient hardware architecture for lossless data compression in data center[C]. IEEE International Workshop on Signal Processing Systems. Orlando, USA, 2016: 159-164.

MAHONEY M. Adaptive weighing of context models for lossless data compression[J]. Florida Institute of Technology, 2005, 16: 1-6.

SARKAR S J, SARKAR N K, DUTTA T, et al. Arithmatic coding based approach for power system parameter data compression[J]. Indonesian Journal of Electrical Engineering and Computer Science, 2016, 2(2): 268-274.

HASHEMPOUR H and LOMBARDI F. Application of arithmetic coding to compression of VLSI test data[J]. IEEE Transactions on Computers, 2005, 54(9): 1166-1177.

高放, 孙长建, 邵庆龙, 等. 基于K-均值聚类和传统递归最小二乘法的高光谱图像无损压缩[J]. 电子与信息学报, 2016, 38(11): 2709-2714. doi: 10.11999/JEIT151439.

GAO Fang, SUN Changjian, SHAO Qinglong, et al. Lossless compression of hyperspectral images based on k-mean clustering and conventional recursive least-squares[J]. Journal of Electronics Information Technology, 2016, 38(11): 2709-2714. doi: 10.11999/JEIT151439.

杨鹏. 可重构片上系统配置数据压缩算法研究[D]. [硕士论文], 湖南大学, 2010: 20-29.

YANG Peng. Research on configuration data compression algorithm for reconfigurable system-on-chip[D]. [Master dissertation], Hunan University, 2010: 20-29.

古海云, 李丽, 许居衍, 等. 一种Virtex系列FPGA配置数据无损压缩算法[J]. 计算机研究与发展, 2006, 43(5): 940-945.

GU Haiyun, LI Li, XU Juyan, et al. Lossless configuration bitstream compression for Virtex FPGA[J]. Computer Research and Development, 2006, 43(5): 940-945.

刘仕东. 一种通用 FPGA 配置数据流压缩与解压缩系统的研究[D]. [硕士论文], 哈尔滨工业大学, 2011: 49-50.

LIU Shidong. Research for compression and decompression system of a generic FPGA configuration data stream[D]. [Master dissertation], Harbin Institute of Technology, 2011: 49-50.

王防修, 刘春红. 一种哈夫曼编码的改进算法[J]. 武汉轻工大学学报, 2016, 35(1): 88-91.

WANG Fangxiu and LIU Chunhong. An improved algorithm of huffman encoding[J]. Journal of Wuhan Polytechnic University, 2016, 35(1): 88-91.

施引文献

资源附件(0)

访问统计