A Fast Iterative Check Polytope Projection Algorithm for ADMM Decoding of LDPC Codes by Bisection Method

Yan LIN  Qiaoqiao XIA  Wenwu HE  Qinglin ZHANG  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E102-A   No.10   pp.1406-1410
Publication Date: 2019/10/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E102.A.1406
Type of Manuscript: LETTER
Category: Information Theory
alternating direction method of multipliers,  low-density parity-check codes,  check polytope projection,  bisection method iterative algorithm,  

Full Text: FreePDF(443.3KB)

Using linear programming (LP) decoding based on alternating direction method of multipliers (ADMM) for low-density parity-check (LDPC) codes shows lower complexity than the original LP decoding. However, the development of the ADMM-LP decoding algorithm could still be limited by the computational complexity of Euclidean projections onto parity check polytope. In this paper, we proposed a bisection method iterative algorithm (BMIA) for projection onto parity check polytope avoiding sorting operation and the complexity is linear. In addition, the convergence of the proposed algorithm is more than three times as fast as the existing algorithm, which can even be 10 times in the case of high input dimension.