Large scale LP decoding with low complexity

Publication Type:
Journal Article
IEEE Communications Letters, 2013, 17 (11), pp. 2152 - 2155
Issue Date:
Filename Description Size
06636134.pdfPublished Version188.62 kB
Adobe PDF
Full metadata record
Linear program (LP) decoding has become increasingly popular for error-correcting codes due to its simplicity and promising performance. Low-complexity and efficient iterative algorithms for LP decoding are of great importance for practical applications. In this paper we focus on solving the binary LP decoding problem by using the alternating direction method of multipliers (ADMM). Our main contribution is that we propose a linear-complexity algorithm for the projection onto a parity polytope (having a computational complexity of O(d), where d is the check-node degree), as compared to recent work [1], which has a computational complexity of O(d log d). In particular, we show that the projection onto the parity polytope can be transformed to a projection onto a simplex. © 1997-2012 IEEE.
Please use this identifier to cite or link to this item: