CaltechAUTHORS
  A Caltech Library Service

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

Xu, Weiyu and Hassibi, Babak (2007) On the Complexity of Exact Maximum-Likelihood Decoding for Asymptotically Good Low Density Parity Check Codes: A New Perspective. In: 2007 IEEE Information Theory Workshop (ITW '07). IEEE , Piscataway, NJ, pp. 150-155. ISBN 1-4244-1563-2. https://resolver.caltech.edu/CaltechAUTHORS:XUWitw07b

[img]
Preview
PDF - Published Version
See Usage Policy.

145Kb
[img] PDF - Submitted Version
See Usage Policy.

108Kb

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:XUWitw07b

Abstract

The problem of exact maximum-likelihood (ML) decoding of general linear codes is well-known to be NP-hard. In this paper, we show that exact ML decoding of a class of asymptotically good low density parity check codes — expander codes — over binary symmetric channels (BSCs) is possible with an average-case polynomial complexity. This offers a new way of looking at the complexity issue of exact ML decoding for communication systems where the randomness in channel plays a fundamental central role. 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 which achieve error probability exponentially decaying in coding length n while admitting exact ML decoding in average-case polynomial time. As p approaches zero, this rate region approaches the Shannon channel capacity region. Similar results can be extended to AWGN channels, suggesting it may be feasible to eliminate the error floor phenomenon associated with belief-propagation decoding of LDPC codes in the high SNR regime. The derivations are based on a hierarchy of ML certificate decoding algorithms adaptive to the channel realization. In this process, we propose an efficient O(n^2) new ML certificate algorithm based on the max-flow algorithm. Moreover, exact 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 average-case complexities.


Item Type:Book Section
Related URLs:
URLURL TypeDescription
https://doi.org/10.1109/ITW.2007.4313065DOIArticle
https://arxiv.org/abs/cs/0702147arXivDiscussion Paper
Additional Information:© 2006 IEEE. Posted online: 2007-09-24. We thank Professor R.J. McEliece for helpful discussions.
Record Number:CaltechAUTHORS:XUWitw07b
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:XUWitw07b
Official Citation:W. Xu and B. Hassibi, "On the Complexity of Exact Maximum-Likelihood Decoding for Asymptotically Good Low Density Parity Check Codes: A New Perspective," 2007 IEEE Information Theory Workshop, Tahoe City, CA, 2007, pp. 150-155. doi: 10.1109/ITW.2007.4313065
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:9070
Collection:CaltechAUTHORS
Deposited By: Archive Administrator
Deposited On:25 Oct 2007
Last Modified:12 Dec 2019 17:07

Repository Staff Only: item control page