Get our free extension to see links to code for papers anywhere online!


Lossy source encoding via message-passing and decimation over generalized codewords of LDGM codes

Add code

Aug 15, 2005
Martin J. Wainwright, Elitza Maneva


Share this with someone who'll enjoy it:


We describe message-passing and decimation approaches for lossy source coding using low-density generator matrix (LDGM) codes. In particular, this paper addresses the problem of encoding a Bernoulli(0.5) source: for randomly generated LDGM codes with suitably irregular degree distributions, our methods yield performance very close to the rate distortion limit over a range of rates. Our approach is inspired by the survey propagation (SP) algorithm, originally developed by Mezard et al. for solving random satisfiability problems. Previous work by Maneva et al. shows how SP can be understood as belief propagation (BP) for an alternative representation of satisfiability problems. In analogy to this connection, our approach is to define a family of Markov random fields over generalized codewords, from which local message-passing rules can be derived in the standard way. The overall source encoding method is based on message-passing, setting a subset of bits to their preferred values (decimation), and reducing the code.

* To appear in the Proceedings of the International Symposium on Information Theory, Adelaide, Australia; September, 2005 


   Access Paper Source



Share this with someone who'll enjoy it: