|
|
|
| A New Lossless Compression Algorithm Based on Array Configuration Speedup Model |
| XU Jinfu① LIU Lu① LI Wei①② WANG Zhouchuang① YANG Yuhang① |
①(The PLA Information Engineering University, Zhengzhou 450001, China)
②(State Key Laboratory of Fudan University Specific Integrated Circuit and System, Shanghai 201203, China) |
|
|
|
|
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.
|
|
Received: 22 September 2017
Published: 24 April 2018
|
|
|
| Fund:The National Natural Science Foundation of China (61404175) |
|
Corresponding Authors:
LIU Lu
E-mail: liulu13213238773@163.com
|
|
|
|
| [1] |
张海斌, 朱苏磊, 徐明亮. 基于可编程逻辑阵列的索贝尔边缘检测算法的两种实现方案[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.
|
| [2] |
冯晓, 李伟, 戴紫彬, 等. 面向分组密码的可重构异构多核并行处理架构[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.
|
| [3] |
肖艺, 鲁华祥, 陈刚, 等. 基于仿生学的多层自适应容错重构阵列研究[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.
|
| [4] |
DHAOUI F, MCCOLLUM J, HAWLEY F, et al. Non-volatile programmable memory cell and array for programmable logic array[P]. US, US7838944, 2010.
|
| [5] |
陈锐, 杨海钢, 王飞, 等. 基于自路由互连网络的粗粒度可重构阵列结构[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.
|
| [6] |
许霞, 马光思, 鱼涛. 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.
|
| [7] |
鄢海舟, 胥布工, 石东江, 等. 无损压缩算法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.
|
| [8] |
徐勇, 李珂, 冯国平, 等. 一种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.
|
| [9] |
蔡明, 乔文孝, 鞠晓东, 等. 一种新的数据无损压缩编码方法[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.
|
| [10] |
杨国为, 涂序彦, 庞杰. 基于虚拟信源的无损数据压缩方法研究[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.
|
| [11] |
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.
|
| [12] |
MAHONEY M. Adaptive weighing of context models for lossless data compression[J]. Florida Institute of Technology, 2005, 16: 1-6.
|
| [13] |
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.
|
| [14] |
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.
|
| [15] |
高放, 孙长建, 邵庆龙, 等. 基于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.
|
| [16] |
杨鹏. 可重构片上系统配置数据压缩算法研究[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.
|
| [17] |
古海云, 李丽, 许居衍, 等. 一种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.
|
| [18] |
刘仕东. 一种通用 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.
|
| [19] |
王防修, 刘春红. 一种哈夫曼编码的改进算法[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.
|
|
|
|
