Message passing algorithms for non-linear nodes and data compression

Abstract

The use of parity-check gates in information theory has proved to be very efficient. In particular, error correcting codes based on parity checks over low-density graphs show excellent performances. Another basic issue of information theory, namely data compression, can be addressed in a similar way by a kind of dual approach. The theoretical performance of such a Parity Source Coder can attain the optimal limit predicted by the general rate-distortion theory. However, in order to turn this approach into an efficient compression code (with fast encoding/decoding algorithms) one must depart from parity checks and use some general random gates. By taking advantage of analytical approaches from the statistical physics of disordered systems and SP-like message passing algorithms, we construct a compressor based on low-density non-linear gates with a very good theoretical and practical performance.

13 pages, European Conference on Complex Systems, Paris (Nov 2005)

Cited by in corpus (6)

• Analysis of LDGM and compound codes for lossy compression and binning
• Low density codes achieve the rate-distortion bound
• Low-density graph codes that are optimal for source/channel coding and binning
• On Superposition Coding for the Wyner-Ziv Problem
• Low-density constructions can achieve the Wyner-Ziv and Gelfand-Pinsker bounds
• Lower Bounds on the Rate-Distortion Function of LDGM Codes