A coding theorem for lossy data compression by LDPC codes

Abstract

In this article, low-density parity-check (LDPC) codes are applied to lossy source coding and we study how the asymptotic performance of MacKay's (see ibid, vol.45, p.399-431, Mar. 1999 and vol.47, p.2101, July, 2001) LDPC codes depends on the sparsity of the parity-check matrices in the source coding of the binary independent and identically distributed (i.i.d.) source with Pr{x=1}=0.5. In the sequel, it is shown that an LDPC code with column weight O(logn) for code length n can attain the rate-distortion function asymptotically.