A simplex algorithm for LP decoding hardware

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.