SCIENCE@home

Capacity-Achieving Codes with Bounded Graphical Complexity on Noisy Channels

Chun-Hao Hsu,A. Anastasopoulos

Published 2005 in arXiv.org

ABSTRACT

We introduce a new family of concatenated codes with an outer low-density parity-check (LDPC) code and an inner low-density generator matrix (LDGM) code, and prove that these codes can achieve capacity under any memoryless binary-input output-symmetric (MBIOS) channel using maximum-likelihood (ML) decoding with bounded graphical complexity, i.e., the number of edges per information bit in their graphical representation is bounded. In particular, we also show that these codes can achieve capacity on the binary erasure channel (BEC) under belief propagation (BP) decoding with bounded decoding complexity per information bit per iteration for all erasure probabilities in (0, 1). By deriving and analyzing the average weight distribution (AWD) and the corresponding asymptotic growth rate of these codes with a rate-1 inner LDGM code, we also show that these codes achieve the Gilbert-Varshamov bound with asymptotically high probability. This result can be attributed to the presence of the inner rate-1 LDGM code, which is demonstrated to help eliminate high weight codewords in the LDPC code while maintaining a vanishingly small amount of low weight codewords.

PUBLICATION RECORD

  • Publication year

    2005

  • Venue

    arXiv.org

  • Publication date

    2005-09-01

  • Fields of study

    Mathematics, Physics, Computer Science

  • Identifiers
    arXiv cs/0509062
  • External record

    Open on Semantic Scholar

  • Source metadata

    Semantic Scholar

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-17 of 17 references · Page 1 of 1

CITED BY

Showing 1-30 of 30 citing papers · Page 1 of 1