高级搜索

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

王刚 靳彦青 彭华 张光伟

引用本文: 王刚, 靳彦青, 彭华, 张光伟. Lempel-Ziv-Welch压缩数据的误码纠正[J]. 电子与信息学报, 2020, 42(6): 1436-1443. 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, 2020, 42(6): 1436-1443. 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 22nd IEEE 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 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.

    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]

      毛秀海, 李凡, 左小磊. DNA数据存储. 电子与信息学报, 2020, 42(6): 1303-1312.

    2. [2]

      田俊峰, 井宣. 多方参与高效撤销组成员的共享数据审计方案. 电子与信息学报, 2020, 42(6): 1534-1541.

    3. [3]

      王立辉, 闫守礼, 李清. 一种轻量级数据加密标准循环掩码实现方案. 电子与信息学报, 2020, 41(0): 1-8.

    4. [4]

      左志斌, 常朝稳, 祝现威. 一种基于数据平面可编程的软件定义网络报文转发验证机制. 电子与信息学报, 2020, 42(5): 1110-1117.

    5. [5]

      王永娟, 王涛, 袁庆军, 高杨, 王相宾. 密码算法旁路立方攻击改进与应用. 电子与信息学报, 2020, 42(5): 1087-1093.

    6. [6]

      贾连印, 陈明鲜, 李孟娟, 游进国, 丁家满. 基于状态视图的高效Hilbert编码和解码算法. 电子与信息学报, 2020, 42(6): 1494-1501.

    7. [7]

      游凌, 李伟浩, 张文林, 王科人. 基于深度神经网络的Morse码自动译码算法. 电子与信息学报, 2020, 41(0): 1-6.

    8. [8]

      蒲磊, 冯新喜, 侯志强, 余旺盛. 基于自适应背景选择和多检测区域的相关滤波算法. 电子与信息学报, 2020, 41(0): 1-7.

    9. [9]

      姚敏立, 王旭健, 张峰干, 戴定成. 基于动态参数差分进化算法的多约束稀布矩形面阵优化. 电子与信息学报, 2020, 42(5): 1281-1287.

    10. [10]

      高东, 梁子林. 基于能量效率的双层非正交多址系统资源优化算法. 电子与信息学报, 2020, 42(5): 1237-1243.

    11. [11]

      陈根华, 陈伯孝. 复杂多径信号下基于空域变换的米波雷达稳健测高算法. 电子与信息学报, 2020, 42(5): 1297-1302.

    12. [12]

      归伟夏, 陆倩, 苏美力. 关于系统级故障诊断的烟花-反向传播神经网络算法. 电子与信息学报, 2020, 42(5): 1102-1109.

    13. [13]

      张斌, 吴浩明. 一种面向连接的快速多维包分类算法. 电子与信息学报, 2020, 42(6): 1526-1533.

    14. [14]

      赵国繁, 唐伦, 胡彦娟, 赵培培, 陈前斌. 面向可靠性的5G网络切片重构及映射算法. 电子与信息学报, 2020, 42(6): 1478-1485.

    15. [15]

      王威丽, 陈前斌, 唐伦. 虚拟网络切片中的在线异常检测算法研究. 电子与信息学报, 2020, 42(6): 1460-1467.

    16. [16]

      张凯, 陈彬, 许志伟. 基于多目标进化策略算法的DNA核酸编码设计. 电子与信息学报, 2020, 42(6): 1365-1373.

    17. [17]

      曹祥红, 李欣妍, 魏晓鸽, 李森, 黄梦溪, 李栋禄. 基于Dijkstra-ACO混合算法的应急疏散路径动态规划. 电子与信息学报, 2020, 42(6): 1502-1509.

    18. [18]

      牛莹, 张勋才. 基于变步长约瑟夫遍历和DNA动态编码的图像加密算法. 电子与信息学报, 2020, 42(6): 1383-1391.

    19. [19]

      王年, 胡旭阳, 朱凡, 唐俊. 基于视图感知的单视图三维重建算法. 电子与信息学报, 2020, 42(0): 1-8.

    20. [20]

      刘新, 阎焜, 杨光耀, 叶盛波, 张群英, 方广有. UWB-MIMO穿墙雷达三维成像与运动补偿算法研究. 电子与信息学报, 2020, 41(0): 1-8.

  • 图 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≤ K ≤5且1≤ L ≤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下载量:  16
  • 文章访问数:  608
  • HTML全文浏览量:  218
文章相关
  • 通讯作者:  彭华, phzttyw@126.com
  • 收稿日期:  2019-07-11
  • 录用日期:  2020-03-25
  • 网络出版日期:  2020-03-27
  • 刊出日期:  2020-06-01
通讯作者: 陈斌, bchen63@163.com
  • 1. 

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

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

/

返回文章