高级搜索

Lempel-Ziv-Welch压缩数据的误码纠正

王刚 靳彦青 彭华 张光伟

引用本文: 王刚, 靳彦青, 彭华, 张光伟. Lempel-Ziv-Welch压缩数据的误码纠正[J]. 电子与信息学报, doi: 10.11999/JEIT190520 shu
Citation:  Gang WANG, Yanqing JIN, Hua PENG, Guangwei ZHANG. Error Correction of Lempel-Ziv-Welch Compressed Data[J]. Journal of Electronics and Information Technology, doi: 10.11999/JEIT190520 shu

Lempel-Ziv-Welch压缩数据的误码纠正

    作者简介: 王刚: 男,1981年生,副教授,研究方向为信号分析、信息处理、模式识别;
    靳彦青: 女,1983年生,工程师,研究方向为移动通信;
    彭华: 男,1973年生,教授,研究方向为通信信号处理、软件无线电;
    张光伟: 男,1984年生,讲师,研究方向为信息安全
    通讯作者: 彭华,phzttyw@126.com
  • 基金项目: 国家自然科学基金(61572518, 61501516)

摘要: 无损数据压缩系统在通信传输过程中容易出现错误,会导致码表和重构数据出错并引发误码扩散,影响其在文件系统和无线通信中的应用。针对在通用编码领域广泛使用的无损数据压缩算法LZW,分析并利用LZW压缩数据的冗余,通过选取部分编码码字并动态调整其对应的被压缩符号串的长度来携带校验码,该文提出了具有误码纠正能力的无损数据压缩方法CLZW。该方法不用额外添加数据,也不改变数据规格和编码规则,与标准LZW算法兼容。实验结果表明,用该方法压缩的文件仍然能用标准LZW解码器解压,且该方法可以对LZW压缩数据的误码进行有效纠正。

