Analysis of LDGM and compound codes for lossy compression and binning

Abstract

Recent work has suggested that low-density generator matrix (LDGM) codes are likely to be effective for lossy source coding problems. We derive rigorous upper bounds on the effective rate-distortion function of LDGM codes for the binary symmetric source, showing that they quickly approach the rate-distortion function as the degree increases. We also compare and contrast the standard LDGM construction with a compound LDPC/LDGM construction introduced in our previous work, which provably saturates the rate-distortion bound with finite degrees. Moreover, this compound construction can be used to generate nested codes that are simultaneously good as source and channel codes, and are hence well-suited to source/channel coding with side information. The sparse and high-girth graphical structure of our constructions render them well-suited to message-passing encoding.

5 pages; to appear in Workshop on Information Theory and its Applications, February 2006, San Diego

References in corpus (4)

• Rigorous decimation-based construction of ground pure states for spin glass models on random lattices
• Iterative Quantization Using Codes On Graphs
• Thouless-Anderson-Palmer Approach for Lossy Compression
• Message passing algorithms for non-linear nodes and data compression

Cited by in corpus (5)

• Binary quantization using Belief Propagation with decimation over factor graphs of LDGM codes
• Low-density graph codes that are optimal for source/channel coding and binning
• Design and Analysis of LDGM-Based Codes for MSE Quantization
• Lower Bounds on the Rate-Distortion Function of LDGM Codes
• Analytical Framework of LDGM-based Iterative Quantization with Decimation