一種基于陣列配置加速比模型的無損壓縮算法

徐金甫; 劉露; 李偉; 王周闖; 楊宇航

doi:10.11999/JEIT170900

一種基于陣列配置加速比模型的無損壓縮算法

doi: 10.11999/JEIT170900

1.
(解放軍信息工程大學(xué) 鄭州 450001) ②(復(fù)旦大學(xué)專用集成電路與系統(tǒng)國家重點(diǎn)實(shí)驗(yàn)室上海 201203)

基金項(xiàng)目:

國家自然科學(xué)基金(61404175)

計(jì)量
- 文章訪問數(shù): 1265
- HTML全文瀏覽量: 134
- PDF下載量: 121
- 被引次數(shù): 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)

摘要

摘要: 針對(duì)現(xiàn)有壓縮算法通過增加復(fù)雜度來降低壓縮率，獲得信息高效傳輸?shù)膯栴}。該文提出陣列配置加速比模型，證明低壓縮率不一定能提高傳輸效率，并找到影響信息傳輸效率的因子，即解壓模塊吞吐率和數(shù)據(jù)塊壓縮率。將影響因子與配置信息特征結(jié)合，設(shè)計(jì)了一種新的無損壓縮算法，并硬件實(shí)現(xiàn)了解壓模塊，吞吐率可達(dá)到16.1 Gbps。采用AES, A5-1和SM4對(duì)無損壓縮算法進(jìn)行測(cè)試，然后與主流無損壓縮算法LZW, Huffman, LPAQ1和Arithmetic對(duì)比。結(jié)果表明，整體壓縮率相當(dāng)，但該文壓縮算法產(chǎn)生的數(shù)據(jù)塊壓縮率經(jīng)過優(yōu)化，不僅能滿足加速需求，且具有高吞吐率的解壓性能；該文無損壓縮算法獲得的配置加速比，比硬件吞吐率理想情況下的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全文

參考文獻(xiàn)(33)

張海斌, 朱蘇磊, 徐明亮. 基于可編程邏輯陣列的索貝爾邊緣檢測(cè)算法的兩種實(shí)現(xiàn)方案[J]. 上海師范大學(xué)學(xué)報(bào)(自然科學(xué)版), 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.

馮曉, 李偉, 戴紫彬, 等. 面向分組密碼的可重構(gòu)異構(gòu)多核并行處理架構(gòu)[J]. 電子學(xué)報(bào), 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.

肖藝, 魯華祥, 陳剛, 等. 基于仿生學(xué)的多層自適應(yīng)容錯(cuò)重構(gòu)陣列研究[J]. 儀器儀表學(xué)報(bào), 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.

陳銳, 楊海鋼, 王飛, 等. 基于自路由互連網(wǎng)絡(luò)的粗粒度可重構(gòu)陣列結(jié)構(gòu)[J]. 電子與信息學(xué)報(bào), 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ìn)[J]. 計(jì)算機(jī)技術(shù)與發(fā)展, 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前綴編碼優(yōu)化及應(yīng)用[J]. 計(jì)算機(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在軌重構(gòu)配置數(shù)據(jù)壓縮算法[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.

蔡明, 喬文孝, 鞠曉東, 等. 一種新的數(shù)據(jù)無損壓縮編碼方法[J]. 電子與信息學(xué)報(bào), 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.

楊國為, 涂序彥, 龐杰. 基于虛擬信源的無損數(shù)據(jù)壓縮方法研究[J]. 電子學(xué)報(bào), 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-均值聚類和傳統(tǒng)遞歸最小二乘法的高光譜圖像無損壓縮[J]. 電子與信息學(xué)報(bào), 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.

楊鵬. 可重構(gòu)片上系統(tǒng)配置數(shù)據(jù)壓縮算法研究[D]. [碩士論文], 湖南大學(xué), 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配置數(shù)據(jù)無損壓縮算法[J]. 計(jì)算機(jī)研究與發(fā)展, 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 配置數(shù)據(jù)流壓縮與解壓縮系統(tǒng)的研究[D]. [碩士論文], 哈爾濱工業(yè)大學(xué), 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ìn)算法[J]. 武漢輕工大學(xué)學(xué)報(bào), 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.

相關(guān)文章

施引文獻(xiàn)

資源附件(0)

訪問統(tǒng)計(jì)