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

Decoding linear codes via optimization and graph-based techniques

Mohammad Hossein Taghavi

Published Jan 1, 2008• 1 citation
OpenAlex

Abstract

Low-density parity-check (LDPC) codes have made it possible to communicate at information rates very close to the Shannon capacity by combining sparsity with quasi- randomness, which enables the use of low-complexity iterative message-passing (IMP) decoders. So far, most systematic studies of IMP decoders have focused on evaluating the average performance of random ensembles of LDPC codes with infinite length. However, the statistical nature of IMP algorithms does not seem very suitable for rigorous analysis the decoding of individual finite-length codes. The need for finite-length studies are most critical in applications such as data storage, where the required decoding error rate is too low to be verifiable by simulation. As an alternative to IMP algorithms, linear programming (LP) decoding is based on relaxing the optimal decoding into a linear optimization. The geometric nature of this approach makes it more amenable to deterministic finite-length analysis than IMP decoding. On the other hand, LP decoding is computationally more complex than IMP decoding, due to both the large number of constraints in the relaxed problem, and the inefficiency of using general -purpose LP solvers. In this dissertation, we study several aspects of LP decoding, starting by some steps toward reducing its complexity. We introduce an adaptive implementation of LP decoding, where the relaxed problem is replaced by a sequence of subproblems of much smaller size, resulting in a complexity reduction by orders of magnitude. This is followed by a sparse implementation of an interior-point LP solver which exploits the structure of the decoding problem. We further propose a cutting- plane approach to improve the error-correcting capability of LP decoding. Along the way, several properties are proved for LP decoding and its proposed variations. We continue by investigating the application of an optimization-based approach to decoding linear codes in the presence of intersymbol interference (ISI). By relaxing the optimal detection problem into a linear program, we derive a new graphical representation for the ISI channel, which can be used for combined equalization and decoding by LP or IMP decoders. Finally, in a separate piece of work, we study the effect of nonlinearities on the multiuser capacity of optical fibers

Related papers

LDPC Codes--Structural Analysis and Decoding Techniques.

Xiaojie Zhang

Low-density parity-check (LDPC) codes have been the focus of much research over the past decade thanks to their near Shannon limit performance and to their efficient message- passing (MP) decoding algorithms. However, the error floor phenomenon observed in MP decoding, which manifests itself as an abrupt change in the slope of the error-rate curve, has hindered the adoption of LDPC codes and MP decoders in some applications requiring very low error rates. As an alternative to MP decoding, linear programming (LP) decoding is an approximation to maximum-likelihood decoding by relaxing the optimal decoding problem into a linear optimization problem. It has been noticed that, when the symbols error probability in channel output is low, LP decoding has superior error correction performance. However, due to the inefficiency of general- purpose LP solvers which are not optimized for solving LP problems, LP decoding is computationally more complex than MP decoding, especially for codes of large block size. In this dissertation, we first design an efficient exhaustive search algorithm to find all small error-prone substructures, some of which are commonly blamed for certain decoding failures of MP decoding. Then, we investigate the cause of error floors in LDPC codes from the perspective of the MP decoder implementation, with special attention to limitations that decrease the numerical accuracy of messages passed during decoding, and propose a quantization method for fixed-point implementation of MP decoding which significantly improves the error-floor performance by overcoming the limitations of standard quantization rules. For LP decoding, we improve the error-correcting capability of LP decoding by using an effective algorithm to generate additional redundant parity-check constraints which eliminate certain undesired solutions to LP decoding problem. We further propose an efficient message-passing algorithm to solve the LP decoding problem. This algorithm is based on the alternating direction method of multipliers (ADMM), a classic technique in convex optimization theory, and our key contribution is a novel, efficient projection algorithm that can improve the decoding speed of the ADMM- based LP decoder. The last part of this dissertation is a separate piece of work on optimizing video transmission over distributed cognitive radio network

ProQuest LLC eBooks•Jan 1, 2012•6 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

Message-Passing Algorithms and Improved LP Decoding

Sanjeev Arora, Constantinos Daskalakis, David Steurer

Linear programming (LP) 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 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 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-½ 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. Our analysis exploits an explicit connection between LP decoding and message-passing algorithms and, unlike other techniques, directly works with the primal linear program. An interesting byproduct of our method is a notion of a “locally optimal” solution that we show to always be globally optimal (i.e., it is the nearest codeword). Such a solution can in fact be found in near-linear time by a “reweighted” version of the min-sum algorithm, obviating the need for LP. Our analysis implies, in particular, that this reweighted version of the min-sum decoder corrects up to a 0.05 fraction of errors.

