Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published December 2013 | public
Journal Article

Decomposition Methods for Large Scale LP Decoding

Abstract

When binary linear error-correcting codes are used over symmetric channels, a relaxed version of the maximum likelihood decoding problem can be stated as a linear program (LP). This LP decoder can be used to decode error-correcting codes at bit-error-rates comparable to state-of-the-art belief propagation (BP) decoders, but with significantly stronger theoretical guarantees. However, LP decoding when implemented with standard LP solvers does not easily scale to the block lengths of modern error correcting codes. In this paper, we draw on decomposition methods from optimization theory, specifically the alternating direction method of multipliers (ADMM), to develop efficient distributed algorithms for LP decoding. The key enabling technical result is a "two-slice" characterization of the parity polytope, the polytope formed by taking the convex hull of all codewords of the single parity check code. This new characterization simplifies the representation of points in the polytope. Using this simplification, we develop an efficient algorithm for Euclidean norm projection onto the parity polytope. This projection is required by the ADMM decoder and its solution allows us to use LP decoding, with all its theoretical guarantees, to decode large-scale error correcting codes efficiently. We present numerical results for LDPC codes of lengths more than 1000. The waterfall region of LP decoding is seen to initiate at a slightly higher SNR than for sum-product BP, however an error floor is not observed for LP decoding, which is not the case for BP. Our implementation of LP decoding using the ADMM executes as fast as our baseline sum-product BP decoder, is fully parallelizable, and can be seen to implement a type of message-passing with a particularly simple schedule.

Additional Information

© 2013 IEEE. Manuscript received April 11, 2012; revised February 25, 2013; accepted April 29, 2013. Date of publication September 10, 2013; date of current version November 19, 2013. This work was supported in part by the National Science Foundation under Grants CCF-1217058 and CCF-1148243 and in part by the Office of Naval Research under Award N00014-13-1-0129. The work in this paper was performed while the authors were affiliated with the University of Wisconsin, Madison. This paper was presented in part at the Allerton Conference on Communication, Control, and Computing, Monticello, IL, USA, 2011. The authors would like to thank M. Anderson, B. Butler, E. Bach, A. Dimakis, P. Siegel, E. Telatar, Y. Wang, J. Yedidia, and D. Zelený for useful discussions and references. The authors would also like to note that some of the simulation results presented herein would not have been possible without the resources and the computing assistance of the University of Wisconsin (UW), Madison, Center For High Throughput Computing (CHTC) in the Department of Computer Sciences. The CHTC is supported by UW-Madison and the Wisconsin Alumni Research Foundation, and is an active member of the Open Science Grid, which is supported by the National Science Foundation and the U.S. Department of Energy's Office of Science.

Additional details

Created:
August 22, 2023
Modified:
October 25, 2023