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

International Symposium on Problems of Redundancy in Information and Control Systems (REDUNDANCY)

Linear Programming Decoding of Non-Linear Sparse-Graph Codes

Gleb Balitskiy, Alexey Frolov, Pavel S. Rybin

Published Oct 25, 2021• 4 citations
Publisher

Abstract

In modern coding theory, linear code constructions are mainly used. Their properties and fundamental theoretical limits are well studied, and they are successfully applied to different classes of problems. Until now, non-linear codes did not attract much attention from specialists because linear structures have coped with their tasks and have the required research tools developed earlier. But in a series of works devoted to the study of codes with graceful degradation, H. Roozbehani, and Y. Polyanskiy proposed the construction of non-linear low-density majority codes (LDMC) and effective encoding and decoding algorithms for them. Moreover, they showed that LDMC has a lower bit error rate (BER) than any linear code in the error-reducing regime for the binary erasure channel (BEC). Given this motivation, we consider non-linear sparse-graph codes (a generalized version of LDMC) and investigate their performance in the AWGN channel. For this class of codes, we proposed efficient generalized BP-based and LP-based decoding algorithms. We accurately estimated BER under ML decoding of non-linear codes based on the LP-based decoder. Also, by simulation, we carried out the analysis and comparison of performances of various non-linear codes.

DOI
10.1109/redundancy52534.2021.9606454

Related papers

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•1 citation

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•14 citations

On LP decoding of polar codes

Naveen Goela, Satish Babu Korada, Michael Gastpar

Polar codes are the first codes to provably achieve capacity on the symmetric binary-input discrete memoryless channel (B-DMC) with low encoding and decoding complexity. The parity check matrix of polar codes is high-density and we show that linear program (LP) decoding fails on the fundamental polytope of the parity check matrix. The recursive structure of the code permits a sparse factor graph representation. We define a new polytope based on the fundamental polytope of the sparse graph representation. This new polytope P is defined in a space of dimension O(N logN) where N is the block length. We prove that the projection of P in the original space is tighter than the fundamental polytope based on the parity check matrix. The LP decoder over P obtains the ML-certificate property. In the case of the binary erasure channel (BEC), the new LP decoder is equivalent to the belief propagation (BP) decoder operating on the sparse factor graph representation, and hence achieves capacity. Simulation results of SC (successive cancellation) decoding, LP decoding over tightened polytopes, and (ML) maximum likelihood decoding are provided. For channels other than the BEC, we discuss why LP decoding over P with a linear objective function is insufficient.

IEEE Information Theory Workshop (ITW)•Aug 1, 2010•119 citations

Message passing algorithms and improved LP decoding

Sanjeev Arora, Constantinos Daskalakis, David Steurer

Linear programming decoding for low-density parity check codes (and related domains such as compressed sensing) has received increased attention over recent years because of its practical performance --coming close to that of iterative decoding algorithms--- and its amenability to finite-blocklength analysis. Several works starting with the work of Feldman et al. showed how to analyze LP decoding using properties of expander graphs. This line of analysis works for only low error rates, about a couple of orders of magnitude lower than the empirically observed performance. It is possible to do better for the case of random noise, as shown by Daskalakis et al. and Koetter and Vontobel. Building on work of Koetter and Vontobel, we obtain a novel understanding of LP decoding, which allows us to establish a 0.05-fraction of correctable errors for rate-1/2 codes; this comes very close to the performance of iterative decoders and is significantly higher than the best previously noted correctable bit error rate for LP decoding. Unlike other techniques, our analysis directly works with the primal linear program and exploits an explicit connection between LP decoding and message passing algorithms.

ACM Symposium on Theory of Computing (STOC)•May 31, 2009•52 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•64 citations
In modern coding theory, linear code constructions are mainly used. Their properties and fundamental theoretical limits are well studied, and they are successfully applied to different classes of problems. Until now, non-linear codes did not attract much attention from specialists because linear structures have coped with their tasks and have the required research tools developed earlier. But in a series of works devoted to the study of codes with graceful degradation, H. Roozbehani, and Y. Polyanskiy proposed the construction of non-linear low-density majority codes (LDMC) and effective encoding and decoding algorithms for them. Moreover, they showed that LDMC has a lower bit error rate (BER) than any linear code in the error-reducing regime for the binary erasure channel (BEC). Given this motivation, we consider non-linear sparse-graph codes (a generalized version of LDMC) and investigate their performance in the AWGN channel. For this class of codes, we proposed efficient generalized BP-based and LP-based decoding algorithms. We accurately estimated BER under ML decoding of non-linear codes based on the LP-based decoder. Also, by simulation, we carried out the analysis and comparison of performances of various non-linear codes.
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.
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.
Polar codes are the first codes to provably achieve capacity on the symmetric binary-input discrete memoryless channel (B-DMC) with low encoding and decoding complexity. The parity check matrix of polar codes is high-density and we show that linear program (LP) decoding fails on the fundamental polytope of the parity check matrix. The recursive structure of the code permits a sparse factor graph representation. We define a new polytope based on the fundamental polytope of the sparse graph representation. This new polytope P is defined in a space of dimension O(N logN) where N is the block length. We prove that the projection of P in the original space is tighter than the fundamental polytope based on the parity check matrix. The LP decoder over P obtains the ML-certificate property. In the case of the binary erasure channel (BEC), the new LP decoder is equivalent to the belief propagation (BP) decoder operating on the sparse factor graph representation, and hence achieves capacity. Simulation results of SC (successive cancellation) decoding, LP decoding over tightened polytopes, and (ML) maximum likelihood decoding are provided. For channels other than the BEC, we discuss why LP decoding over P with a linear objective function is insufficient.
Linear programming decoding for low-density parity check codes (and related domains such as compressed sensing) has received increased attention over recent years because of its practical performance --coming close to that of iterative decoding algorithms--- and its amenability to finite-blocklength analysis. Several works starting with the work of Feldman et al. showed how to analyze LP decoding using properties of expander graphs. This line of analysis works for only low error rates, about a couple of orders of magnitude lower than the empirically observed performance. It is possible to do better for the case of random noise, as shown by Daskalakis et al. and Koetter and Vontobel. Building on work of Koetter and Vontobel, we obtain a novel understanding of LP decoding, which allows us to establish a 0.05-fraction of correctable errors for rate-1/2 codes; this comes very close to the performance of iterative decoders and is significantly higher than the best previously noted correctable bit error rate for LP decoding. Unlike other techniques, our analysis directly works with the primal linear program and exploits an explicit connection between LP decoding and message passing algorithms.
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.