IEEE Transactions on Information Theory•Jul 13, 2012•23 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

Efficient implementation of linear programming decoding

Mohammad Hossein Taghavi, Amin Shokrollahi, Paul H. Siegel

This paper explores ideas for fast linear programming (LP) decoding of low-density parity-check (LDPC) codes. We first propose a modification of adaptive LP decoding, and prove that it performs LP decoding by solving a number of linear programs that contain at most one linear constraint derived from each of the parity-check constraints. Then, as a step toward designing an efficient LP solver that exploits the structure of LDPC codes, 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 algorithms is to solve a (usually ill-conditioned) system of linear equations for finding the step direction, we propose a framework for designing preconditioners to be used with the iterative methods for solving these systems. The effectiveness of the proposed approach is demonstrated via both analytical and simulation results.

Allerton Conference on Communication, Control, and Computing•Sep 1, 2008•13 citations

Short-length Low-density Parity-check Codes: Construction and Decoding Algorithms

Cornelius T. Healy

Error control coding is an essential part of modern communications systems. LDPC codes have been demonstrated to offer performance near the fundamental limits of channels corrupted by random noise. Optimal maximum likelihood decoding of LDPC codes is too complex to be practically useful even at short block lengths and so a graph-based message passing decoder known as the belief propagation algorithm is used instead. In fact, on graphs without closed paths known as cycles the iterative message passing decoding is known to be optimal and may converge in a single iteration, although identifying the message update schedule which allows single-iteration convergence is not trivial. At finite block lengths graphs without cycles have poor minimum distance properties and perform poorly even under optimal decoding. LDPC codes with large block length have been demonstrated to offer performance close to that predicted for codes of infinite length, as the cycles present in the graph are quite long. In this thesis, LDPC codes of shorter length are considered as they offer advantages in terms of latency and complexity, at the cost of performance degradation from the increased number of short cycles in the graph. For these shorter LDPC codes, the problems considered are: \n \nFirst, improved construction of structured and unstructured LDPC code graphs of short length with a view to reducing the harmful effects of the cycles on error rate performance, based on knowledge of the decoding process. Structured code graphs are particularly interesting as they allow benefits in encoding and decoding complexity and speed. Secondly, the design and construction of LDPC codes for the block fading channel, a particularly challenging scenario from the point of view of error control code design. Both established and novel classes of codes for the channel are considered. Finally the decoding of LDPC codes by the belief propagation algorithm is considered, in particular the scheduling of messages passed in the iterative decoder. A knowledge-aided approach is developed based on message reliabilities and residuals to allow fast convergence and significant improvements in error rate performance.

