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

Signal Processing and Communications Applications Conference (SIU)

A heuristic method for adaptive linear programming decoding

Abdullah Sarıduman, Alí Emre Pusane, Z. Caner Taşkın

Published May 1, 2016• 1 citation
Publisher

Abstract

Adaptive linear programming (ALP) decoders are mainly used for decoding low-density parity-check (LDPC) codes. The principle of ALP decoders is based on generating redundant-parity check equations, which could eliminate fractional solutions of linear programming (LP) decoders. These generated redundant parity check equations increase the error rate performance of decoder. In this paper, LP model is defined with auxiliary variables to facilitate finding redundant-parity check equations, and redundant parity check equations are searched over proposed LP model with a heuristic method. Simulation results demonstrate that the proposed algorithm could find redundant-parity check equations in a shorter time than other ALP decoders.

DOI
10.1109/siu.2016.7496077

Related papers

Adaptive linear programming for decoding LDPC codes

Abdullah Sarıduman, Alí Emre Pusane, Z. Caner Taşkın

When linear programming is used to decode low-density parity-check (LDPC) codes, the outcome is a codeword or a pseudocodeword that contains fractional symbol values. It is possible to make pseudocodewords infeasible and increase the performance of linear programming decoders by generating redundant parity check equations. In this paper, redundant parity check equations that can eliminate pseudocodewords are searched using an integer programming based optimization approach. We show that the generated parity check equations increase the performance of the adaptive linear programming decoder and that its performance can converge that of a maximum-likelihood decoder.

Signal Processing and Communications Applications Conference (SIU)•Apr 1, 2014•2 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

Adaptive Cut Generation Algorithm for Improved Linear Programming Decoding of Binary Linear Codes

Xiaojie Zhang, Student Member, Paul H. Siegel

Abstract—Linear programming (LP) decoding approximates 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 box constraints together with a set of linear inequalities called “parity inequalities ” that are derived from the constraints represented by the rows of a parity-check matrix of the code and can be added iteratively and adaptively. In this paper, we first derive a new necessary condition and a new sufficient condition for a violated parity inequality constraint, or “cut, ” at a point in the unit hypercube. Then, we propose a new and effective algorithm to generate parity inequalities derived from certain additional redundant parity check (RPC) constraints that can eliminate pseudocodewords produced by the LP decoder, often significantly improving the decoder error-rate performance. The cut-generating algorithm is based upon a specific transformation of an initial parity-check matrix of the linear block code. We also design two variations of the proposed decoder to make it more efficient when it is combined with the new cut-generating algorithm. Simulation results for several low-density parity-check (LDPC) codes demonstrate that the proposed decoding algorithms significantly narrow the performance gap between LP decoding and ML decoding. Index Terms—Iterative decoding, linear codes, linear programming (LP) decoding, low-density parity-check (LDPC) codes, maximum-likelihood (ML) decoding, pseudocodewords. I.

•Jan 1, 2012•58 citations

Adaptive Cut Generation Algorithm for Improved Linear Programming Decoding of Binary Linear Codes

Xiaojie Zhang, Paul H. Siegel

Linear programming (LP) decoding approximates 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 box constraints together with a set of linear inequalities called “parity inequalities” that are derived from the constraints represented by the rows of a parity-check matrix of the code and can be added iteratively and adaptively. In this paper, we first derive a new necessary condition and a new sufficient condition for a violated parity inequality constraint, or “cut,” at a point in the unit hypercube. Then, we propose a new and effective algorithm to generate parity inequalities derived from certain additional redundant parity check (RPC) constraints that can eliminate pseudocodewords produced by the LP decoder, often significantly improving the decoder error-rate performance. The cut-generating algorithm is based upon a specific transformation of an initial parity-check matrix of the linear block code. We also design two variations of the proposed decoder to make it more efficient when it is combined with the new cut-generating algorithm. Simulation results for several low-density parity-check (LDPC) codes demonstrate that the proposed decoding algorithms significantly narrow the performance gap between LP decoding and ML decoding.

arXiv:1105.0703•IEEE Transactions on Information Theory•Jun 16, 2012•59 citations

Multistep linear programming approaches for decoding low-density parity-check codes

Haiyang Liu, Lianrong Ma, Jie Chen

