Computer Science – Information Theory
Scientific paper
2005-08-15
Computer Science
Information Theory
To appear in the Proceedings of the International Symposium on Information Theory, Adelaide, Australia; September, 2005
Scientific paper
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.
Maneva Elitza
Wainwright Martin J.
No associations
LandOfFree
Lossy source encoding via message-passing and decimation over generalized codewords of LDGM codes does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Lossy source encoding via message-passing and decimation over generalized codewords of LDGM codes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Lossy source encoding via message-passing and decimation over generalized codewords of LDGM codes will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-138276