Density Evolution for Asymmetric Memoryless Channels

DOI10.1109/TIT.2005.858931zbMATH Open1318.94054arXivcs/0509014MaRDI QIDQ3547766FDOQ3547766

Authors: Chih-Chun Wang, Sanjeev R. Kulkarni, H. Vincent Poor 

Publication date: 21 December 2008

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Abstract: Density evolution is one of the most powerful analytical tools for low-density parity-check (LDPC) codes and graph codes with message passing decoding algorithms. With channel symmetry as one of its fundamental assumptions, density evolution (DE) has been widely and successfully applied to different channels, including binary erasure channels, binary symmetric channels, binary additive white Gaussian noise channels, etc. This paper generalizes density evolution for non-symmetric 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 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.

Full work available at URL: https://arxiv.org/abs/cs/0509014

Recommendations

• Fixed points and stability of density evolution
• Typical performance of regular low-density parity-check codes over general symmetric channels
• The density evolution for layered decoding algorithms of low-density parity-check codes
• Analysis of Low-Density Parity-Check Codes for the Gilbert–Elliott Channel
• The capacity of low-density parity-check codes under message-passing decoding

Mathematics Subject Classification ID

Channel models (including quantum) in information and communication theory (94A40) Decoding (94B35)

Cited In (3)

• Gallager error-correcting codes for binary asymmetric channels
• An accurate density evolution analysis for a finite-state Markov channel
• Fixed points and stability of density evolution

This page was built for publication: Density Evolution for Asymmetric Memoryless Channels

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3547766)