Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences

COLLEGE OF ENGINEERING

UC Berkeley

   

2008 Research Summary

Lower Bounds on the Rate-Distortion Function of LDGM Codes

View Current Project Information

Georgios Alexandros Dimakis, Martin Wainwright and Kannan Ramchandran

We analyze the performance of low-density generator matrix (LDGM) codes for lossy source coding. We first develop a generic technique for deriving lower bounds on the effective rate-distortion functions of binary linear codes. This result provides a source coding analog of a classical result due to Gallager for channel coding over the binary symmetric channel. We illustrate this method for the ensemble of check-regular low-density generator matrix (LDGM) codes by deriving an explicit lower bound on its rate-distortion performance as a function of the check degree.

[1]
A. G. Dimakis, M. J. Wainwright, and K. Ramchandran, "Lower Bounds on the Rate-Distortion Function of LDGM Codes," Information Theory Workshop (ITW), 2007.