An Iterative Check Polytope Projection Algorithm for ADMM-Based LP Decoding of LDPC Codes

被引：43

作者：

Wei, Haoyuan ^{[1
]}

Banihashemi, Amir H. ^{[1
]}

机构：

[1] Carleton Univ, Dept Syst & Comp Engn, Ottawa, ON K1S 5B6, Canada

来源：

IEEE COMMUNICATIONS LETTERS | 2018年 / 22卷 / 01期

关键词：

Alternating direction method of multipliers (ADMM); low-density parity-check (LDPC) codes; linear-programming (LP) decoding of LDPC codes; Euclidean projection; check polytope projection; COMPLEXITY;

D O I：

10.1109/LCOMM.2017.2766223

中图分类号：

TN [电子技术、通信技术];

学科分类号：

0809 ;

摘要：

Alternating direction method of multipliers (ADMM) is a popular technique for linear-programming decoding of low-density parity-check codes. The computational complexity of ADMM is dominated by the Euclidean projection of a real-valued vector onto a parity-check polytope. Existing algorithms for such a projection all require sorting operations, which happen to be the most complex part of the projection. In this letter, we propose an iterative algorithm, without sorting operation, for projection onto the parity-check polytope. The proposed algorithm has a worst case complexity linear in the input dimension compared with the super-linear complexity of existing algorithms.

引用

页码：29 / 32

页数：4

共 14 条

[1]

[Anonymous], FOUND TRENDS MACH LE

[2]

[Anonymous], 2005, C80216E050066R3 IEEE

[3] Decomposition Methods for Large Scale LP Decoding [J].

Barman, Siddharth ;

Liu, Xishuo ;

Draper, Stark C. ;

Recht, Benjamin .

IEEE TRANSACTIONS ON INFORMATION THEORY, 2013, 59 (12) :7870-7886

[4]

Debbabi I, 2016, INT CONF ACOUST SPEE, P971, DOI 10.1109/ICASSP.2016.7471820

[5] Fast Converging ADMM-Penalized Algorithm for LDPC Decoding [J].

Debbabi, Imen ;

Le Gal, Bertrand ;

Khouja, Nadia ;

Tlili, Fethi ;

Jego, Christophe .

IEEE COMMUNICATIONS LETTERS, 2016, 20 (04) :648-651

[6] Using linear programming to decode binary linear codes [J].

Feldman, J ;

Wainwright, MJ ;

Karger, DR .

IEEE TRANSACTIONS ON INFORMATION THEORY, 2005, 51 (03) :954-972

[7] Efficient ADMM Decoding of LDPC Codes Using Lookup Tables [J].

Jiao, Xiaopeng ;

Mu, Jianjun ;

He, Yu-Cheng ;

Chen, Chao .

IEEE TRANSACTIONS ON COMMUNICATIONS, 2017, 65 (04) :1425-1437

[8] Reduced Complexity Node-Wise Scheduling of ADMM Decoding for LDPC Codes [J].

Jiao, Xiaopeng ;

Mu, Jianjun ;

Wei, Haoyuan .

IEEE COMMUNICATIONS LETTERS, 2017, 21 (03) :472-475

[9] The ADMM Penalized Decoder for LDPC Codes [J].

Liu, Xishuo ;

Draper, Stark C. .

IEEE TRANSACTIONS ON INFORMATION THEORY, 2016, 62 (06) :2966-2984

[10]

Wasson M, 2015, 2015 49TH ASILOMAR CONFERENCE ON SIGNALS, SYSTEMS AND COMPUTERS, P1015, DOI 10.1109/ACSSC.2015.7421292

← 1 2 →