Lempel-Ziv-Welch壓縮數(shù)據(jù)的誤碼糾正

王剛; 靳彥青; 彭華; 張光偉

doi:10.11999/JEIT190520

Lempel-Ziv-Welch壓縮數(shù)據(jù)的誤碼糾正

doi: 10.11999/JEIT190520 cstr: 32379.14.JEIT190520

王剛¹,
靳彥青²,
彭華^1, ,,
張光偉¹

1.
中國(guó)人民解放軍戰(zhàn)略支援部隊(duì)信息工程大學(xué) 鄭州 450000
2.
國(guó)家數(shù)字交換系統(tǒng)工程技術(shù)研究中心鄭州 450002

基金項(xiàng)目: 國(guó)家自然科學(xué)基金(61501516, 61572518)

詳細(xì)信息

作者簡(jiǎn)介:
王剛：男，1981年生，副教授，研究方向?yàn)樾盘?hào)分析、信息處理、模式識(shí)別

靳彥青：女，1983年生，工程師，研究方向?yàn)橐苿?dòng)通信

彭華：男，1973年生，教授，研究方向?yàn)橥ㄐ判盘?hào)處理、軟件無線電

張光偉：男，1984年生，講師，研究方向?yàn)樾畔踩?/p>

通訊作者:
彭華　phzttyw@126.com

中圖分類號(hào): TP911.21
計(jì)量
- 文章訪問數(shù): 3010
- HTML全文瀏覽量: 1206
- PDF下載量: 62
- 被引次數(shù): 0
出版歷程
- 收稿日期: 2019-07-11
- 修回日期: 2020-03-25
- 網(wǎng)絡(luò)出版日期: 2020-03-27
- 刊出日期: 2020-06-22

Error Correction of Lempel-Ziv-Welch Compressed Data

1.
PLA Strategic Support Force Information Engineering University, Zhengzhou 450000, China
2.
National Digital Switching System Engineering & Technology Research Center, Zhengzhou 450002, China

Funds: The National Natural Science Foundation of China (61501516, 61572518)

摘要

摘要:
無損數(shù)據(jù)壓縮系統(tǒng)在通信傳輸過程中容易出現(xiàn)錯(cuò)誤，會(huì)導(dǎo)致碼表和重構(gòu)數(shù)據(jù)出錯(cuò)并引發(fā)誤碼擴(kuò)散，影響其在文件系統(tǒng)和無線通信中的應(yīng)用。針對(duì)在通用編碼領(lǐng)域廣泛使用的無損數(shù)據(jù)壓縮算法LZW，該文分析并利用LZW壓縮數(shù)據(jù)的冗余，通過選取部分編碼碼字并動(dòng)態(tài)調(diào)整其對(duì)應(yīng)的被壓縮符號(hào)串的長(zhǎng)度來攜帶校驗(yàn)碼，提出了具有誤碼糾正能力的無損數(shù)據(jù)壓縮方法CLZW。該方法不用額外添加數(shù)據(jù)，也不改變數(shù)據(jù)規(guī)格和編碼規(guī)則，與標(biāo)準(zhǔn)LZW算法兼容。實(shí)驗(yàn)結(jié)果表明，用該方法壓縮的文件仍然能用標(biāo)準(zhǔn)LZW解碼器解壓，且該方法可以對(duì)LZW壓縮數(shù)據(jù)的誤碼進(jìn)行有效糾正。
- Lempel-Ziv-Welch算法 /
- 數(shù)據(jù)壓縮 /
- 誤碼糾正
Abstract:
Lossless data compression system is prone to bit error and causes error spread during communication transmission, which affects its application to file system and wireless communication. For the lossless data compression algorithm Lempel-Ziv-Welch (LZW), which is widely used in the field of general coding, analyzes and utilizes the redundancy of LZW compressed data, carries the check code by selecting part of the codeword and dynamically adjusting the length of its corresponding compressed string. A lossless data compression method Carrier-LZW(CLZW) with error correction capability is proposed. This method does not need additional data, does not change the data specification and coding rules, and is compatible with the standard LZW algorithm. The experimental results show that the file compressed by this method can still be decompressed by the standard LZW decoder. In the range of error correction capability, the method can effectively correct the error of LZW compressed data.
- Lempel-Ziv-Welch(LZW) algorithm /
- Data compression /
- Error correction

HTML全文

圖 1 CLZW壓縮數(shù)據(jù)中消息比特的嵌入

下載: 全尺寸圖片幻燈片

圖 2 LZW壓縮數(shù)據(jù)的誤碼糾正

下載: 全尺寸圖片幻燈片

圖 3 糾錯(cuò)率與BER的關(guān)系

下載: 全尺寸圖片幻燈片

表 1 分別用LZW與CLZW壓縮坎特伯雷語料庫(kù)的對(duì)比(K=3, L=1)

