Linear programming decoding: The ultimate decoding technique for low density parity check codes
DOI:
https://doi.org/10.3103/S0735272713020015Keywords:
LP, ALP, low complexity, decodingAbstract
Linear programming (LP) decoding is an alternative to iterative algorithms for decoding low density parity check (LDPC) codes. Although the practical performance of LP decoding is comparable to message-passing decoding, a significant advantage is its relative amenability to nonasymptotic analysis. Moreover, there turn out to be a number of important theoretical connections between the LP decoding and standard forms of iterative decoding. These connections allow theoretical insight from the LP decoding perspective to be transferred to iterative decoding algorithms. These advantages encouraged many researchers to work in this recent decoding technique for LDPC codes. In this paper, LP decoding for LDPC code is extensively reviewed and is discussed in different segmented areas.
References
GALLAGER, R.G. Low-Density Parity-Check Codes. MIT Press, 1963.
RICHARDSON, T.J.; SHOKROLLAHI, M.A.; URBANKE, R.L. Design of capacity-approaching irregular low-density parity-check codes. IEEE Trans. Inf. Theory, v.47, n.2, p.619-637, 2001.
CHUNG, S.; FORNEY, G. Jr.; RICHARDSON, T.; URBANKE, R. On the design of low-density parity-check codes within 0.0045 dB of the Shannon limit. IEEE Commun. Lett., v.5, n.2, p.58-60, 2001.
TANNER, R.M. A recursive approach to low complexity codes. IEEE Trans. Inf. Theory, v.27, n.5, p.533-547, 1981.
FELDMAN, J. And KARGER, D. Decoding turbo-like codes in polynomial time with provably good error-correcting performing via linear programming. Proc. Conf. Foundations of Computer Science (FOCS), July 2002.
FELDMAN, J.; KARGER, D.R.; WAINWRIGHT, M.J. Linear programming-based decoding of turbo-like codes and its relation to iterative approaches. Proc. 40th Annu. Allerton Conf. Communication, Control, and Computing, Oct. 2002, Monticello, IL, 2002.
FELDMAN, J.; WAINWRIGHT, M.J.; KARGER, D.R. Using linear programming to decode binary linear codes. IEEE Trans. Inf. Theory, v.51, n.3, p.954-972, 2005.
FELDMAN, J.; MALKIN, T.; SERVEDIO, R.A.; STEIN, C.; WAINWRIGHT, M.J. LP decoding corrects a constant fraction of errors. IEEE Trans. Inf. Theory, v.53, n.1, p.82-89, 2007.
TANATMIS, A.; RUZIKA, S.; HAMACHER, H.W.; PUNEKAR, M.; KIENLE F.; WEHN, N. A separation algorithm for improved LP-decoding of linear block codes. IEEE Trans. Inf. Theory, v.51, n.3, p.3277-3289, 2010.
CHERTKOV, M. AND STEPANOV, M.G. An efficient pseudocodeword search algorithm for linear programming decoding of LDPC codes. IEEE Trans. Inf. Theory, v.54, n.4, p.1514-1520, 2008.
SASON, I. Linear programming bounds on the degree distributions of LDPC code ensembles. ISIT, June 28-July 3, 2009, Seoul, Korea, 2009.
DASKALAKIS, C.; DIMAKIS, A.G.; KARP, R.M.; WAINWRIGHT, M.J. Probabilistic analysis of linear programming decoding. IEEE Trans. Inf. Theory, v.54, n.8, p.3565-3578, 2008.
DASKALAKIS, C.; DIMAKIS, A.G.; KARP, R.M.; WAINWRIGHT, M.J. Probabilistic analysis of linear programming decoding. Forty-Fourth Annual Allerton Conference Allerton House, Sept 27–29, 2006, UIUC, Illinois, USA, 2006.
ARORA, S.; DASKALAKIS, C.; STEURER, D. Message passing algorithms and improved LP decoding. STOC’09, 2009, p.3-12.
HALABI, N. AND EVEN, G. LP decoding of regular LDPC codes in memoryless channels. IEEE Trans. Inf. Theory, v.57, n.2, p.887-897, 2011.
HALABI, N. AND EVEN, G. LP decoding of regular LDPC codes in memoryless channels. ISIT 2010, June 13–18, 2010, Austin, Texas, USA, 2010.
FLANAGAN, M.F.; SKACHEK, V.; BYRNE, E.; GREFERATH, M. Linear-programming decoding of nonbinary linear codes. IEEE Trans. Inf. Theory, v.55, n.9, p.4134-4154, 2009.
TAGHAVI, M.H.N. AND SIEGEL, P.H. Adaptive linear programming decoding. Proc. Int. Symp. Inform. Theory, July 2006, Seattle, USA, 2006, p.1374-1378.
TAGHAVI, M.H.N. AND SIEGEL, P.H. Adaptive linear programming decoding. IEEE Trans. Inf. Theory, v.54, n.12, p.5396-5410, 2008.
TAGHAVI, M.H.N. AND SIEGEL, P.H. Efficient implementation of linear programming decoding. Forty-Sixth Annual Allerton Conference Allerton House, September 23–26, 2008, UIUC, Illinois, USA, 2008.
TAGHAVI, M.H.N.; SHOKROLLAHI, A.; SIEGEL, P.H. Efficient implementation of linear programming decoding. http://arxiv.org/abs/0902.0657v1, 4 February 2009.
DRAPER, S.C.; YEDIDIA, J.S.; WANG, Y. ML decoding via mixed integer adaptive linear programming decoding. Int. Symp. Inform. Theory, July 2007, Nice, France, 2007.
DRAPER, S.C. AND YEDIDIA, J.S. Complexity scaling of mixed-integer linear programming decoding. UCSD Workshop Inform. Theory Apps., January 2008, San Diego, 2008.
GNU linear programming kit. http://www.gnu.org/software/glpk.
YANG, K.; FELDMAN, J.; WANG, X. Nonlinear programming approaches to decoding low-density parity-check codes. IEEE J. Select. Areas Commun., v.24, p.1603-1613, 2006.
WANG, Y.; YEDIDIA, J.S.; DRAPER, S.C. Multi-stage Decoding of LDPC Codes. Int. Symp. Inform. Theory, June 28–July 3, 2009, Seoul, Korea, 2009.
VONTOBEL, P.O. AND KOETTER, R. Towards low-complexity linear programming decoding. Proc. 4th Int. Symp. on Turbo Codes and Related Topics, April 2006, Munich, Germany, 2006, arxiv:cs/0602088v1.
VONTOBEL, P.O. AND KOETTER, R. On low-complexity linear-programming decoding of LDPC codes. European Trans. Telecom., v.18, n.5, p.509-517, 2007.
YANG, K.; WANG, X.; FELDMAN, J. A new linear programming approach to decoding linear block codes. IEEE Trans. Inf. Theory, v.54, n.3, p.1061-1072, 2008.
BURSHTEIN, D. AND GOLDENBERG, I. Improved linear programming decoding and bounds on the minimum distance of LDPC codes. IEEE Inf. Theory Workshop (ITW 2010), Dublin, 2010.
PUNEKAR, M. AND FLANAGAN, M.F. Low complexity linear programming decoding of nonbinary linear codes. Forty-Eighth Annual Allerton Conference Allerton House, September 29–October 1, 2010, UIUC, Illinois, USA, 2010.
PUNEKAR, M. AND FLANAGAN, M.F. Low complexity linear programming decoding of nonbinary linear codes. arXiv:1007.1368v2 [cs.IT], 4 Oct. 2010.
VONTOBEL, P.O. AND KOETTER, R. On the relationship between linear programming decoding and min-sum algorithm decoding. IEEE Int. Symp. Inf. Theory Applications, Oct. 2004, p.991-996.
VONTOBEL, P.O. AND KOETTER, R. Graph-cover decoding and finite-length analysis of message-passing iterative decoding of LDPC codes. To be published.
KARMARKAR, N. A new polynomial-time algorithm for linear programming. Combinatorica, v.4, n.4, p.373-395, 1984.
BERTSIMAS, D. AND TSITSIKLIS, J.N. Introduction to linear optimization. Athena Scientific, 1997.
WADAYAMA, T. Interior point decoding for linear vector channels based on convex optimization. IEEE Trans. Inform. Theory, v.56, n.10, p.4905-4921, 2010.
WADAYAMA, T. An LP decoding algorithm based on primal path following interior point method. IEEE Int. Symp. Inf. Theory, June 2009, Seoul, Korea, 2009, p.389-393.
VONTOBEL, P. Interior-point algorithms for linear-programming decoding. 3rd Annual Workshop on Inf. Theory and Its Appl., February 2008, San Diego, CA, 2008.
NGATCHED, T.M.N.; ALFA, A.S.; CAI, J. Hybrid linear programming based decoding of finite-geometries LDPC codes. IEEE Trans. Commun., to appear.
BURSHTEIN, D. Iteartive approximate linear programming decoding of LDPC codes with linear complexity. ISIT, July 6–11, 2008, Toronto, Canada, 2008.
BURSHTEIN, D. Iteartive approximate linear programming decoding of LDPC codes with linear complexity. IEEE Trans. Inf. Theory, v.55, n.11, p.4835-4859, 2009.
BURSHTEIN, D. Approximate iterative LP decoding of LDPC codes over GF(q) in linear complexity. IEEE 26th Convention of Electrical and Electronics Engineers, Israel, 2010.
DONOHO, D. High-dimensional centrally symmetric polytopes with neighborliness proportional to dimension. Discrete and Computational Geometry, v.102, n.27, p.617-652, 2006.
DONOHO, D. AND TANNER, J. Neighborlyness of randomly-projected simplices in high dimensions. Proc. National Academy of Sciences, v.102, n.27, p.9452-9457, 2005.
DONOHO D.L. AND HUO, X. Uncertainty principles and ideal atomic decomposition. IEEE Trans. Inf. Theory, v.47, n.7, p.2845-2862, 2001.
STOJNIC, M.; XU, W.; HASSIBI, B. Compressed sensing — probabilistic analysis of a null-space characterization. IEEE Int. Conf. on Acoustic, Speech and Signal Processing, ICASSP 2008.
COHEN, A.; DAHMEN, W.; DEVORE, R. Compressed sensing and best k-term approximation. Journal of the American Mathematical Society, v.22, n.1, p.211-231, 2009.
XU, W. AND HASSIB, B. On sharp performance bounds for robust sparse signal recoveries. Int. Symp. on Inf. Theory, 2009.
DIMAKIS, A.G. AND VONTOBEL, P.O. LP decoding meets LP decoding: A connection between channel coding and compressed sensing. Allerton, 2009.
DIMAKIS, A.G.; SMARANDACHE, R.; VONTOBEL, P.O. LDPC codes for compressed sensing. arxiv 1012.0602.
KHAJEHNEJAD, A.; DIMAKISY, A.G.; HASSIBI, B.; BRADLEY, W. Reweighted LP decoding for LDPC codes. Forty-Eighth Annual Allerton Conference Allerton House, UIUC, September 29–October 1, 2010, Illinois, USA, 2010.
KHAJEHNEJAD, A.; DIMAKISY, A.G.; HASSIBI, B.; VIGODA, B.; BRADLEY, W. Reweighted LP decoding for LDPC codes. arXiv:1103.2837v1 [cs.IT], 15 Mar. 2011.
KHAJEHNEJAD, A.; XU, W.; AVESTIMEHR, S.; HASSIBI, B. Improved sparse recovery thresholds with two-step reweighted minimization. ISIT, 2010.
KURKOSKI, B.M.; SIEGEL, P.H.; WOLF, J.K. Joint message-passing decoding of LDPC codes and partial-response channels. IEEE Trans. Inform. Theory, v.48, n.6, p.1410-1422, 2002.
KIM, B.-H. AND PFISTER, H.D. On the joint decoding of LDPC codes and finite-state channels via linear programming. IEEE Int. Symp. Inf. Theory, June 2010, Austin, TX, 2010, p.754-758.
KIM, B.-H. AND PFISTER, H.D. Joint decoding of LDPC codes and finite-state channels via linear-programming. Submitted to IEEE J. Select. Topics in Signal Processing, http://arxiv.org/abs/1102.1480, Jan. 2011.
KIM, B.-H. AND PFISTER, H.D. An iterative joint linear-programming decoding of LDPC codes and finite-state channels. IEEE Int. Conf. Commun., http://arxiv.org/abs/1009.4352, June 2011.
FLANAGAN, M.F. A unified framework for linear-programming based communication receivers. http://arxiv.org/abs/0902.0892, Feb. 2009.
