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 Communications Letters

A Generator-Matrix-Based Approach for Adaptively Generating Cut-Inducing Redundant Parity Checks

Hossein Falsafain, Sayyed Rasoul Mousavi

Published Feb 16, 2016• 2 citations
Publisher

Abstract

A generator matrix (GM)-based approach for adaptively deriving cut-inducing redundant parity checks (RPCs) during the adaptive linear programming decoding algorithm is presented. More precisely speaking, if the decoder gets stuck in a non-integral pseudocodeword, then the resulting RPCs are likely to provide violated forbidden-set inequalities that can separate this non-integral optimal solution from the feasible region. The described approach can be viewed as a GM-based counterpart of the approach proposed by Zhang and Siegel in 2012. For binary linear codes of low rate, while providing the same error-correcting performance, our approach requires much less computational time compared to its analogue.

DOI
10.1109/lcomm.2016.2530706

Related papers

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, 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

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

A heuristic method for adaptive linear programming decoding

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

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.

Signal Processing and Communications Applications Conference (SIU)•May 1, 2016•1 citation

Efficient Linear Programming Decoding of HDPC Codes

Alex Yufit, Asi Lifshitz, Yair Be'ery

We propose several improvements for Linear Programming (LP) decoding algorithms for High Density Parity Check (HDPC) codes. First, we use the automorphism groups of a code to create parity check matrix diversity and to generate valid cuts from redundant parity checks. Second, we propose an efficient mixed integer decoder utilizing the branch and bound method. We further enhance the proposed decoders by removing inactive constraints and by adapting the parity check matrix prior to decoding according to the channel observations. Based on simulation results the proposed decoders achieve near-ML performance with reasonable complexity.

arXiv:0912.3907•IEEE Transactions on Communications•Dec 23, 2010•20 citations
A generator matrix (GM)-based approach for adaptively deriving cut-inducing redundant parity checks (RPCs) during the adaptive linear programming decoding algorithm is presented. More precisely speaking, if the decoder gets stuck in a non-integral pseudocodeword, then the resulting RPCs are likely to provide violated forbidden-set inequalities that can separate this non-integral optimal solution from the feasible region. The described approach can be viewed as a GM-based counterpart of the approach proposed by Zhang and Siegel in 2012. For binary linear codes of low rate, while providing the same error-correcting performance, our approach requires much less computational time compared to its analogue.
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.
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.
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.
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.
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.
We propose several improvements for Linear Programming (LP) decoding algorithms for High Density Parity Check (HDPC) codes. First, we use the automorphism groups of a code to create parity check matrix diversity and to generate valid cuts from redundant parity checks. Second, we propose an efficient mixed integer decoder utilizing the branch and bound method. We further enhance the proposed decoders by removing inactive constraints and by adapting the parity check matrix prior to decoding according to the channel observations. Based on simulation results the proposed decoders achieve near-ML performance with reasonable complexity.