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

Jing Bai, Yongchao Wang, Francis C.M. Lau

Research output: Journal article publicationJournal articleAcademic researchpeer-review

11 Citations (Scopus)


In this letter, we develop an efficient linear programming (LP) decoding algorithm for low-density parity-check (LDPC) codes. The LP relaxation is formulated based on a check-node decomposition approach. Our main contributions are as follows. First, we propose an algorithm based on the alternating direction method of multipliers (ADMM) technique to solve this LP relaxation. By exploiting the orthogonality structure of the LP model, each ADMM update step can be implemented in parallel. Second, the proposed decoding algorithm under this LP formulation eliminates the Euclidean projection on the check polytope compared with the existing ADMM-based LP decoding algorithms. Third, the feasibility analysis of the proposed algorithm is presented. Moveover, complexity analysis shows that our proposed LP decoder in each iteration has a lower complexity than the state-of-the-art ADMM-based LP decoders. Simulation results demonstrate that the proposed LP decoder achieves better performance than other competing ADMM-based LP decoders in terms of decoding time.

Original languageEnglish
Article number8665873
Pages (from-to)1032-1035
Number of pages4
JournalIEEE Wireless Communications Letters
Issue number4
Publication statusPublished - Aug 2019


  • alternating direction method of multipliers (ADMM)
  • Linear programming decoding
  • minimum polytope

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Electrical and Electronic Engineering


Dive into the research topics of 'Minimum-Polytope-Based Linear Programming Decoder for LDPC Codes via ADMM Approach'. Together they form a unique fingerprint.

Cite this