Density evolution for asymmetric memoryless channels

Research output: Contribution to journalArticlepeer-review

45 Scopus citations

Abstract

Density evolution (DE) is one of the most powerful analytical tools for Iow-density parity-check (LDPC) codes and graph codes with message passing decoding algorithms. With channel symmetry as one of its fundamental assumptions, density evolution has been widely and successfully applied to different channels, including binary erasure channels (BECs), binary symmetric channels (BSCs), binary additive white Gaussian noise (BiAWGN) channels, etc. This paper generalizes density evolution for asymmetric memoryless channels, which in turn broadens the applications to general memoryless channels, e.g., z-channels, composite white Gaussian noise channels, etc. The central theorem underpinning this generalization is the convergence to perfect projection for any fixed-size supporting tree. A new iterative formula of the same complexity is then presented and the necessary theorems for the performance concentration theorems are developed. Several properties of the new density evolution method are explored, including stability results for general asymmetric memoryless channels. Simulations, code optimizations, and possible new applications suggested by this new density evolution method are also provided. This result is also used to prove the typicality of linear LDPC codes among the coset code ensemble when the minimum check node degree is sufficiently large. It is shown that the convergence to perfect projection is essential to the belief propagation (BP) algorithm even when only symmetric channels are considered. Hence, the proof of the convergence to perfect projection serves also as a completion of the theory of classical density evolution for symmetric memoryless channels.

Original languageEnglish (US)
Pages (from-to)4216-4236
Number of pages21
JournalIEEE Transactions on Information Theory
Volume51
Issue number12
DOIs
StatePublished - Dec 2005

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences

Keywords

  • Asymmetric channels
  • Density evolution (DE)
  • Low-density parity-check (LDPC) codes
  • Rank of random matrices
  • Sum-product algorithms
  • Z-channels

Fingerprint Dive into the research topics of 'Density evolution for asymmetric memoryless channels'. Together they form a unique fingerprint.

Cite this