On low‐complexity linear‐programming decoding of LDPC codes
Pascal O. Vontobel, R. Koetter · European Transactions on Telecommunications · 2007
Abstract We consider linear‐programming (LP) decoding of low‐density parity‐check (LDPC) codes. While 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 can be exploited. 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. Copyright © 2007 John Wiley & Sons, Ltd.