The problem of improving the performance of linear programming (LP) decoding of low-density parity-check (LDPC) codes is considered in this paper. A multistep linear programming (MLP) algorithm was developed for decoding LDPC codes that includes a slight increase in computational complexity. The MLP decoder adaptively adds new constraints which are compatible with a selected check node to refine the results when an error is reported by the original LP decoder. The MLP decoder result is shown to have the maximum-likelihood (ML) certificate property. Simulations with moderate block length LOpe codes suggest that the M LP decoder gives better performance than both the original LP decoder and the conventional sum-product (SP) decoder.

Tsinghua Science & Technology•Oct 1, 2009•2 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•11 citations
Adaptive linear programming (ALP) decoders are mainly used for decoding low-density parity-check (LDPC) codes. The principle of ALP decoders is based on generating redundant-parity check equations, which could eliminate fractional solutions of linear programming (LP) decoders. These generated redundant parity check equations increase the error rate performance of decoder. In this paper, LP model is defined with auxiliary variables to facilitate finding redundant-parity check equations, and redundant parity check equations are searched over proposed LP model with a heuristic method. Simulation results demonstrate that the proposed algorithm could find redundant-parity check equations in a shorter time than other ALP decoders.
When linear programming is used to decode low-density parity-check (LDPC) codes, the outcome is a codeword or a pseudocodeword that contains fractional symbol values. It is possible to make pseudocodewords infeasible and increase the performance of linear programming decoders by generating redundant parity check equations. In this paper, redundant parity check equations that can eliminate pseudocodewords are searched using an integer programming based optimization approach. We show that the generated parity check equations increase the performance of the adaptive linear programming decoder and that its performance can converge that of a maximum-likelihood decoder.
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.
Abstract—Linear programming (LP) decoding approximates 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 box constraints together with a set of linear inequalities called “parity inequalities ” that are derived from the constraints represented by the rows of a parity-check matrix of the code and can be added iteratively and adaptively. In this paper, we first derive a new necessary condition and a new sufficient condition for a violated parity inequality constraint, or “cut, ” at a point in the unit hypercube. Then, we propose a new and effective algorithm to generate parity inequalities derived from certain additional redundant parity check (RPC) constraints that can eliminate pseudocodewords produced by the LP decoder, often significantly improving the decoder error-rate performance. The cut-generating algorithm is based upon a specific transformation of an initial parity-check matrix of the linear block code. We also design two variations of the proposed decoder to make it more efficient when it is combined with the new cut-generating algorithm. Simulation results for several low-density parity-check (LDPC) codes demonstrate that the proposed decoding algorithms significantly narrow the performance gap between LP decoding and ML decoding. Index Terms—Iterative decoding, linear codes, linear programming (LP) decoding, low-density parity-check (LDPC) codes, maximum-likelihood (ML) decoding, pseudocodewords. I.
Linear programming (LP) decoding approximates 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 box constraints together with a set of linear inequalities called “parity inequalities” that are derived from the constraints represented by the rows of a parity-check matrix of the code and can be added iteratively and adaptively. In this paper, we first derive a new necessary condition and a new sufficient condition for a violated parity inequality constraint, or “cut,” at a point in the unit hypercube. Then, we propose a new and effective algorithm to generate parity inequalities derived from certain additional redundant parity check (RPC) constraints that can eliminate pseudocodewords produced by the LP decoder, often significantly improving the decoder error-rate performance. The cut-generating algorithm is based upon a specific transformation of an initial parity-check matrix of the linear block code. We also design two variations of the proposed decoder to make it more efficient when it is combined with the new cut-generating algorithm. Simulation results for several low-density parity-check (LDPC) codes demonstrate that the proposed decoding algorithms significantly narrow the performance gap between LP decoding and ML decoding.
The problem of improving the performance of linear programming (LP) decoding of low-density parity-check (LDPC) codes is considered in this paper. A multistep linear programming (MLP) algorithm was developed for decoding LDPC codes that includes a slight increase in computational complexity. The MLP decoder adaptively adds new constraints which are compatible with a selected check node to refine the results when an error is reported by the original LP decoder. The MLP decoder result is shown to have the maximum-likelihood (ML) certificate property. Simulations with moderate block length LOpe codes suggest that the M LP decoder gives better performance than both the original LP decoder and the conventional sum-product (SP) decoder.
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.