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 Information Theory Workshop (ITW)

On adaptive linear programming decoding of ternary linear codes

Eirik Rosnes, Michael Helmling

Published Apr 1, 2015• 5 citations
Publisher

Abstract

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.

DOI
10.1109/itw.2015.7133150

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

Adaptive Linear Programming Decoding of Nonbinary Linear Codes Over Prime Fields

Eirik Rosnes, Michael Helmling

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.

arXiv:1708.06959•International Symposium on Turbo Codes and Iterative Information Processing•Sep 1, 2016•4 citations

Linear-Programming Decoding of Nonbinary Linear Codes

Mark F. Flanagan, Vitaly Skachek, Eimear Byrne +1 more

A framework for linear-programming (LP) decoding of nonbinary linear codes over rings is developed. This framework facilitates LP-based reception for coded modulation systems which use direct modulation mapping of coded symbols. It is proved that the resulting LP decoder has the ldquomaximum-likelihood (ML) certificaterdquo property. It is also shown that the decoder output is the lowest cost pseudocodeword. Equivalence between pseudocodewords of the linear program and pseudocodewords of graph covers is proved. It is also proved that if the modulator-channel combination satisfies a particular symmetry condition, the codeword error rate performance is independent of the transmitted codeword. Two alternative polytopes for use with LP decoding are studied, and it is shown that for many classes of codes these polytopes yield a complexity advantage for decoding. These polytope representations lead to polynomial-time decoders for a wide variety of classical nonbinary linear codes. LP decoding performance is illustrated for ternary Golay code with ternary phase-shift keying (PSK) modulation over additive white Gaussian noise (AWGN), and in this case it is shown that the performance of the LP decoder is comparable to codeword-error-rate-optimum hard-decision-based decoding. LP decoding is also simulated for medium-length ternary and quaternary low-density parity-check (LDPC) codes with corresponding PSK modulations over AWGN.

arXiv:0707.4360•IEEE Transactions on Information Theory•Aug 24, 2009•66 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

Approximate iterative LP decoding of LDPC codes over GF(q) in linear complexity

Dina Goldin, David Burshtein

The problem of low-complexity approximated linear programming (LP) decoding of LDPC codes over GF(q) is considered. An iterative algorithm with linear complexity was proposed by Burshtein for the binary case. However, this algorithm cannot be trivially generalized for the non-binary case, since the derivation uses the even parity property of the check nodes, which does not hold for codes over GF(q). In this work the algorithm is generalized to the non-binary case. We show, that by applying this algorithm to a softened version of the non-binary LP problem proposed by Flanagan, Skachek, Byrne and Grefeath, we can obtain, with complexity linear in the block length, a feasible solution vector for the non-binary LP decoding problem, which is arbitrarily close to optimal in the following sense. The distance between the minimum value achieved by the exact LP decoder and the objective function value of the approximate solution, normalized by the block length of the code, can be made arbitrarily small. We present simulation results and comparisons with the belief propagation (BP) algorithm using-regular ternary LDPC codes. The proposed algorithm can be easily extended to generalized LDPC codes.

IEEE Convention of Electrical and Electronics Engineers in Israel•Nov 1, 2010•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
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.
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 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.
A framework for linear-programming (LP) decoding of nonbinary linear codes over rings is developed. This framework facilitates LP-based reception for coded modulation systems which use direct modulation mapping of coded symbols. It is proved that the resulting LP decoder has the ldquomaximum-likelihood (ML) certificaterdquo property. It is also shown that the decoder output is the lowest cost pseudocodeword. Equivalence between pseudocodewords of the linear program and pseudocodewords of graph covers is proved. It is also proved that if the modulator-channel combination satisfies a particular symmetry condition, the codeword error rate performance is independent of the transmitted codeword. Two alternative polytopes for use with LP decoding are studied, and it is shown that for many classes of codes these polytopes yield a complexity advantage for decoding. These polytope representations lead to polynomial-time decoders for a wide variety of classical nonbinary linear codes. LP decoding performance is illustrated for ternary Golay code with ternary phase-shift keying (PSK) modulation over additive white Gaussian noise (AWGN), and in this case it is shown that the performance of the LP decoder is comparable to codeword-error-rate-optimum hard-decision-based decoding. LP decoding is also simulated for medium-length ternary and quaternary low-density parity-check (LDPC) codes with corresponding PSK modulations over AWGN.
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.
The problem of low-complexity approximated linear programming (LP) decoding of LDPC codes over GF(q) is considered. An iterative algorithm with linear complexity was proposed by Burshtein for the binary case. However, this algorithm cannot be trivially generalized for the non-binary case, since the derivation uses the even parity property of the check nodes, which does not hold for codes over GF(q). In this work the algorithm is generalized to the non-binary case. We show, that by applying this algorithm to a softened version of the non-binary LP problem proposed by Flanagan, Skachek, Byrne and Grefeath, we can obtain, with complexity linear in the block length, a feasible solution vector for the non-binary LP decoding problem, which is arbitrarily close to optimal in the following sense. The distance between the minimum value achieved by the exact LP decoder and the objective function value of the approximate solution, normalized by the block length of the code, can be made arbitrarily small. We present simulation results and comparisons with the belief propagation (BP) algorithm using-regular ternary LDPC codes. The proposed algorithm can be easily extended to generalized LDPC codes.
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.