The alternating direction method of multipliers has recently been adapted for linear programming decoding of low-density parity-check codes. The computation of the projection onto the parity polytope is the core of this algorithm and usually involves a sorting operation, which is the main effort of the projection. In this paper, we present an algorithm with low complexity to compute this projection. The algorithm relies on new findings in the recursive structure of the parity polytope and iteratively fixes selected components. As shown in our realistic simulation setup, it requires up to 37% less arithmetical operations compared with state-of-the-art projections. Additionally, it does not involve a sorting operation, which is needed in all exact state-of-the-art projection algorithms. These two benefits make it appealing for efficient hardware and software implementations.

An efficient LP decoder is the key building block for a maximum likelihood decoder based on integer programming. In this paper we propose to employ a variant of the simplex algorithm for LP decoding, called the dual simplex algorithm. This algorithm has two advantages: It inherently uses the received LLRs to generate a close to optimum starting solution and it allows to reuse former LP solutions if an adaptive LP decoding scheme is used. It is shown, that the dual simplex algorithm outperforms the standard (primal) simplex by a factor of 15-20 in runtime. This allows for efficient future hardware implementations. Furthermore the use of fixed-point instead of floating-point numbers is investigated to further reduce hardware complexity.