Towards Low-Complexity Linear-Programming Decoding
| dc.creator | Vontobel, Pascal O. | |
| dc.creator | Koetter, Ralf | |
| dc.date | 2006-02-26 | |
| dc.date.accessioned | 2026-07-07T08:17:57Z | |
| dc.date.available | 2026-07-07T08:17:57Z | |
| dc.description | 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. | |
| dc.identifier | https://arxiv.org/abs/cs/0602088 | |
| dc.identifier | http://arxiv.org/abs/cs/0602088 | |
| dc.identifier | Proc. 4th Int. Symposium on Turbo Codes and Related Topics, Munich, Germany, April 3-7, 2006 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/134270 | |
| dc.subject | Information Theory | |
| dc.title | Towards Low-Complexity Linear-Programming Decoding | |
| dc.type | text |