Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Allerton Conference on Communication, Control, and Computing

Efficient implementation of linear programming decoding

Mohammad Hossein Taghavi, Amin Shokrollahi, Paul H. Siegel

Published Sep 1, 2008• 13 citations
Publisher

Abstract

This paper explores ideas for fast linear programming (LP) decoding of low-density parity-check (LDPC) codes. We first propose a modification of adaptive LP decoding, and prove that it performs LP decoding by solving a number of linear programs that contain at most one linear constraint derived from each of the parity-check constraints. Then, as a step toward designing an efficient LP solver that exploits the structure of LDPC codes, we study a sparse interior-point implementation for solving this sequence of linear programs. Since the most complex part of each iteration of the interior-point algorithms is to solve a (usually ill-conditioned) system of linear equations for finding the step direction, we propose a framework for designing preconditioners to be used with the iterative methods for solving these systems. The effectiveness of the proposed approach is demonstrated via both analytical and simulation results.

DOI
10.1109/allerton.2008.4797586

Related papers

Efficient Implementation of Linear Programming Decoding

Mohammad Hossein Taghavi, Amin Shokrollahi, Paul H. Siegel

While linear programming (LP) decoding provides more flexibility for finite-length performance analysis than iterative message-passing (IMP) decoding, it is computationally more complex to implement in its original form, due to both the large size of the relaxed LP problem and the inefficiency of using general-purpose LP solvers. This paper explores ideas for fast LP decoding of low-density parity-check (LDPC) codes. By modifying the previously reported Adaptive LP decoding scheme to allow removal of unnecessary constraints, we first prove that LP decoding can be performed by solving a number of LP problems that each contains at most one linear constraint derived from each of the parity-check constraints. By exploiting this property, we study a sparse interior-point implementation for solving this sequence of linear programs. Since the most complex part of each iteration of the interior-point algorithm is the solution of a (usually ill-conditioned) system of linear equations for finding the step direction, we propose a preconditioning algorithm to facilitate solving such systems iteratively. The proposed preconditioning algorithm is similar to the encoding procedure of LDPC codes, and we demonstrate its effectiveness via both analytical methods and computer simulation results.

arXiv:0902.0657•IEEE Transactions on Information Theory•Sep 1, 2011•45 citations

Efficient Implementation of Interior Point Decoding Based on Barrier Function for LDPC Codes

Telex M. N. Ngatched, Attahiru Sule Alfa, Jun Cai

In this paper, an efficient implementation of the interior point algorithm recently proposed by Wadayama for linear programming (LP) decoding of low-density parity-check (LDPC) codes is presented. The main idea behind the modification is to approximate the barrier function for the fundamental polytope defining the code so that it contains only one linear constraint for each of the parity-check constraints. Simulation results show that the approximations introduced do not result in any performance degradation, while considerably reducing the decoding complexity and latency.

IEEE Wireless Communications and Networking Conference•Apr 1, 2010•0 citations

Hybrid Linear Programming Based Decoding Algorithm for LDPC Codes

Telex M. N. Ngatched, Attahiru Sule Alfa, Jun Cai

This paper presents a hybrid decoding algorithm for low-density parity-check (LDPC) codes based on the interior point method with barrier function for linear programming (LP) decoding introduced by Wadayama . First, an efficient implementation of Wadayama's algorithm is presented. The main idea behind the modification is to approximate the barrier function for the fundamental polytope defining the code so that it contains only one linear constraint for each of the parity-check constraints. A two-stage hybrid decoding which combines the interior point decoding and a low-complexity decoding algorithm for LDPC codes is then proposed. Simulation results show that the approximations introduced in the proposed algorithms do not result in any performance degradation, while considerably reducing the decoding complexity and latency.

IEEE Transactions on Communications•Jan 21, 2011•3 citations

Infeasible primal-dual interior-point algorithm for linear-programming decoding of LDPC codes

Xuye Wang, Piming Ma