•Jul 1, 2014•4 citations
Low-density parity-check (LDPC) codes have made it possible to communicate at information rates very close to the Shannon capacity by combining sparsity with quasi- randomness, which enables the use of low-complexity iterative message-passing (IMP) decoders. So far, most systematic studies of IMP decoders have focused on evaluating the average performance of random ensembles of LDPC codes with infinite length. However, the statistical nature of IMP algorithms does not seem very suitable for rigorous analysis the decoding of individual finite-length codes. The need for finite-length studies are most critical in applications such as data storage, where the required decoding error rate is too low to be verifiable by simulation. As an alternative to IMP algorithms, linear programming (LP) decoding is based on relaxing the optimal decoding into a linear optimization. The geometric nature of this approach makes it more amenable to deterministic finite-length analysis than IMP decoding. On the other hand, LP decoding is computationally more complex than IMP decoding, due to both the large number of constraints in the relaxed problem, and the inefficiency of using general -purpose LP solvers. In this dissertation, we study several aspects of LP decoding, starting by some steps toward reducing its complexity. We introduce an adaptive implementation of LP decoding, where the relaxed problem is replaced by a sequence of subproblems of much smaller size, resulting in a complexity reduction by orders of magnitude. This is followed by a sparse implementation of an interior-point LP solver which exploits the structure of the decoding problem. We further propose a cutting- plane approach to improve the error-correcting capability of LP decoding. Along the way, several properties are proved for LP decoding and its proposed variations. We continue by investigating the application of an optimization-based approach to decoding linear codes in the presence of intersymbol interference (ISI). By relaxing the optimal detection problem into a linear program, we derive a new graphical representation for the ISI channel, which can be used for combined equalization and decoding by LP or IMP decoders. Finally, in a separate piece of work, we study the effect of nonlinearities on the multiuser capacity of optical fibers
Low-density parity-check (LDPC) codes have been the focus of much research over the past decade thanks to their near Shannon limit performance and to their efficient message- passing (MP) decoding algorithms. However, the error floor phenomenon observed in MP decoding, which manifests itself as an abrupt change in the slope of the error-rate curve, has hindered the adoption of LDPC codes and MP decoders in some applications requiring very low error rates. As an alternative to MP decoding, linear programming (LP) decoding is an approximation to maximum-likelihood decoding by relaxing the optimal decoding problem into a linear optimization problem. It has been noticed that, when the symbols error probability in channel output is low, LP decoding has superior error correction performance. However, due to the inefficiency of general- purpose LP solvers which are not optimized for solving LP problems, LP decoding is computationally more complex than MP decoding, especially for codes of large block size. In this dissertation, we first design an efficient exhaustive search algorithm to find all small error-prone substructures, some of which are commonly blamed for certain decoding failures of MP decoding. Then, we investigate the cause of error floors in LDPC codes from the perspective of the MP decoder implementation, with special attention to limitations that decrease the numerical accuracy of messages passed during decoding, and propose a quantization method for fixed-point implementation of MP decoding which significantly improves the error-floor performance by overcoming the limitations of standard quantization rules. For LP decoding, we improve the error-correcting capability of LP decoding by using an effective algorithm to generate additional redundant parity-check constraints which eliminate certain undesired solutions to LP decoding problem. We further propose an efficient message-passing algorithm to solve the LP decoding problem. This algorithm is based on the alternating direction method of multipliers (ADMM), a classic technique in convex optimization theory, and our key contribution is a novel, efficient projection algorithm that can improve the decoding speed of the ADMM- based LP decoder. The last part of this dissertation is a separate piece of work on optimizing video transmission over distributed cognitive radio network
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.
Linear programming (LP) 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 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 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-½ 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. Our analysis exploits an explicit connection between LP decoding and message-passing algorithms and, unlike other techniques, directly works with the primal linear program. An interesting byproduct of our method is a notion of a “locally optimal” solution that we show to always be globally optimal (i.e., it is the nearest codeword). Such a solution can in fact be found in near-linear time by a “reweighted” version of the min-sum algorithm, obviating the need for LP. Our analysis implies, in particular, that this reweighted version of the min-sum decoder corrects up to a 0.05 fraction of errors.
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.
This paper explores ideas for fast linear programming (LP) decoding of low-density parity-check (LDPC) codes. We first propose a modification of adaptive LP decoding, and prove that it performs LP decoding by solving a number of linear programs that contain at most one linear constraint derived from each of the parity-check constraints. Then, as a step toward designing an efficient LP solver that exploits the structure of LDPC codes, 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 algorithms is to solve a (usually ill-conditioned) system of linear equations for finding the step direction, we propose a framework for designing preconditioners to be used with the iterative methods for solving these systems. The effectiveness of the proposed approach is demonstrated via both analytical and simulation results.
Error control coding is an essential part of modern communications systems. LDPC codes have been demonstrated to offer performance near the fundamental limits of channels corrupted by random noise. Optimal maximum likelihood decoding of LDPC codes is too complex to be practically useful even at short block lengths and so a graph-based message passing decoder known as the belief propagation algorithm is used instead. In fact, on graphs without closed paths known as cycles the iterative message passing decoding is known to be optimal and may converge in a single iteration, although identifying the message update schedule which allows single-iteration convergence is not trivial. At finite block lengths graphs without cycles have poor minimum distance properties and perform poorly even under optimal decoding. LDPC codes with large block length have been demonstrated to offer performance close to that predicted for codes of infinite length, as the cycles present in the graph are quite long. In this thesis, LDPC codes of shorter length are considered as they offer advantages in terms of latency and complexity, at the cost of performance degradation from the increased number of short cycles in the graph. For these shorter LDPC codes, the problems considered are: \n \nFirst, improved construction of structured and unstructured LDPC code graphs of short length with a view to reducing the harmful effects of the cycles on error rate performance, based on knowledge of the decoding process. Structured code graphs are particularly interesting as they allow benefits in encoding and decoding complexity and speed. Secondly, the design and construction of LDPC codes for the block fading channel, a particularly challenging scenario from the point of view of error control code design. Both established and novel classes of codes for the channel are considered. Finally the decoding of LDPC codes by the belief propagation algorithm is considered, in particular the scheduling of messages passed in the iterative decoder. A knowledge-aided approach is developed based on message reliabilities and residuals to allow fast convergence and significant improvements in error rate performance.