Computer Science – Information Theory
Scientific paper
2005-09-19
Computer Science
Information Theory
17 pages, 2 figures. This paper is to be presented in the 43rd Annual Allerton Conference on Communication, Control and Comput
Scientific paper
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.
Anastasopoulos Achilleas
Hsu Chun-Hao
No associations
LandOfFree
Capacity-Achieving Codes with Bounded Graphical Complexity on Noisy Channels does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Capacity-Achieving Codes with Bounded Graphical Complexity on Noisy Channels, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Capacity-Achieving Codes with Bounded Graphical Complexity on Noisy Channels will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-1382