Universal variable-length data compression of binary sources using fountain codes

Giuseppe Caire, Shlomo Shamai, Amin Shokrollahi, Sergio Verdú

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

15 Scopus citations

Abstract

This paper proposes a universal variable-length lossless compression algorithm based on fountain codes. The compressor concatenates the Burrows-Wheeler block sorting transform (BWT) with a fountain encoder, together with the closed-loop iterative doping algorithm. The decompressor uses a Belief Propagation algorithm in conjunction with the iterative doping algorithm and the inverse BWT. Linear-time compression/decompression complexity and competitive performance with respect to state-of-the-art compression algorithms are achieved.

Original languageEnglish (US)
Title of host publication2004 IEEE Information Theory Workshop - Proceedings, ITW
Pages123-128
Number of pages6
StatePublished - Dec 1 2004
Event2004 IEEE Information Theory Workshop - Proceedings, ITW - San Antonio, TX, United States
Duration: Oct 24 2004Oct 29 2004

Publication series

Name2004 IEEE Information Theory Workshop - Proceedings, ITW

Other

Other2004 IEEE Information Theory Workshop - Proceedings, ITW
CountryUnited States
CitySan Antonio, TX
Period10/24/0410/29/04

All Science Journal Classification (ASJC) codes

  • Engineering(all)

Fingerprint Dive into the research topics of 'Universal variable-length data compression of binary sources using fountain codes'. Together they form a unique fingerprint.

  • Cite this

    Caire, G., Shamai, S., Shokrollahi, A., & Verdú, S. (2004). Universal variable-length data compression of binary sources using fountain codes. In 2004 IEEE Information Theory Workshop - Proceedings, ITW (pp. 123-128). (2004 IEEE Information Theory Workshop - Proceedings, ITW).