Research Projects

Lower Bounds on the Rate-Distortion Function of LDGM Codes

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.

More information: http://www.eecs.berkeley.edu/~adim