The linear programming (LP) decoding of Low-Density Parity-Check (LDPC) codes is widely concerned for its maximum likelihood (ML) features. It is that the ML decoding rule for LDPC codes can be relaxed to LP optimization problem. Therefore, this paper focus on an efficient algorithm called infeasible primal-dual interior-point (IPDIP) to solve the LP problem. In each iteration, the IPDIP algorithm obtains the predictor and corrector steps by solving the Karush-Kuhn-Tucker (KKT) equation twice. The predictor term is used to responsible for optimal solution and the corrector term keeps the current iteration away from the boundary of the feasible region. Furthermore, a modification of the centering parameter is developed to accelerate the convergence speed for the IPDIP algorithm. Simulation results of LP decoding demonstrate that the proposed IPDIP algorithm achieves beautiful bit error rate (BER) performance and good global convergence properties with less iteration number and time than other algorithms which only solve the KKT equation once by Newton method or use the not modified centering parameter.

IEEE International Conference on Communication Technology (ICCT)•Sep 1, 2011•0 citations

Multistep linear programming approaches for decoding low-density parity-check codes

Haiyang Liu, Lianrong Ma, Jie Chen

The problem of improving the performance of linear programming (LP) decoding of low-density parity-check (LDPC) codes is considered in this paper. A multistep linear programming (MLP) algorithm was developed for decoding LDPC codes that includes a slight increase in computational complexity. The MLP decoder adaptively adds new constraints which are compatible with a selected check node to refine the results when an error is reported by the original LP decoder. The MLP decoder result is shown to have the maximum-likelihood (ML) certificate property. Simulations with moderate block length LOpe codes suggest that the M LP decoder gives better performance than both the original LP decoder and the conventional sum-product (SP) decoder.

Tsinghua Science & Technology•Oct 1, 2009•2 citations

Iterative Linear Programming Decoding of Nonbinary LDPC Codes With Linear Complexity

Dina Goldin, David Burshtein

The problem of low-complexity linear programming (LP) decoding of nonbinary low-density parity-check (LDPC) codes is considered, and an iterative LP decoding algorithm is presented. Results that were previously derived for binary LDPC codes are extended to the nonbinary case. Both simple and generalized nonbinary LDPC codes are considered. It is shown how the algorithm can be implemented efficiently using a finite-field fast Fourier transform. Then, the convergence rate of the algorithm is analyzed. The complexity of the algorithm scales linearly in the block length, and it can approximate, up to an arbitrarily small relative error, the objective function of the exact LP solution. When applied to a typical code from an appropriate nonbinary LDPC code ensemble, the algorithm can correct a constant fraction of errors in linear (in the block length) computational complexity. Computer experiments with the new iterative LP decoding algorithm show that, in the error floor region, it can have better performance compared to belief propagation decoding, with similar computational requirements.

