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

IEEE International Conference on Communication Technology (ICCT)

Modified multistage linear programming decoding of LDPC codes

Xian Zhang, Piming Ma

Published Sep 1, 2011• 1 citation
Publisher

Abstract

Linear programming (LP) decoding is getting more and more attention because of the maximum-likelihood (ML) certificate property. As one of the improved LP decoding methods, multistage LP (MLP) decoding has been proposed to improve the performance of LP decoding but at the cost of higher complexity. In this paper, the problem of achieving a balance between the performance and the complexity of LP decoding is considered. First, a criterion used for searching new constraints adaptively is proposed. Then a modified MLP decoding is presented by incorporating the adaptive decoding algorithm to decrease the complexity. The presented modified MLP decoding can obtain a good tradeoff between the performance and the complexity and is proved also has the ML certificate characteristic. Simulations with moderate block length LDPC codes show that the proposed MLP decoding achieves the same BER performance as the original MLP decoding with far fewer used constraints and faster convergence speed consequently.

DOI
10.1109/icct.2011.6157842

Related papers

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

Nonlinear programming approaches to decoding low-density parity-check codes

Kai Yang, J. Feldman, Xiaodong Wang

We consider the decoding problem for low-density parity-check codes, and apply nonlinear programming methods. This extends previous work using linear programming (LP) to decode linear block codes. First, a multistage LP decoder based on the branch-and-bound method is proposed. This decoder makes use of the maximum-likelihood-certificate property of the LP decoder to refine the results when an error is reported. Second, we transform the original LP decoding formulation into a box-constrained quadratic programming form. Efficient linear-time parallel and serial decoding algorithms are proposed and their convergence properties are investigated. Extensive simulation studies are performed to assess the performance of the proposed decoders. It is seen that the proposed multistage LP decoder outperforms the conventional sum-product (SP) decoder considerably for low-density parity-check (LDPC) codes with short to medium block length. The proposed box-constrained quadratic programming decoder has less complexity than the SP decoder and yields much better performance for LDPC codes with regular structure

IEEE Journal on Selected Areas in Communications•Aug 1, 2006•54 citations

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.

IEEE Transactions on Information Theory•Sep 1, 2011•48 citations

Adaptive cut generation for improved linear programming decoding of binary linear codes

Xiaojie Zhang, Paul H. Siegel

Linear programming (LP) decoding approximates optimal maximum-likelihood (ML) decoding of a linear block code by relaxing the equivalent ML integer programming (IP) problem into a more easily solved LP problem. The LP problem is defined by a set of linear inequalities derived from the constraints represented by the rows of a parity-check matrix of the code. Adaptive linear programming (ALP) decoding significantly reduces the complexity of LP decoding by iteratively and adaptively adding necessary constraints in a sequence of smaller LP problems. Adaptive introduction of constraints derived from certain additional redundant parity check (RPC) constraints can further improve ALP performance. In this paper, we propose a new and effective algorithm to identify RPCs that produce linear constraints, referred to as “cuts,” that can eliminate non-ML solutions generated by the ALP decoder, often significantly improving the decoder error-rate performance. The cut-finding algorithm is based upon a specific transformation of an initial parity-check matrix of the linear block code. Simulation results for several low-density parity-check codes demonstrate that the modified ALP decoding algorithm significantly narrows the performance gap between LP decoding and ML decoding.

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2011•3 citations

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. We first prove, by modifying the previously reported Adaptive LP decoding scheme to allow removal of unnecessary constraints, that LP decoding can be performed by solving a number of LP problems that contain 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 iterative solution of such systems. 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•Feb 4, 2009•2 citations

ML decoding via mixed-integer adaptive linear programming

Stark Christiaan Draper, Jonathan S. Yedidia, Yige Wang

