TR2006-038

Low-Density Constructions can Achieve the Wyner-Ziv and Gelfand-Pinsker Bounds


    •  Emin Martinian and Martin Wainwright, "Low-Density Constructions can Achieve the Wyner-Ziv and Gelfand-Pinsker Bounds", Tech. Rep. TR2006-038, Mitsubishi Electric Research Laboratories, Cambridge, MA, June 2006.
      BibTeX TR2006-038 PDF
      • @techreport{MERL_TR2006-038,
      • author = {Emin Martinian and Martin Wainwright},
      • title = {Low-Density Constructions can Achieve the Wyner-Ziv and Gelfand-Pinsker Bounds},
      • institution = {MERL - Mitsubishi Electric Research Laboratories},
      • address = {Cambridge, MA 02139},
      • number = {TR2006-038},
      • month = jun,
      • year = 2006,
      • url = {https://www.merl.com/publications/TR2006-038/}
      • }
Abstract:

We describe and analyze sparse graphical code constructions for the problems of source coding with decoder side information (the Wyner-Ziv problem), and channel coding with encoder side information (the Gelfand-Pinsker problem). Our approach relies on a combination of low-density parity check (LDPC) codes and low-density generator matrix (LDGM) codes, and produces sparse constructions that are simultaneously good as both source and channel codes. In particular, we prove that under maximum likelihood encoding/decoding, there exist low-density codes (i.e., with finite degrees) from our constructions that can saturate both the Wyner-Ziv and Gelfand-Pinsker bounds.