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

G. Caire; S. Shamai; S. Verdu

doi:10.1109/ITW.2003.1216751

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 proceeding › Conference contribution

52 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 language	English (US)
Title of host publication	Proceedings - 2003 IEEE Information Theory Workshop, ITW 2003
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	291-295
Number of pages	5
ISBN (Electronic)	0780377990, 9780780377998
DOIs	https://doi.org/10.1109/ITW.2003.1216751
State	Published - 2003
Event	2003 IEEE Information Theory Workshop, ITW 2003 - Paris, France Duration: Mar 31 2003 → Apr 4 2003

Publication series

Name	Proceedings - 2003 IEEE Information Theory Workshop, ITW 2003

Other

Other	2003 IEEE Information Theory Workshop, ITW 2003
Country/Territory	France
City	Paris
Period	3/31/03 → 4/4/03

All Science Journal Classification (ASJC) codes

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

Access to Document

10.1109/ITW.2003.1216751

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). Article 1216751 (Proceedings - 2003 IEEE Information Theory Workshop, ITW 2003). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ITW.2003.1216751

@inproceedings{5ccc89d592ac497f91ca8a5c698204d3,

title = "A new data compression algorithm for sources with memory based on error correcting codes",

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.",

author = "G. Caire and S. Shamai and S. Verdu",

note = "Publisher Copyright: {\textcopyright} 2003 IEEE.; 2003 IEEE Information Theory Workshop, ITW 2003 ; Conference date: 31-03-2003 Through 04-04-2003",

year = "2003",

doi = "10.1109/ITW.2003.1216751",

language = "English (US)",

series = "Proceedings - 2003 IEEE Information Theory Workshop, ITW 2003",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "291--295",

booktitle = "Proceedings - 2003 IEEE Information Theory Workshop, ITW 2003",

address = "United States",

}

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., 1216751, Proceedings - 2003 IEEE Information Theory Workshop, ITW 2003, Institute of Electrical and Electronics Engineers Inc., pp. 291-295, 2003 IEEE Information Theory Workshop, ITW 2003, Paris, France, 3/31/03. https://doi.org/10.1109/ITW.2003.1216751

A new data compression algorithm for sources with memory based on error correcting codes. / Caire, G.; Shamai, S.; Verdu, S.
Proceedings - 2003 IEEE Information Theory Workshop, ITW 2003. Institute of Electrical and Electronics Engineers Inc., 2003. p. 291-295 1216751 (Proceedings - 2003 IEEE Information Theory Workshop, ITW 2003).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

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

AU - Caire, G.

AU - Shamai, S.

AU - Verdu, S.

PY - 2003

Y1 - 2003

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84939161197&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84939161197&partnerID=8YFLogxK

U2 - 10.1109/ITW.2003.1216751

DO - 10.1109/ITW.2003.1216751

M3 - Conference contribution

AN - SCOPUS:84939161197

T3 - Proceedings - 2003 IEEE Information Theory Workshop, ITW 2003

SP - 291

EP - 295

BT - Proceedings - 2003 IEEE Information Theory Workshop, ITW 2003

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2003 IEEE Information Theory Workshop, ITW 2003

Y2 - 31 March 2003 through 4 April 2003

ER -

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

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this