In this letter, we investigate the application of the subgradient method to design efficient algorithm for linear programming (LP) decoding of binary linear codes. A major drawback of the original formulation of LP decoding is that the description complexity of the feasible region is exponential in the check node degrees of the code. In order to tackle the problem, we propose a processing technique for LP decoding with the subgradient method, whose complexity is linear in the check node degrees. Consequently, a message-passing type decoding algorithm can be obtained, whose per-iteration complexity is extremely low. Moreover, if the algorithm converges to a valid codeword, it is guaranteed to be a maximum likelihood codeword. Simulation results on several binary linear codes with short lengths suggest that the performances of LP decoding based on the subgradient method and the state-of-art LP decoding implementation approach are comparable.

In this letter, a new method is presented to suppress fractional pseudocodewords by eliminating small instantons of irregular low-density parity-check (LDPC) codes under the linear programming (LP) decoding over the binary symmetric channel (BSC). By appending several new rows found by the integer linear programming formulation to the original parity-check matrix, the optimal distribution spectrum of BSC-instantons in the modified code is obtained. Simulation results show that the proposed method can improve the fractional distance of parity-check matrices and considerably enhance the error-correcting performance of irregular LDPC codes under the LP decoding at the cost of a slightly loss of the original code rate.