Tradeoff between decoding complexity and rate for codes on graphs

We consider transmission over a general memoryless channel, with bounded decoding complexity per bit under message passing decoding. We show that the achievable rate is bounded below capacity if there is a finite success in the decoding in a specified number of operations per bit at the decoder for some codes on graphs. These codes include LDPC and LDGM codes. Good performance with low decoding complexity suggests strong local structures in the graphs of these codes, which are detrimental to the code rate asymptotically. The proof method leads to an interesting necessary condition on the code structures which could achieve capacity with bounded decoding complexity. We also show that if a code sequence achieves a rate epsilon close to the channel capacity, the decoding complexity scales at least as O(log(1/epsilon).

• Publication year

  2007

• Venue

  arXiv.org

• Publication date

  2007-02-12

• Fields of study

  Mathematics, Computer Science

• Identifiers
  arXiv cs/0702073
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Capacity-Achieving Codes with Bounded Graphical Complexity on Noisy Channels

  2005cited by this paper
• Accumulate-Repeat-Accumulate Codes: Systematic Codes Achieving the Binary Erasure Channel Capacity with Bounded Complexity

  2005cited by this paper
• Raptor codes on symmetric channels

  2004influential reference
• Capacity-achieving ensembles for the binary erasure channel with bounded complexity

  2004cited by this paper
• Parity-check density versus performance of binary linear block codes over memoryless symmetric channels

  2003cited by this paper
• Graph-based codes and iterative decoding

  2003cited by this paper
• The capacity of low-density parity-check codes under message-passing decoding

  2001cited by this paper
• Capacity-achieving sequences

  2001cited by this paper
• On the complexity of reliable communication on the erasure channel

  2001cited by this paper
• Submitted To Ieee Transactions On Information Theory.

  year unknowncited by this paper

• No citing papers are available for this paper.