Capacity-Achieving Codes With Bounded Graphical Complexity and Maximum Likelihood Decoding

• Published in: IEEE transactions on information theory 2010-03, Vol.56 (3), p.992-1006
• Main Authors: Chun-Hao Hsu, Anastasopoulos, A.
• Format: Article
• Language: English
• Subjects: Additive white noise; Applied sciences; Asymptotic growth rate; average weight distribution; Belief propagation; Bipartite graph; capacity-achieving codes; Codes; Coding, codes; Communication system control; Concatenated codes; Data encryption; density evolution; Exact sciences and technology; Gilbert-Varshamov bound; Graphs; Information theory; Information, signal and communications theory; irregular repeat-accumulate codes; Iterative algorithms; Iterative decoding; low-density generator matrix codes; low-density parity-check (LDPC) codes; Maximum likelihood decoding; Maximum likelihood method; Message passing; Normal distribution; Parity check codes; Signal and communications theory; Telecommunications and information theory
• ISSN: 0018-9448; 1557-9654
• DOI: 10.1109/TIT.2009.2039084

In this paper, the existence of capacity-achieving codes for memoryless binary-input output-symmetric (MBIOS) channels under maximum-likelihood (ML) decoding with bounded graphical complexity is investigated. Graphical complexity of a code is defined as the number of edges in the graphical representation of the code per information bit and is proportional to the decoding complexity per information bit per iteration under iterative decoding. Irregular repeat-accumulate (IRA) codes are studied first. Utilizing the asymptotic average weight distribution (AAWD) of these codes and invoking Divsalar's bound on the binary-input additive white Gaussian noise (BIAWGN) channel, it is shown that simple nonsystematic IRA ensembles outperform systematic IRA and regular low-density parity-check (LDPC) ensembles with the same graphical complexity, and are at most 0.124 dB away from the Shannon limit. However, a conclusive result as to whether these nonsystematic IRA codes can really achieve capacity cannot be reached. Motivated by this inconclusive result, a new family of codes is proposed, called low-density parity-check and generator matrix (LDPC-GM) codes, which are serially concatenated codes with an outer LDPC code and an inner low-density generator matrix (LDGM) code. It is shown that these codes can achieve capacity on any MBIOS channel using ML decoding and also achieve capacity on any BEC using belief propagation (BP) decoding, both with bounded graphical complexity. Moreover, it is shown that, under certain conditions, these capacity-achieving codes have linearly increasing minimum distances and achieve the asymptotic Gilbert-Varshamov bound for all rates.