Linear programming (LP) decoding was introduced by Feldman et al. (IEEE Trans. Inform. Theory Mar. 2005) as a novel way to decode binary low-density parity-check codes. Taghavi and Siegel (Proc. ISIT 2006) describe a computationally simplified decoding approach they term "adaptive" LP decoding. Adaptive LP decoding starts with a sub-set of the LP constraints, and iteratively adds violated constraints until an optimum of the original LP is found. Usually only a tiny fraction of the original constraints need to be reinstated, leading to huge efficiency gains compared to ordinary LP decoding. Here we describe a modification of the adaptive LP decoder that results in a maximum likelihood (ML) decoder. Whenever the adaptive LP decoder returns a pseudo-codeword rather than a codeword, we add an integer constraint on the least certain symbol of the pseudo-codeword. For certain codes, and especially in the high-SNR (error floor) regime, only a few integer constraints are required to force the resultant mixed-integer LP to the ML solution. We demonstrate that our approach can efficiently achieve the optimal ML decoding performance on a (155,64) LDPC code introduced by Tanner et al.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2007•46 citations
Linear programming (LP) decoding is getting more and more attention because of the maximum-likelihood (ML) certificate property. As one of the improved LP decoding methods, multistage LP (MLP) decoding has been proposed to improve the performance of LP decoding but at the cost of higher complexity. In this paper, the problem of achieving a balance between the performance and the complexity of LP decoding is considered. First, a criterion used for searching new constraints adaptively is proposed. Then a modified MLP decoding is presented by incorporating the adaptive decoding algorithm to decrease the complexity. The presented modified MLP decoding can obtain a good tradeoff between the performance and the complexity and is proved also has the ML certificate characteristic. Simulations with moderate block length LDPC codes show that the proposed MLP decoding achieves the same BER performance as the original MLP decoding with far fewer used constraints and faster convergence speed consequently.
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.
We consider the decoding problem for low-density parity-check codes, and apply nonlinear programming methods. This extends previous work using linear programming (LP) to decode linear block codes. First, a multistage LP decoder based on the branch-and-bound method is proposed. This decoder makes use of the maximum-likelihood-certificate property of the LP decoder to refine the results when an error is reported. Second, we transform the original LP decoding formulation into a box-constrained quadratic programming form. Efficient linear-time parallel and serial decoding algorithms are proposed and their convergence properties are investigated. Extensive simulation studies are performed to assess the performance of the proposed decoders. It is seen that the proposed multistage LP decoder outperforms the conventional sum-product (SP) decoder considerably for low-density parity-check (LDPC) codes with short to medium block length. The proposed box-constrained quadratic programming decoder has less complexity than the SP decoder and yields much better performance for LDPC codes with regular structure
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.
Linear programming (LP) decoding approximates optimal maximum-likelihood (ML) decoding of a linear block code by relaxing the equivalent ML integer programming (IP) problem into a more easily solved LP problem. The LP problem is defined by a set of linear inequalities derived from the constraints represented by the rows of a parity-check matrix of the code. Adaptive linear programming (ALP) decoding significantly reduces the complexity of LP decoding by iteratively and adaptively adding necessary constraints in a sequence of smaller LP problems. Adaptive introduction of constraints derived from certain additional redundant parity check (RPC) constraints can further improve ALP performance. In this paper, we propose a new and effective algorithm to identify RPCs that produce linear constraints, referred to as “cuts,” that can eliminate non-ML solutions generated by the ALP decoder, often significantly improving the decoder error-rate performance. The cut-finding algorithm is based upon a specific transformation of an initial parity-check matrix of the linear block code. Simulation results for several low-density parity-check codes demonstrate that the modified ALP decoding algorithm significantly narrows the performance gap between LP decoding and ML decoding.
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. We first prove, by modifying the previously reported Adaptive LP decoding scheme to allow removal of unnecessary constraints, that LP decoding can be performed by solving a number of LP problems that contain 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 iterative solution of such systems. 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.
Linear programming (LP) decoding was introduced by Feldman et al. (IEEE Trans. Inform. Theory Mar. 2005) as a novel way to decode binary low-density parity-check codes. Taghavi and Siegel (Proc. ISIT 2006) describe a computationally simplified decoding approach they term "adaptive" LP decoding. Adaptive LP decoding starts with a sub-set of the LP constraints, and iteratively adds violated constraints until an optimum of the original LP is found. Usually only a tiny fraction of the original constraints need to be reinstated, leading to huge efficiency gains compared to ordinary LP decoding. Here we describe a modification of the adaptive LP decoder that results in a maximum likelihood (ML) decoder. Whenever the adaptive LP decoder returns a pseudo-codeword rather than a codeword, we add an integer constraint on the least certain symbol of the pseudo-codeword. For certain codes, and especially in the high-SNR (error floor) regime, only a few integer constraints are required to force the resultant mixed-integer LP to the ML solution. We demonstrate that our approach can efficiently achieve the optimal ML decoding performance on a (155,64) LDPC code introduced by Tanner et al.