A new data compression algorithm for sources with memory based on error correcting codes

G. Caire, S. Shamai, S. Verdu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

46 Scopus citations

Abstract

A new fixed-length asymptotically optimal scheme for lossless compression of stationary ergodic tree sources with memory is proposed. Our scheme is based on the concatenation of the Burrows-Wheeler block sorting transform with the syndrome former of a linear error correcting code. Low-density parity-check (LDPC) codes together with belief propagation decoding lead to linear compression and decompression times, and to natural universal implementation of the algorithm.

Original languageEnglish (US)
Title of host publicationProceedings - 2003 IEEE Information Theory Workshop, ITW 2003
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages291-295
Number of pages5
ISBN (Electronic)0780377990, 9780780377998
DOIs
StatePublished - Jan 1 2003
Event2003 IEEE Information Theory Workshop, ITW 2003 - Paris, France
Duration: Mar 31 2003Apr 4 2003

Publication series

NameProceedings - 2003 IEEE Information Theory Workshop, ITW 2003

Other

Other2003 IEEE Information Theory Workshop, ITW 2003
CountryFrance
CityParis
Period3/31/034/4/03

All Science Journal Classification (ASJC) codes

  • Computational Theory and Mathematics
  • Computer Networks and Communications
  • Information Systems
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'A new data compression algorithm for sources with memory based on error correcting codes'. Together they form a unique fingerprint.

  • Cite this

    Caire, G., Shamai, S., & Verdu, S. (2003). A new data compression algorithm for sources with memory based on error correcting codes. In Proceedings - 2003 IEEE Information Theory Workshop, ITW 2003 (pp. 291-295). [1216751] (Proceedings - 2003 IEEE Information Theory Workshop, ITW 2003). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ITW.2003.1216751