文件名	$\|T\|$	$\|T'\|$	$\|T{'_M}\|$	$l$	${l_M}$	$\|T{'_M}\|$–$\|T'\|$	$\|M\|$	R	R_M
alice29	152089	72322	76194	3.65	3.23	3872	3982	0.053538	0.055059
cp	24603	12228	12856	3.92	3.49	628	716	0.051358	0.058554
fields	11150	5316	5580	4.11	3.66	264	322	0.049661	0.060572
ptt5	513216	70228	73961	5.78	5.30	3733	4295	0.053155	0.061158
sum	38240	31940	32605	2.49	2.17	665	1356	0.020820	0.043827

下載: 導(dǎo)出CSV

表 2 分別用LZW與CLZW壓縮坎特伯雷語料庫(kù)的對(duì)比

文件名	$\|T\|$	$\|T'\|$	$\|T{'_M}\|$	$l$	${l_M}$	$\|T{'_M}\|$–$\|T'\|$	$\|M\|$	R	R_M
alice29	152089	72322	76194	3.65	3.23	3872	4113	0.053538	0.056871
cp	24603	12228	12856	3.92	3.49	628	758	0.051358	0.061989
fields	11150	5316	5580	4.11	3.66	264	331	0.049661	0.062265
ptt5	513216	70228	73961	5.78	5.30	3733	4614	0.053155	0.065700
sum	38240	31940	32605	2.49	2.17	665	1370	0.020820	0.044279

下載: 導(dǎo)出CSV

表 3 1≤ K ≤5且1≤ L ≤2攜帶消息量R_M的實(shí)驗(yàn)結(jié)果

文件名	L=1					L=2
文件名	K=1	K=2	K=3	K=4	K=5	K=1	K=2	K=3	K=4	K=5
alice29	0.081577	0.077739	0.055059	0.038675	0.024377	0.140538	0.100949	0.062275	0.037212	0.023465
cp	0.077334	0.080686	0.058554	0.040188	0.025369	0.126359	0.096884	0.058758	0.040893	0.025621
fields	0.079725	0.077587	0.060572	0.0398761	0.026660	0.116642	0.0866315	0.064385	0.040385	0.028232
ptt5	0.083042	0.080529	0.061158	0.040919	0.030843	0.130991	0.104748	0.069976	0.043431	0.030271
sum	0.073440	0.072135	0.043827	0.026355	0.018469	0.072916	0.055985	0.038270	0.029750	0.016390

下載: 導(dǎo)出CSV

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

BERTINO E, CHOO K K R, GEORGAKOPOLOUS D, et al. Internet of Things (IoT): Smart and secure service delivery[J]. ACM Transactions on Internet Technology, 2016, 16(4): 22. doi: 10.1145/3013520

TALWANA J C and HUANG Jianhua. Smart world of Internet of Things (IoT) and its security concerns[C]. 2016 IEEE International Conference on Internet of Things (iThings) and IEEE Green Computing and Communications (GreenCom) and IEEE Cyber, Physical and Social Computing (CPSCom) and IEEE Smart Data (SmartData), Chengdu, China, 2016: 240–245. doi: 10.1109/iThings-GreenCom-CPSCom-SmartData.2016.64.

WEN Lulu, ZHOU Kaile, YANG Shanlin, et al. Compression of smart meter big data: A survey[J]. Renewable and Sustainable Energy Reviews, 2018, 91: 59–69. doi: 10.1016/j.rser.2018.03.088

CHENG Ledan, GUO Songtao, WANG Ying, et al. Lifting wavelet compression based data aggregation in big data wireless sensor networks[C]. The 22nd IEEE International Conference on Parallel and Distributed Systems, Wuhan, China, 2016: 561–568. doi: 10.1109/ICPADS.2016.0080.

徐金甫, 劉露, 李偉, 等. 一種基于陣列配置加速比模型的無損壓縮算法[J]. 電子與信息學(xué)報(bào), 2018, 40(6): 1492–1498. doi: 10.11999/JEIT170900

XU Jinfu, LIU Lu, LI Wei, et al. A new lossless compression algorithm based on array configuration speedup model[J]. Journal of Electronics &Information Technology, 2018, 40(6): 1492–1498. doi: 10.11999/JEIT170900

姚軍財(cái), 劉貴忠. 一種基于人眼對(duì)比度敏感視覺特性的圖像自適應(yīng)量化方法[J]. 電子與信息學(xué)報(bào), 2016, 38(5): 1202–1210. doi: 10.11999/JEIT150848

YAO Juncai and LIU Guizhong. An adaptive quantization method of image based on the contrast sensitivity characteristics of human visual system[J]. Journal of Electronics &Information Technology, 2016, 38(5): 1202–1210. doi: 10.11999/JEIT150848

YANG J and BHATTACHARYA K. Combining image compression with digital image correlation[J]. Experimental Mechanics, 2019, 59(5): 629–642. doi: 10.1007/s11340-018-00459-y

BLASCH E, CHEN Huamei, IRVINE J M, et al. Prediction of compression-induced image interpretability degradation[J]. Optical Engineering, 2018, 57(4): 043108. doi: 10.1117/1.OE.57.4.043108

王剛, 彭華, 唐永旺. 破損壓縮文件的修復(fù)還原[J]. 電子與信息學(xué)報(bào), 2019, 41(8): 1831–1837. doi: 10.11999/JEIT180942

WANG Gang, PENG Hua, and TANG Yongwang. Repair and restoration of corrupted compressed files[J]. Journal of Electronics &Information Technology, 2019, 41(8): 1831–1837. doi: 10.11999/JEIT180942

羅瑜, 張珍珍. 一種快速的紋理預(yù)測(cè)和混合哥倫布的無損壓縮算法[J]. 電子與信息學(xué)報(bào), 2018, 40(1): 137–142. doi: 10.11999/JEIT170305

LUO Yu and ZHANG Zhenzhen. A fast-lossless compression using texture prediction and mixed golomb coding[J]. Journal of Electronics &Information Technology, 2018, 40(1): 137–142. doi: 10.11999/JEIT170305

WELCH T A. A technique for high-performance data compression[J]. Computer, 1984, 17(6): 8–19. doi: 10.1109/MC.1984.1659158

WANG Digang, ZHAO Xiaoqun, and SUN Qingquan. Novel fault-tolerant decompression method of corrupted huffman files[J]. Wireless Personal Communications, 2018, 102(4): 2555–2574. doi: 10.1007/s11277-018-5277-5

DRMOTA M and SZPANKOWSKI W. Redundancy of lossless data compression for known sources by analytic methods[J]. Foundations and Trends? in Communications and Information Theory, 2017, 13(4): 277–417. doi: 10.1561/0100000090

KOGA H and YAMAMOTO H. Asymptotic properties on codeword lengths of an optimal FV code for general sources[J]. IEEE Transactions on Information Theory, 2005, 51(4): 1546–1555. doi: 10.1109/TIT.2005.844098

FRENKEL S, KOPEETSKY M, and MOLOTKOVSKI R. Lempel-Ziv-welch compression algorithm with exponential decay[C]. The 2nd International Symposium on Stochastic Models in Reliability Engineering, Life Science and Operations Management, Beer-Sheva, Israel, 2016: 616–619. doi: 10.1109/SMRLO.2016.108.

李從鶴, 鄭輝. 一種用于文本壓縮的信源容錯(cuò)譯碼算法[J]. 無線電通信技術(shù), 2006, 32(2): 36–38, 64. doi: 10.3969/j.issn.1003-3114.2006.02.013

LI Conghe and ZHENG Hui. A fault-tolerance decoding algorithm for text compression[J]. Radio Communications Technology, 2006, 32(2): 36–38, 64. doi: 10.3969/j.issn.1003-3114.2006.02.013

KLEIN S T and SHAPIRA D. Practical fixed length Lempel-Ziv coding[J]. Discrete Applied Mathematics, 2014, 163: 326–333. doi: 10.1016/j.dam.2013.08.022

ZHANG Jie, YANG Enhui, and KIEFFER J C. A universal grammar-based code for lossless compression of binary trees[J]. IEEE Transactions on Information Theory, 2014, 60(3): 1373–1386. doi: 10.1109/TIT.2013.2295392

KWON B, GONG M, and LEE S. Novel error detection algorithm for LZSS compressed data[J]. IEEE Access, 2017, 5: 8940–8947. doi: 10.1109/ACCESS.2017.2704900

KITAKAMI M and KAWASAKI T. Burst error recovery method for LZSS coding[J]. IEICE Transactions on Information and Systems, 2009, 92(12): 2439–2444. doi: 10.1587/transinf.e92.d.2439

PEREIRA Z C, PELLENZ M E, SOUZA R D, et al. Unequal error protection for LZSS compressed data using Reed-Solomon codes[J]. IET Communications, 2007, 1(4): 612–617. doi: 10.1049/iet-com:20060530

KEMPA D and KOSOLOBOV D. LZ-end parsing in compressed space[C]. 2017 Data Compression Conference, Snowbird, USA, 2017: 350-359.

DO H H, JANSSON J, SADAKANE K, et al. Fast relative Lempel-Ziv self-index for similar sequences[J]. Theoretical Computer Science, 2014, 532: 14–30. doi: 10.1016/j.tcs.2013.07.024

REED I S and SOLOMON G. Polynomial codes over certain finite fields[J]. Journal of the Society for Industrial and Applied Mathematics, 1960, 8(2): 300–304. doi: 10.1137/0108018

LOUCHARD G and SZPANKOWSKI W. On the average redundancy rate of the Lempel-Ziv code[J]. IEEE Transactions on Information Theory, 1997, 43(1): 2–8. doi: 10.1109/18.567640

DAS S, BULL D M, and WHATMOUGH P N. Error-resilient design techniques for reliable and dependable computing[J]. IEEE Transactions on Device and Materials Reliability, 2015, 15(1): 24–34. doi: 10.1109/tdmr.2015.2389038

The Canterbury corpus[EB/OL]. http://corpus.canterbury.ac.nz/descriptions/#cantrbry, 2018.

相關(guān)文章

施引文獻(xiàn)

資源附件(0)

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