Title :
Decomposition methods for large scale LP decoding
Author :
Barman, Siddharth ; Liu, Xishuo ; Draper, Stark ; Recht, Benjamin
Author_Institution :
Dept. of Comput. Sci., Univ. of Wisconsin - Madison, Madison, WI, USA
Abstract :
Feldman et al. (IEEE Trans. Inform. Theory, Mar. 2005) showed that linear programming (LP) can be used to decode linear error correcting codes. The bit-error-rate performance of LP decoding is comparable to state-of-the-art BP decoders, but has 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 to develop efficient distributed algorithms for LP decoding. The key enabling technical result is a nearly linear time algorithm for two-norm projection onto the parity polytope. This allows us to use LP decoding, with all its theoretical guarantees, to decode large-scale error correcting codes efficiently.
Keywords :
decoding; error correction codes; error statistics; linear codes; linear programming; bit error rate performance; block lengths; decomposition methods; distributed algorithms; large-scale LP decoding; linear error correcting codes; linear programming; linear time algorithm; optimization theory; parity polytope; state-of-the-art BP decoders; two-norm projection; Algorithm design and analysis; Iterative decoding; Maximum likelihood decoding; Projection algorithms; Vectors;
Conference_Titel :
Communication, Control, and Computing (Allerton), 2011 49th Annual Allerton Conference on
Conference_Location :
Monticello, IL
Print_ISBN :
978-1-4577-1817-5
DOI :
10.1109/Allerton.2011.6120176