Towards Low-Complexity Linear-Programming Decoding
Conference: TURBO - CODING - 2006 - 4th International Symposium on Turbo Codes & Related Topics; 6th International ITG-Conference on Source and Channel Coding
04/03/2006 - 04/07/2006 at Munich, Germany
Proceedings: TURBO - CODING - 2006
Pages: 9Language: englishTyp: PDF
Personal VDE Members are entitled to a 10% discount on this title
Authors:
Vontobel, Pascal O. (Dept. of EECS, MIT, Cambridge, MA 02139, USA)
Koetter, Ralf (CSL and Dept. of ECE, University of Illinois, Urbana, IL 61801, USA)
Abstract:
We consider linear-programming (LP) decoding of low-density parity-check (LDPC) codes. While it is clear that one can use any general-purpose LP solver to solve the LP that appears in the decoding problem, we argue in this paper that the LP at hand is equipped with a lot of structure that one should take advantage of. Towards this goal, we study the dual LP and show how coordinate-ascent methods lead to very simple update rules that are tightly connected to the min-sum algorithm. Moreover, replacing minima in the formula of the dual LP with soft-minima one obtains update rules that are tightly connected to the sum-product algorithm. This shows that LP solvers with complexity similar to the min-sum algorithm and the sum-product algorithm are feasible. Finally, we also discuss some sub-gradient-based methods.