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:1708.06959 · International Symposium on Turbo Codes and Iterative Information Processing

Adaptive Linear Programming Decoding of Nonbinary Linear Codes Over Prime Fields

Eirik Rosnes, Michael Helmling

Published Sep 1, 2016• 4 citations
arXivHTMLPDF

Abstract

In this work, we study linear programming (LP) decoding of nonbinary linear codes over prime fields. In particular, we develop a novel separation algorithm for valid inequalities describing the codeword polytope of the so-called constant-weight embedding of a single parity-check (SPC) code over any prime field. The algorithm has linear (in the length of the SPC code) complexity, is structurally different from the one for binary codes, and is based on the principle of dynamic programming. Furthermore, it is the basis of the proposed efficient (relaxed) adaptive LP (ALP) decoder for general (non-SPC) linear codes over any prime field, generalizing the well-known ALP decoding algorithm for binary codes. Numerical results show that the ALP decoding algorithm is very efficient compared to a static approach.

DOI
10.1109/istc.2016.7593086

Related papers

On adaptive linear programming decoding of linear codes over GF(8)

Eirik Rosnes, Michael Helmling

In this work, we consider adaptive linear programming (LP) decoding of linear codes over GF(8). In particular, we give explicit constructions of valid inequalities (using no auxiliary variables) for the codeword polytope (or the convex hull) of the so-called constant-weight embedding of a single parity-check code over GF(8) that all are facet-defining. We conjecture that these inequalities together with so-called simplex constraints give a complete and irredundant description of the embedded (under the constant-weight embedding) codeword polytope. Furthermore, these sets of inequalities are used to develop an efficient (as compared to a static approach) exact (assuming that the conjecture is true) adaptive LP decoder for linear codes over GF(8). Numerical results show that only a very small subset of these inequalities is necessary for achieving close-to-exact LP decoding performance.

Information Theory and Applications Workshop (ITA)•Jan 1, 2016•1 citation

On adaptive linear programming decoding of ternary linear codes

Eirik Rosnes, Michael Helmling

In this work, we consider adaptive linear programming (LP) decoding of ternary linear codes, i. e., linear codes over the finite field Fqwith q = 3 elements. In particular, we characterize completely the codeword polytope (or the convex hull) of the binary image, under Flanagan's embedding, of a ternary single parity-check code. Then, this characterization is used to develop an efficient adaptive LP decoder for ternary codes. Numerical experiments confirm that this decoder is very efficient compared to a static LP decoder and scales well with both block length and check node degree. Finally, we briefly consider the case of nonbinary codes over the finite field Fqwith q = 3melements, where m > 1 is a positive integer.

IEEE Information Theory Workshop (ITW)•Apr 1, 2015•5 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

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•17 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

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
In this work, we study linear programming (LP) decoding of nonbinary linear codes over prime fields. In particular, we develop a novel separation algorithm for valid inequalities describing the codeword polytope of the so-called constant-weight embedding of a single parity-check (SPC) code over any prime field. The algorithm has linear (in the length of the SPC code) complexity, is structurally different from the one for binary codes, and is based on the principle of dynamic programming. Furthermore, it is the basis of the proposed efficient (relaxed) adaptive LP (ALP) decoder for general (non-SPC) linear codes over any prime field, generalizing the well-known ALP decoding algorithm for binary codes. Numerical results show that the ALP decoding algorithm is very efficient compared to a static approach.
In this work, we consider adaptive linear programming (LP) decoding of linear codes over GF(8). In particular, we give explicit constructions of valid inequalities (using no auxiliary variables) for the codeword polytope (or the convex hull) of the so-called constant-weight embedding of a single parity-check code over GF(8) that all are facet-defining. We conjecture that these inequalities together with so-called simplex constraints give a complete and irredundant description of the embedded (under the constant-weight embedding) codeword polytope. Furthermore, these sets of inequalities are used to develop an efficient (as compared to a static approach) exact (assuming that the conjecture is true) adaptive LP decoder for linear codes over GF(8). Numerical results show that only a very small subset of these inequalities is necessary for achieving close-to-exact LP decoding performance.
In this work, we consider adaptive linear programming (LP) decoding of ternary linear codes, i. e., linear codes over the finite field Fqwith q = 3 elements. In particular, we characterize completely the codeword polytope (or the convex hull) of the binary image, under Flanagan's embedding, of a ternary single parity-check code. Then, this characterization is used to develop an efficient adaptive LP decoder for ternary codes. Numerical experiments confirm that this decoder is very efficient compared to a static LP decoder and scales well with both block length and check node degree. Finally, we briefly consider the case of nonbinary codes over the finite field Fqwith q = 3melements, where m > 1 is a positive integer.
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.
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.
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.
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.