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.
徐金甫,刘露,李伟,王周闯,杨宇航. 一种基于阵列配置加速比模型的无损压缩算法[J]. 电子与信息学报, 2018, 40(6): 1492-1498.
XU Jinfu, LIU Lu, LI Wei, WANG Zhouchuang, YANG Yuhang. A New Lossless Compression Algorithm Based on Array Configuration Speedup Model. JEIT, 2018, 40(6): 1492-1498.
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.
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.
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.
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.
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.
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.
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.
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.
YANG Peng. Research on configuration data compression algorithm for reconfigurable system-on-chip[D]. [Master dissertation], Hunan University, 2010: 20-29.
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.
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.