DocumentCode :
2885424
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
fYear :
2011
fDate :
28-30 Sept. 2011
Firstpage :
253
Lastpage :
260
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;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Communication, Control, and Computing (Allerton), 2011 49th Annual Allerton Conference on
Conference_Location :
Monticello, IL
Print_ISBN :
978-1-4577-1817-5
Type :
conf
DOI :
10.1109/Allerton.2011.6120176
Filename :
6120176
Link To Document :
بازگشت