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

arXiv:1409.4761 · International Symposium on Telecommunications

Reducing the complexity of the linear programming decoding

Hassan Tavakoli

Published Sep 1, 2014• 3 citations
arXivHTMLPDF

Abstract

In this paper we show how the complexity of Linear Programming (LP) decoder can decrease. We use the degree 3 check equation to model all variation check degrees. The complexity of LP decoding is directed relative to the number of constraint. Number of constraint for original LP decoder is O(n2n). Our method decrease the number of the constraint to O(n).

DOI
10.1109/istel.2014.7000772

Related papers

Adaptive Linear Programming Decoding

Mohammad H. Taghavi N., Paul H. Siegel

Detectability of failures of linear programming (LP) decoding and its potential for improvement by adding new constraints motivate the use of an adaptive approach in selecting the constraints for the LP problem. In this paper, we make a first step in studying this method, and show that it can significantly reduce the complexity of the problem, which was originally exponential in the maximum check-node degree. We further show that adaptively adding new constraints, e.g. by combining parity checks, can provide large gains in the performance.

arXiv:cs/0601099•Jan 23, 2006•31 citations

Adaptive Methods for Linear Programming Decoding

M. Hossein Taghavi, Paul H. Siegel

Detectability of failures of linear programming (LP) decoding and the potential for improvement by adding new constraints motivate the use of an adaptive approach in selecting the constraints for the underlying LP problem. In this paper, we make a first step in studying this method, and show that by starting from a simple LP problem and adaptively adding the necessary constraints, the complexity of LP decoding can be significantly reduced. In particular, we observe that with adaptive LP decoding, the sizes of the LP problems that need to be solved become practically independent of the density of the parity-check matrix. We further show that adaptively adding extra constraints, such as constraints based on redundant parity checks, can provide large gains in the performance.

arXiv:cs/0703123•IEEE Transactions on Information Theory•Dec 1, 2008•117 citations

Adaptive Linear Programming Decoding

Mohammad Taghavi, Paul H. Siegel

The ability of linear programming (LP) decoding to detect failures, and its potential for improvement by the addition of new constraints, motivates the use of an adaptive approach in selecting the constraints for the underlying LP problem. In this paper, we show that the application of such adaptive methods can significantly reduce the complexity of the LP decoding algorithm, which, in the standard formulation, is exponential in the maximum row weight of the parity-check matrix. We further show that adaptively adding new constraints, e.g. by combining parity checks, can provide large gains in LP decoder performance

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2006•46 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.

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

An Investigation on LP Decoding of Short Binary Linear Codes With the Subgradient Method

Haiyang LIU, Xiaopeng Jiao, Lianrong Ma

In this letter, we investigate the application of the subgradient method to design efficient algorithm for linear programming (LP) decoding of binary linear codes. A major drawback of the original formulation of LP decoding is that the description complexity of the feasible region is exponential in the check node degrees of the code. In order to tackle the problem, we propose a processing technique for LP decoding with the subgradient method, whose complexity is linear in the check node degrees. Consequently, a message-passing type decoding algorithm can be obtained, whose per-iteration complexity is extremely low. Moreover, if the algorithm converges to a valid codeword, it is guaranteed to be a maximum likelihood codeword. Simulation results on several binary linear codes with short lengths suggest that the performances of LP decoding based on the subgradient method and the state-of-art LP decoding implementation approach are comparable.

IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences•Nov 20, 2023•1 citation

Improved Check Node Decomposition for Linear Programming Decoding

Xiaopeng Jiao, Jianjun Mu

For the linear programming decoding (LPD) proposed by Feldman et al., the number of constraints increases exponentially with check degrees. By decomposing a high-degree check node into a number of degree-3 check nodes, the number of constraints grows linearly with check degrees. In this letter, we show that the size of the LPD can be reduced by decomposing a high-degree check node into a number of degree-4 check nodes. The LPD using the degree-4 decomposition leads to almost the same number of constraints as using the degree-3 decomposition, while the number of auxiliary variable nodes is less than half of the one using the degree-3 decomposition. Moreover, when decomposing a high degree check node into a number of check nodes with degree d, d>4, the number of constraints increases rapidly and the size of the LPD becomes larger than the degree-4 decomposition. It is demonstrated on an LDPC code and a BCH code that the decoding time of the degree-4 decomposition is the smallest among the different decomposition methods.

IEEE Communications Letters•Jan 2, 2013•4 citations
In this paper we show how the complexity of Linear Programming (LP) decoder can decrease. We use the degree 3 check equation to model all variation check degrees. The complexity of LP decoding is directed relative to the number of constraint. Number of constraint for original LP decoder is O(n2n). Our method decrease the number of the constraint to O(n).
Detectability of failures of linear programming (LP) decoding and its potential for improvement by adding new constraints motivate the use of an adaptive approach in selecting the constraints for the LP problem. In this paper, we make a first step in studying this method, and show that it can significantly reduce the complexity of the problem, which was originally exponential in the maximum check-node degree. We further show that adaptively adding new constraints, e.g. by combining parity checks, can provide large gains in the performance.
Detectability of failures of linear programming (LP) decoding and the potential for improvement by adding new constraints motivate the use of an adaptive approach in selecting the constraints for the underlying LP problem. In this paper, we make a first step in studying this method, and show that by starting from a simple LP problem and adaptively adding the necessary constraints, the complexity of LP decoding can be significantly reduced. In particular, we observe that with adaptive LP decoding, the sizes of the LP problems that need to be solved become practically independent of the density of the parity-check matrix. We further show that adaptively adding extra constraints, such as constraints based on redundant parity checks, can provide large gains in the performance.
The ability of linear programming (LP) decoding to detect failures, and its potential for improvement by the addition of new constraints, motivates the use of an adaptive approach in selecting the constraints for the underlying LP problem. In this paper, we show that the application of such adaptive methods can significantly reduce the complexity of the LP decoding algorithm, which, in the standard formulation, is exponential in the maximum row weight of the parity-check matrix. We further show that adaptively adding new constraints, e.g. by combining parity checks, can provide large gains in LP decoder performance
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 letter, we investigate the application of the subgradient method to design efficient algorithm for linear programming (LP) decoding of binary linear codes. A major drawback of the original formulation of LP decoding is that the description complexity of the feasible region is exponential in the check node degrees of the code. In order to tackle the problem, we propose a processing technique for LP decoding with the subgradient method, whose complexity is linear in the check node degrees. Consequently, a message-passing type decoding algorithm can be obtained, whose per-iteration complexity is extremely low. Moreover, if the algorithm converges to a valid codeword, it is guaranteed to be a maximum likelihood codeword. Simulation results on several binary linear codes with short lengths suggest that the performances of LP decoding based on the subgradient method and the state-of-art LP decoding implementation approach are comparable.
For the linear programming decoding (LPD) proposed by Feldman et al., the number of constraints increases exponentially with check degrees. By decomposing a high-degree check node into a number of degree-3 check nodes, the number of constraints grows linearly with check degrees. In this letter, we show that the size of the LPD can be reduced by decomposing a high-degree check node into a number of degree-4 check nodes. The LPD using the degree-4 decomposition leads to almost the same number of constraints as using the degree-3 decomposition, while the number of auxiliary variable nodes is less than half of the one using the degree-3 decomposition. Moreover, when decomposing a high degree check node into a number of check nodes with degree d, d>4, the number of constraints increases rapidly and the size of the LPD becomes larger than the degree-4 decomposition. It is demonstrated on an LDPC code and a BCH code that the decoding time of the degree-4 decomposition is the smallest among the different decomposition methods.