Fountain codes for lossless data compression

Caire, Giuseppe;Shamai, Shlomo Shitz;Shokrollahi, A; Verdu, Sergio
DIMACS 2005, Algebraic Coding Theory and Information Theory Workshop, May 5-6, 2005, Piscataway, NJ, USA, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol.68, December 2005

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


DOI
Type:
Conférence
City:
Piscataway
Date:
2005-12-15
Department:
Systèmes de Communication
Eurecom Ref:
1877
Copyright:
First published in in DIMACS 2005, Algebraic Coding Theory and Information Theory Workshop, May 5-6, 2005, Piscataway, NJ, USA, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol.68, December 2005, published by the American Mathematical Society

PERMALINK : https://www.eurecom.fr/publication/1877