IEEE Transactions on Information Theory•Aug 6, 2012•16 citations
This paper explores ideas for fast linear programming (LP) decoding of low-density parity-check (LDPC) codes. We first propose a modification of adaptive LP decoding, and prove that it performs LP decoding by solving a number of linear programs that contain at most one linear constraint derived from each of the parity-check constraints. Then, as a step toward designing an efficient LP solver that exploits the structure of LDPC codes, we study a sparse interior-point implementation for solving this sequence of linear programs. Since the most complex part of each iteration of the interior-point algorithms is to solve a (usually ill-conditioned) system of linear equations for finding the step direction, we propose a framework for designing preconditioners to be used with the iterative methods for solving these systems. The effectiveness of the proposed approach is demonstrated via both analytical and simulation results.
While linear programming (LP) decoding provides more flexibility for finite-length performance analysis than iterative message-passing (IMP) decoding, it is computationally more complex to implement in its original form, due to both the large size of the relaxed LP problem and the inefficiency of using general-purpose LP solvers. This paper explores ideas for fast LP decoding of low-density parity-check (LDPC) codes. By modifying the previously reported Adaptive LP decoding scheme to allow removal of unnecessary constraints, we first prove that LP decoding can be performed by solving a number of LP problems that each contains at most one linear constraint derived from each of the parity-check constraints. By exploiting this property, we study a sparse interior-point implementation for solving this sequence of linear programs. Since the most complex part of each iteration of the interior-point algorithm is the solution of a (usually ill-conditioned) system of linear equations for finding the step direction, we propose a preconditioning algorithm to facilitate solving such systems iteratively. The proposed preconditioning algorithm is similar to the encoding procedure of LDPC codes, and we demonstrate its effectiveness via both analytical methods and computer simulation results.
In this paper, an efficient implementation of the interior point algorithm recently proposed by Wadayama for linear programming (LP) decoding of low-density parity-check (LDPC) codes is presented. The main idea behind the modification is to approximate the barrier function for the fundamental polytope defining the code so that it contains only one linear constraint for each of the parity-check constraints. Simulation results show that the approximations introduced do not result in any performance degradation, while considerably reducing the decoding complexity and latency.
This paper presents a hybrid decoding algorithm for low-density parity-check (LDPC) codes based on the interior point method with barrier function for linear programming (LP) decoding introduced by Wadayama . First, an efficient implementation of Wadayama's algorithm is presented. The main idea behind the modification is to approximate the barrier function for the fundamental polytope defining the code so that it contains only one linear constraint for each of the parity-check constraints. A two-stage hybrid decoding which combines the interior point decoding and a low-complexity decoding algorithm for LDPC codes is then proposed. Simulation results show that the approximations introduced in the proposed algorithms do not result in any performance degradation, while considerably reducing the decoding complexity and latency.
The linear programming (LP) decoding of Low-Density Parity-Check (LDPC) codes is widely concerned for its maximum likelihood (ML) features. It is that the ML decoding rule for LDPC codes can be relaxed to LP optimization problem. Therefore, this paper focus on an efficient algorithm called infeasible primal-dual interior-point (IPDIP) to solve the LP problem. In each iteration, the IPDIP algorithm obtains the predictor and corrector steps by solving the Karush-Kuhn-Tucker (KKT) equation twice. The predictor term is used to responsible for optimal solution and the corrector term keeps the current iteration away from the boundary of the feasible region. Furthermore, a modification of the centering parameter is developed to accelerate the convergence speed for the IPDIP algorithm. Simulation results of LP decoding demonstrate that the proposed IPDIP algorithm achieves beautiful bit error rate (BER) performance and good global convergence properties with less iteration number and time than other algorithms which only solve the KKT equation once by Newton method or use the not modified centering parameter.
The problem of improving the performance of linear programming (LP) decoding of low-density parity-check (LDPC) codes is considered in this paper. A multistep linear programming (MLP) algorithm was developed for decoding LDPC codes that includes a slight increase in computational complexity. The MLP decoder adaptively adds new constraints which are compatible with a selected check node to refine the results when an error is reported by the original LP decoder. The MLP decoder result is shown to have the maximum-likelihood (ML) certificate property. Simulations with moderate block length LOpe codes suggest that the M LP decoder gives better performance than both the original LP decoder and the conventional sum-product (SP) decoder.
The problem of low-complexity linear programming (LP) decoding of nonbinary low-density parity-check (LDPC) codes is considered, and an iterative LP decoding algorithm is presented. Results that were previously derived for binary LDPC codes are extended to the nonbinary case. Both simple and generalized nonbinary LDPC codes are considered. It is shown how the algorithm can be implemented efficiently using a finite-field fast Fourier transform. Then, the convergence rate of the algorithm is analyzed. The complexity of the algorithm scales linearly in the block length, and it can approximate, up to an arbitrarily small relative error, the objective function of the exact LP solution. When applied to a typical code from an appropriate nonbinary LDPC code ensemble, the algorithm can correct a constant fraction of errors in linear (in the block length) computational complexity. Computer experiments with the new iterative LP decoding algorithm show that, in the error floor region, it can have better performance compared to belief propagation decoding, with similar computational requirements.