Multistep Linear Programming Approaches for Decoding Low-Density Parity-Check Codes

The problem of improving the performance of linear programming (LP) decoding of low-density parity-check (LDPC) codes is considered in this paper. A multistep linear programming (MLP) algorithm was developed for decoding LDPC codes that includes a slight increase in computational complexity. The MLP decoder adaptively adds new constraints which are compatible with a selected check node to refine the results when an error is reported by the original LP decoder. The MLP decoder result is shown to have the maximum-likelihood (ML) certificate property. Simulations with moderate block length LDPC codes suggest that the MLP decoder gives better performance than both the original LP decoder and the conventional sum-product (SP) decoder.