A coding theorem for lossy data compression by LDPC codes

Author

Matsunaga, Yuko ; Yamamoto, Hirosuke

Author_Institution

Internet Syst. Res. Labs., NEC Corp., Kanagawa, Japan

Volume

49

Issue

9

fYear

2003

Firstpage

2225

Lastpage

2229

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.

Keywords

matrix algebra; parity check codes; rate distortion theory; source coding; LDPC codes; asymptotic performance; binary independent identically distributed source; code length; coding theorem; column weight; i.i.d. source; lossy data compression; lossy source coding; low-density parity-check codes; parity-check matrices; rate-distortion function; Belief propagation; Data compression; Decoding; Error correction codes; Parity check codes; Performance loss; Propagation losses; Rate-distortion; Source coding; Viterbi algorithm;

fLanguage

English

Journal_Title

Information Theory, IEEE Transactions on

Publisher

ieee

ISSN

0018-9448

Type

jour

DOI

10.1109/TIT.2003.815805

Filename

1226608