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

IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences

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

Haiyang LIU, Xiaopeng Jiao, Lianrong Ma

Published Nov 20, 2023• 1 citation
Publisher

Abstract

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.

DOI
10.1587/transfun.2023eal2045

Related papers

Low-Complexity LP Decoding of Nonbinary Linear Codes

Mayur Punekar, Pascal O. Vontobel, Mark F. Flanagan

Linear Programming (LP) decoding of Low-Density Parity-Check (LDPC) codes has attracted much attention in the research community in the past few years. LP decoding has been derived for binary and nonbinary linear codes. However, the most important problem with LP decoding for both binary and nonbinary linear codes is that the complexity of standard LP solvers such as the simplex algorithm remains prohibitively large for codes of moderate to large block length. To address this problem, two low-complexity LP (LCLP) decoding algorithms for binary linear codes have been proposed by Vontobel and Koetter, henceforth called the basic LCLP decoding algorithm and the subgradient LCLP decoding algorithm. In this paper, we generalize these LCLP decoding algorithms to nonbinary linear codes. The computational complexity per iteration of the proposed nonbinary LCLP decoding algorithms scales linearly with the block length of the code. A modified BCJR algorithm for efficient check-node calculations in the nonbinary basic LCLP decoding algorithm is also proposed, which has complexity linear in the check node degree. Several simulation results are presented for nonbinary LDPC codes defined over Z4, GF(4), and GF(8) using quaternary phase-shift keying and 8-phase-shift keying, respectively, over the AWGN channel. It is shown that for some group-structured LDPC codes, the error-correcting performance of the nonbinary LCLP decoding algorithms is similar to or better than that of the min-sum decoding algorithm.

arXiv:1211.5757•IEEE Transactions on Communications•Jul 16, 2013•16 citations

Low complexity Linear Programming decoding of nonbinary linear codes

Mayur Punekar, Mark F. Flanagan

Linear Programming (LP) decoding of Low-Density Parity-Check (LDPC) codes has attracted much attention in the research community in the past few years. The aim of LP decoding is to develop an algorithm which has error-correcting performance similar to that of the Sum-Product (SP) decoding algorithm, while at the same time it should be amenable to mathematical analysis. The LP decoding algorithm has been derived for both binary and nonbinary decoding frameworks. However, the most important problem with LP decoding for both binary and nonbinary linear codes is that the complexity of standard LP solvers such as the simplex algorithm remain prohibitively large for codes of moderate to large block length. To address this problem, Vontobel et al. proposed a low complexity LP decoding algorithm for binary linear codes which has complexity linear in the block length. In this paper, we extend the latter work and propose a low-complexity LP decoding algorithm for nonbinary linear codes. We use the LP formulation for the nonbinary codes as a basis and derive a pair of primal-dual LP formulations. The dual LP is then used to develop the low-complexity LP decoding algorithm for nonbinary linear codes. The complexity of the proposed algorithm is linear in the block length and is limited mainly by the maximum check node degree. As a proof of concept, we also present a simulation result for a [80, 48] LDPC code defined over ℤ4using quaternary phase-shift keying over the AWGN channel, and we show that the error-correcting performance of the proposed LP decoding algorithm is similar to that of the standard LP decoding using the simplex solver.

Allerton Conference on Communication, Control, and Computing•Sep 1, 2010•8 citations

Low Complexity Linear Programming Decoding of Nonbinary Linear Codes

Mayur Punekar, Mark F. Flanagan

Linear Programming (LP) decoding of Low-Density Parity-Check (LDPC) codes has attracted much attention in the research community in the past few years. The aim of LP decoding is to develop an algorithm which has error-correcting performance similar to that of the Sum-Product (SP) decoding algorithm, while at the same time it should be amenable to mathematical analysis. The LP decoding algorithm has also been extended to nonbinary linear codes by Flanagan et al. However, the most important problem with LP decoding for both binary and nonbinary linear codes is that the complexity of standard LP solvers such as the simplex algorithm remain prohibitively large for codes of moderate to large block length. To address this problem, Vontobel et al. proposed a low complexity LP decoding algorithm for binary linear codes which has complexity linear in the block length. In this paper, we extend the latter work and propose a low-complexity LP decoding algorithm for nonbinary linear codes. We use the LP formulation proposed by Flanagan et al. as a basis and derive a pair of primal-dual LP formulations. The dual LP is then used to develop the low-complexity LP decoding algorithm for nonbinary linear codes. In contrast to the binary low-complexity LP decoding algorithm, our proposed algorithm is not directly related to the nonbinary SP algorithm. Nevertheless, the complexity of the proposed algorithm is linear in the block length and is limited mainly by the maximum check node degree. As a proof of concept, we also present a simulation result for a $[80,48]$ LDPC code defined over $\mathbb{Z}_4$ using quaternary phase-shift keying over the AWGN channel, and we show that the error-correcting performance of the proposed LP decoding algorithm is similar to that of the standard LP decoding using the simplex solver.

arXiv:1007.1368•Jul 8, 2010•0 citations

A Note on the Linear Programming Decoding of Binary Linear Codes for Multiple-Access Channel

Shunsuke Horii, Toshiyasu Matsushima, Shigeichi Hirasawa

In this paper, we develop linear-programming (LP) decoding for multiple-access channels with binary linear codes. For single-user channels, LP decoding has attracted much attention in recent years as a good approximation to maximum-likelihood (ML) decoding. We demonstrate how the ML decoding problem for multiple-access channels with binary linear codes can be formulated as an LP problem. This is not straightforward, because the objective function of the problem is generally a non-linear function of the codeword symbols. We introduce auxiliary variables such that the objective function is a linear function of these variables. The ML decoding problem then reduces to the LP problem. As in the case for single-user channels, we formulate the relaxed LP problem to reduce the complexity for practical implementation, and as a result propose a decoder that has the desirable property known as the ML certificate property (i.e., if the decoder outputs an integer solution, the solution is guaranteed to be the ML codeword). Although the computational complexity of the proposed algorithm is exponential in the number of users, we can reduce this complexity for Gaussian multiple-access channels. Furthermore, we compare the performance of the proposed decoder with a decoder based on the sum-product algorithm.

IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences•Jan 1, 2011•0 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

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
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.
Linear Programming (LP) decoding of Low-Density Parity-Check (LDPC) codes has attracted much attention in the research community in the past few years. LP decoding has been derived for binary and nonbinary linear codes. However, the most important problem with LP decoding for both binary and nonbinary linear codes is that the complexity of standard LP solvers such as the simplex algorithm remains prohibitively large for codes of moderate to large block length. To address this problem, two low-complexity LP (LCLP) decoding algorithms for binary linear codes have been proposed by Vontobel and Koetter, henceforth called the basic LCLP decoding algorithm and the subgradient LCLP decoding algorithm. In this paper, we generalize these LCLP decoding algorithms to nonbinary linear codes. The computational complexity per iteration of the proposed nonbinary LCLP decoding algorithms scales linearly with the block length of the code. A modified BCJR algorithm for efficient check-node calculations in the nonbinary basic LCLP decoding algorithm is also proposed, which has complexity linear in the check node degree. Several simulation results are presented for nonbinary LDPC codes defined over Z4, GF(4), and GF(8) using quaternary phase-shift keying and 8-phase-shift keying, respectively, over the AWGN channel. It is shown that for some group-structured LDPC codes, the error-correcting performance of the nonbinary LCLP decoding algorithms is similar to or better than that of the min-sum decoding algorithm.
Linear Programming (LP) decoding of Low-Density Parity-Check (LDPC) codes has attracted much attention in the research community in the past few years. The aim of LP decoding is to develop an algorithm which has error-correcting performance similar to that of the Sum-Product (SP) decoding algorithm, while at the same time it should be amenable to mathematical analysis. The LP decoding algorithm has been derived for both binary and nonbinary decoding frameworks. However, the most important problem with LP decoding for both binary and nonbinary linear codes is that the complexity of standard LP solvers such as the simplex algorithm remain prohibitively large for codes of moderate to large block length. To address this problem, Vontobel et al. proposed a low complexity LP decoding algorithm for binary linear codes which has complexity linear in the block length. In this paper, we extend the latter work and propose a low-complexity LP decoding algorithm for nonbinary linear codes. We use the LP formulation for the nonbinary codes as a basis and derive a pair of primal-dual LP formulations. The dual LP is then used to develop the low-complexity LP decoding algorithm for nonbinary linear codes. The complexity of the proposed algorithm is linear in the block length and is limited mainly by the maximum check node degree. As a proof of concept, we also present a simulation result for a [80, 48] LDPC code defined over ℤ4using quaternary phase-shift keying over the AWGN channel, and we show that the error-correcting performance of the proposed LP decoding algorithm is similar to that of the standard LP decoding using the simplex solver.
Linear Programming (LP) decoding of Low-Density Parity-Check (LDPC) codes has attracted much attention in the research community in the past few years. The aim of LP decoding is to develop an algorithm which has error-correcting performance similar to that of the Sum-Product (SP) decoding algorithm, while at the same time it should be amenable to mathematical analysis. The LP decoding algorithm has also been extended to nonbinary linear codes by Flanagan et al. However, the most important problem with LP decoding for both binary and nonbinary linear codes is that the complexity of standard LP solvers such as the simplex algorithm remain prohibitively large for codes of moderate to large block length. To address this problem, Vontobel et al. proposed a low complexity LP decoding algorithm for binary linear codes which has complexity linear in the block length. In this paper, we extend the latter work and propose a low-complexity LP decoding algorithm for nonbinary linear codes. We use the LP formulation proposed by Flanagan et al. as a basis and derive a pair of primal-dual LP formulations. The dual LP is then used to develop the low-complexity LP decoding algorithm for nonbinary linear codes. In contrast to the binary low-complexity LP decoding algorithm, our proposed algorithm is not directly related to the nonbinary SP algorithm. Nevertheless, the complexity of the proposed algorithm is linear in the block length and is limited mainly by the maximum check node degree. As a proof of concept, we also present a simulation result for a [80,48][80,48][80,48] LDPC code defined over Z4\mathbb{Z}_4Z4​ using quaternary phase-shift keying over the AWGN channel, and we show that the error-correcting performance of the proposed LP decoding algorithm is similar to that of the standard LP decoding using the simplex solver.
In this paper, we develop linear-programming (LP) decoding for multiple-access channels with binary linear codes. For single-user channels, LP decoding has attracted much attention in recent years as a good approximation to maximum-likelihood (ML) decoding. We demonstrate how the ML decoding problem for multiple-access channels with binary linear codes can be formulated as an LP problem. This is not straightforward, because the objective function of the problem is generally a non-linear function of the codeword symbols. We introduce auxiliary variables such that the objective function is a linear function of these variables. The ML decoding problem then reduces to the LP problem. As in the case for single-user channels, we formulate the relaxed LP problem to reduce the complexity for practical implementation, and as a result propose a decoder that has the desirable property known as the ML certificate property (i.e., if the decoder outputs an integer solution, the solution is guaranteed to be the ML codeword). Although the computational complexity of the proposed algorithm is exponential in the number of users, we can reduce this complexity for Gaussian multiple-access channels. Furthermore, we compare the performance of the proposed decoder with a decoder based on the sum-product algorithm.
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.
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.