On the Complexity of Exact Maximum-Likelihood Decoding for Asymptotically Good Low Density Parity Check Codes

Details On the Complexity of Exact Maximum-Likelihood Decoding for Asymptotically Good Low Density Parity Check Codes On the Complexity of Exact Maximum-Likelihood Decoding for Asymptotically Good Low Density Parity Check Codes

2007-02-25

arxiv.org/abs/cs/0702147v1

Computer Science

Information Theory

an attempt at exploring the communication complexity limit,5 pages,submitted to 2007 IEEE International Symposium on Informati

Scientific paper

Since the classical work of Berlekamp, McEliece and van Tilborg, it is well known that the problem of exact maximum-likelihood (ML) decoding of general linear codes is NP-hard. In this paper, we show that exact ML decoding of a classs of asymptotically good error correcting codes--expander codes, a special case of low density parity check (LDPC) codes--over binary symmetric channels (BSCs) is possible with an expected polynomial complexity. More precisely, for any bit-flipping probability, $p$, in a nontrivial range, there exists a rate region of non-zero support and a family of asymptotically good codes, whose error probability decays exponentially in coding length $n$, for which ML decoding is feasible in expected polynomial time. Furthermore, as $p$ approaches zero, this rate region approaches the channel capacity region. The result is based on the existence of polynomial-time suboptimal decoding algorithms that provide an ML certificate and the ability to compute the probability that the suboptimal decoder yields the ML solution. One such ML certificate decoder is the LP decoder of Feldman; we also propose a more efficient $O(n^2)$ algorithm based on the work of Sipser and Spielman and the Ford-Fulkerson algorithm. The results can be extended to AWGN channels and suggest that it may be feasible to eliminate the error floor phenomenon associated with message-passage decoding of LDPC codes in the high SNR regime. Finally, we observe that the argument of Berlekamp, McEliece and van Tilborg can be used to show that ML decoding of the considered class of codes constructed from LDPC codes with regular left degree, of which the considered expander codes are a special case, remains NP-hard; thus giving an interesting contrast between the worst-case and expected complexities.

Affiliated with

Also associated with

No associations

Rating

On the Complexity of Exact Maximum-Likelihood Decoding for Asymptotically Good Low Density Parity Check Codes 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 On the Complexity of Exact Maximum-Likelihood Decoding for Asymptotically Good Low Density Parity Check Codes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Complexity of Exact Maximum-Likelihood Decoding for Asymptotically Good Low Density Parity Check Codes will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-460375