Reduced-Complexity Linear Programming Decoding Based on ADMM for LDPC Codes
Authors:
- 31 March 2015
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Communications Letters
- Vol. 19 (6) , 909-912
Abstract
The Euclidean projection onto check polytopes is the most time-consuming operation in the linear programming (LP) decoding based on alternating direction method of multipliers (ADMM) for low-density parity-check (LDPC) codes. In this letter, instead of reducing the complexity of Euclidean projection itself, we propose a new method to reduce the decoding complexity of ADMM-based LP decoder by decreasing the number of Euclidean projections. In particular, if all absolute values of the element-wise differences between the input vector of Euclidean projection in the current iteration and that in the previous iteration are less than a predefined value, then the Euclidean projection at the current iteration will be no longer performed. Simulation results show that the proposed decoder can still save roughly 20% decoding time even if both the over-relaxation and early termination techniques are used.Keywords
Funding Information
- National Natural Science Foundation of China (61471286, 61271004)
- Fundamental Research Funds for the Central Universities
This publication has 6 references indexed in Scilit:
- Large Scale LP Decoding with Low ComplexityIEEE Communications Letters, 2013
- Decomposition Methods for Large Scale LP DecodingIEEE Transactions on Information Theory, 2013
- Efficient iterative LP decoding of LDPC codes with alternating direction method of multipliers2013
- Adaptive Cut Generation Algorithm for Improved Linear Programming Decoding of Binary Linear CodesIEEE Transactions on Information Theory, 2012
- Distributed Optimization and Statistical Learning via the Alternating Direction Method of MultipliersFoundations and Trends in Machine Learning, 2011
- Using Linear Programming to Decode Binary Linear CodesIEEE Transactions on Information Theory, 2005