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
![]()
|
PDF
- Published Version
See Usage Policy. 145Kb | |
![]() |
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: |
| |||||||||
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