ADMM versus simplex algorithm for LP decoding
Florian Gensheimer, Stefan Ruzika, Stefan Scholl, Norbert Wehn · 2016
In this paper, we investigate the complexity of different algorithms for LP decoding for short BCH and LDPC codes. Two approaches have gained particular interest: The simplex algorithm and the alternating direction method of multipliers (ADMM). For the adaptive LP decoding algorithm, we propose a special implementation of the dual simplex algorithm that uses the same simplex tableau in every linear program of the adaptive scheme. We compare this algorithm with another variant of the adaptive decoder and two variants of the recently proposed ADMM regarding the required arithmetic operations. These are important measures for design decisions for future hardware implementations.