The Journal of Korean Institute of Communications and Information Sciences (한국통신학회논문지)

The Korean Institute of Commucations and Information Sciences (한국통신학회)
권호 표지
DOI QR코드

DOI QR Code

A Novel Error Detection Algorithm Based on the Structural Pattern of LZ78-Compression Data

LZ78 압축 데이터의 구조적 패턴에 기반한 새로운 오류 검출 알고리즘

  • Gong, Myongsik (Yonsei University, Department of Electrical and Electronic Engineering) ;
  • Kwon, Beom (Yonsei University, Department of Electrical and Electronic Engineering) ;
  • Kim, Jinwoo (Yonsei University, Department of Electrical and Electronic Engineering) ;
  • Lee, Sanghoon (Yonsei University, Department of Electrical and Electronic Engineering)
  • Received : 2016.08.17
  • Accepted : 2016.11.18
  • Published : 2016.11.30
Download PDF
⟨ Previous Next ⟩

Abstract

In this paper, we propose a novel error detection algorithm for LZ78-compressed data. The conventional error detection method adds a certain number of parity bits in transmission, and the receiver checks the number of bits representing '1' to detect the errors. These conventional methods use additional bits resulting in increased redundancy in the compressed data which results in reduced effectiveness of the final compressed data. In this paper, we propose error detection algorithm using the structural properties of LZ78 compression without using additional bits in the compressed data. The simulation results show that the error detection ratio of the proposed algorithm is about 1.3 times better for error detection than conventional algorithms.

본 논문에서는 LZ78 알고리즘으로 압축된 데이터의 오류 검출 알고리즘을 제안하였다. 기존의 비트 오류를 검출하는 방법들은 송신 단에서 패리티(parity) 비트를 추가하여 전송한 후, 수신 단에서 값이 '1'인 비트의 개수를 이용하여 오류를 검출하는 방법을 사용하였다. 이러한 기존의 방법들은 오류 검출을 위하여 추가적인 비트를 사용하는데 이는 데이터의 크기를 줄이는 것을 목적으로 하는 압축 데이터에 대해서는 적합하지 않은 방법이다. 따라서 본 논문에서는 LZ78 알고리즘 기반의 압축 데이터에서 추가적인 비트를 사용하지 않고 알고리즘의 구조적인 특성을 이용하여 오류를 검출하는 방법을 제안하였다. 실험을 통하여 제안하는 알고리즘의 오류 검출율에 대한 효율이 기존의 오류 검출 알고리즘에 비해 약 1.3 배 높은 효율을 가지는 것을 보였다.

Keywords

References

  1. J. Park, T.-W. Ban, and B. C. Jung, "A compressed sensing-based signal recovery technique for multi-user spatial modulation systems," J. KICS, vol. 39, no. 7, pp. 424-430, Jul. 2014.
  2. I. Lee, H. Kim, T. Oh, and S. Lee "Study on low delay and adaptive video transmission for a surveillance system in visual sensor networks," J. KICS, vol. 39, no. 5, pp. 435-446, May 2014.
  3. Thu L. N. Nguyen, H. Jung, and Y. Shin, "A signal detection and estimation method based on compressive sensing," J. KICS, vol. 40, no. 6, pp. 1024-1031, Jun. 2015. https://doi.org/10.7840/kics.2015.40.6.1024
  4. J. Ziv and A. Lempelm "A universal algorithm for sequential data compression," IEEE Trans. Inf. Theory, vol. 23, no. 3, pp. 337-343, 1977. https://doi.org/10.1109/TIT.1977.1055714
  5. J. Ziv and A. Lempel, "Compression of individual sequences via variable-rate coding," IEEE Trans. Inf. Theory, vol. 24, no. 5, pp. 530-536, 1978. https://doi.org/10.1109/TIT.1978.1055934
  6. S. Jung, D.-I. Seo, and B.-R. Moon, "Performance improvement of LZ77 algorithm using a strategy table and a genetic algorithm," J. KIISE, vol. 31, no. 12, pp. 1628-1638, Dec. 2004.
  7. T. A. Welch, "A technique for high-performance data compression," Computer, vol. 17, no. 6. pp. 8-19, 1984.
  8. J. A. Storer and T. G. Szymanski, "Data compression via textual substitution," JACM, vol. 29, no. 4, pp. 928-951, Oct. 1982. https://doi.org/10.1145/322344.322346
  9. D. MacKay, Information theory, inference and learning algorithms, Cambridge University Press, 2003.
  10. T. K. Moon, Error correction coding, Mathematical Methods and Algorithms, John Wiley & Sons, 2005.

Cited by

  1. 지리정보 데이터 압축률 향상을 위한 Run-Length/Byte-Packing 압축 알고리즘 설계 및 구현 vol.21, pp.10, 2016, https://doi.org/10.6109/jkiice.2017.21.10.1935