English

    1. [1]

      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

    2. [2]

      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.

    3. [3]

      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

    4. [4]

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

    5. [5]

      徐金甫, 刘露, 李伟, 等. 一种基于阵列配置加速比模型的无损压缩算法[J]. 电子与信息学报, 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

    6. [6]

      姚军财, 刘贵忠. 一种基于人眼对比度敏感视觉特性的图像自适应量化方法[J]. 电子与信息学报, 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

    7. [7]

      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

    8. [8]

      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

    9. [9]

      王刚, 彭华, 唐永旺. 破损压缩文件的修复还原[J]. 电子与信息学报, 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

    10. [10]

      罗瑜, 张珍珍. 一种快速的纹理预测和混合哥伦布的无损压缩算法[J]. 电子与信息学报, 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

    11. [11]

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

    12. [12]

      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

    13. [13]

      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

    14. [14]

      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

    15. [15]

      FRENKEL S, KOPEETSKY M, and MOLOTKOVSKI R. Lempel-Ziv-welch compression algorithm with exponential decay[C]. The 2016 Second 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.

    16. [16]

      李从鹤, 郑辉. 一种用于文本压缩的信源容错译码算法[J]. 无线电通信技术, 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

    17. [17]

      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

    18. [18]

      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

    19. [19]

      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

    20. [20]

      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

    21. [21]

      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

    22. [22]

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

    23. [23]

      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

    24. [24]

      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

    25. [25]

      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

    26. [26]

      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

    27. [27]

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

    1. [1]

      吴倩, 张荣, 徐大卫. 基于稀疏表示的高光谱数据压缩算法. 电子与信息学报,

    2. [2]

      翟双, 钱志鸿, 刘晓慧, 孙大洋. 无线传感器网络中基于序列相关性的数据压缩算法. 电子与信息学报,

    3. [3]

      蒋鹏, 李胜强. 基于最优阶估计与分布式分簇的传感器网络数据压缩方法研究. 电子与信息学报,

    4. [4]

      郭浩然, 庞建民. 基于提升小波的地形数据混合熵编码压缩与实时渲染. 电子与信息学报,

    5. [5]

      仇晓兰, 雷斌, 葛蕴萍, 胡东辉, 丁赤飚. SAR原始数据两种量化压缩方式的性能评估. 电子与信息学报,

    6. [6]

      李冰, 龙冰洁, 刘勇. 一种基于后缀排序快速实现Burrows-Wheeler变换的方法. 电子与信息学报,

    7. [7]

      谭丽, 孙季丰, 郭礼华. 基于Memetic算法的DNA序列数据压缩方法. 电子与信息学报,

    8. [8]

      潘志刚, 王岩飞. 基于DCT的分块自适应量化算法及其用于SAR原始数据压缩. 电子与信息学报,

    9. [9]

      曾尚春, 朱兆达. 一种距离聚焦后的SAR原始数据压缩算法. 电子与信息学报,

    10. [10]

      秦蕾, 王岩飞, 胡晓新. 快速可变速率SAR原始数据压缩算法. 电子与信息学报,

    11. [11]

      胡晓新, 王岩飞, 秦蕾. 基于提升小波的SAR原始数据压缩算法. 电子与信息学报,

    12. [12]

      宋鸿梅, 王岩飞, 潘志刚. 基于DCT-TCQ的SAR原始数据压缩算法. 电子与信息学报,

    13. [13]

      张文超, 王岩飞, 潘志刚. 合成孔径雷达原始数据压缩AP算法幅相比特分配研究. 电子与信息学报,

    14. [14]

      潘志刚, 王岩飞. 一种基于小波变换的高倍数SAR原始数据压缩算法. 电子与信息学报,

    15. [15]

      王雷春, 马传香. 传感器网络中一种基于一元线性回归模型的空时数据压缩算法. 电子与信息学报,

    16. [16]

      杨耀增. 合成孔径雷达原始数据压缩. 电子与信息学报,

    17. [17]

      许耀昌, 平西建. 图象数据压缩的DCT法. 电子与信息学报,

    18. [18]

      赵宇鹏, 万锋, 雷宏. 部分饱和SAR原始数据压缩. 电子与信息学报,

    19. [19]

      祁海明, 禹卫东. 基于实测数据的原始数据压缩对InSAR系统测高影响研究. 电子与信息学报,

    20. [20]

      李信, 祁海明, 华斌, 雷宏, 禹卫东. 星载SAR原始数据压缩引起的目标辐射误差机理研究. 电子与信息学报,

  • 图 1  CLZW压缩数据中消息比特的嵌入

    图 2  LZW压缩数据的误码纠正

    图 3  纠错率与BER的关系

    表 1  分别用LZW与CLZW压缩坎特伯雷语料库的对比(K=3,L=1)

    文件名$|T|$$|T'|$$|T{'_M}|$$l$${l_M}$$|T{'_M}|$–$|T'|$$|M|$RRM
    alice2915208972322761943.653.23387239820.0535380.055059
    cp2460312228128563.923.496287160.0513580.058554
    fields11150531655804.113.662643220.0496610.060572
    ptt551321670228739615.785.30373342950.0531550.061158
    sum3824031940326052.492.1766513560.0208200.043827
    下载: 导出CSV

    表 2  分别用LZW与CLZW压缩坎特伯雷语料库的对比

    文件名$|T|$$|T'|$$|T{'_M}|$$l$${l_M}$$|T{'_M}|$–$|T'|$$|M|$RRM
    alice2915208972322761943.653.23387241130.0535380.056871
    cp2460312228128563.923.496287580.0513580.061989
    fields11150531655804.113.662643310.0496610.062265
    ptt551321670228739615.785.30373346140.0531550.065700
    sum3824031940326052.492.1766513700.0208200.044279
    下载: 导出CSV

    表 3  $1 \le K \le 5$$1 \le L \le 2$携带消息量RM的实验结果

    文件名L=1L=2
    K=1K=2K=3K=4K=5K=1K=2K=3K=4K=5
    alice290.0815770.0777390.0550590.0386750.0243770.1405380.1009490.0622750.0372120.023465
    cp0.0773340.0806860.0585540.0401880.0253690.1263590.0968840.0587580.0408930.025621
    fields0.0797250.0775870.0605720.03987610.0266600.1166420.08663150.0643850.0403850.028232
    ptt50.0830420.0805290.0611580.0409190.0308430.1309910.1047480.0699760.0434310.030271
    sum0.0734400.0721350.0438270.0263550.0184690.0729160.0559850.0382700.0297500.016390
    下载: 导出CSV
  • 加载中
图(3)表(3)
计量
  • PDF下载量:  0
  • 文章访问数:  38
  • HTML全文浏览量:  30
文章相关
  • 通讯作者:  彭华, phzttyw@126.com
  • 收稿日期:  2019-07-11
  • 录用日期:  2020-03-27
  • 网络出版日期:  2020-03-25
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

/

返回文章