Minimum-Polytope-Based Linear Programming Decoder for LDPC Codes via ADMM Approach

In this letter, we develop an efficient linear programming (LP) decoding algorithm for low-density parity-check (LDPC) codes. We first relax the maximum likelihood (ML) decoding problem to a LP problem by using check-node decomposition. Then, to solve the resulting LP problem, we propose an efficient iterative algorithm based on the alternating direction method of multipliers (ADMM) technique. In addition, the feasibility analysis of the proposed algorithm is presented. Furthermore, through exploiting the sparsity and orthogonality structures of the LP problem, the computational complexity of the proposed decoding algorithm increases linearly with the length of the LDPC code. Simulation results demonstrate that our proposed algorithm achieves better performance than other competing algorithms in terms of decoding time.