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

Improved Maximum-Likelihood Decoding Using Sparse Parity-Check Matrices

Florian Gensheimer, Tobias Dietz, Stefan Ruzika, Kira Kraft, Norbert Wehn

Published Jun 1, 2018• 6 citations
Publisher

Abstract

Maximum-likelihood (ML) decoding is an important and powerful method in communications to obtain the optimal performance of a channel code. However, ML decoding is a challenging problem whose complexity grows exponentially with the blocklength of the code, making it unfeasible to decode optimally for large codes. In this paper, we present a new approach to accelerate ML decoding by minimizing the number of ones in the code's underlying matrix representation. We formulate this minimization problem as an integer program and use a heuristic algorithm to solve it. Using these minimized matrices, we significantly reduce the runtime of different ML decoders for various codes, resulting in speedups of up to 81% compared to the runtime on the original matrices.

DOI
10.1109/ict.2018.8464884

Related papers

A Separation Algorithm for Improved LP-Decoding of Linear Block Codes

Akın Tanatmis, Stefan Ruzika, Horst W. Hamacher +3 more

Maximum Likelihood (ML) decoding is the optimal decoding algorithm for arbitrary linear block codes and can be written as an Integer Programming (IP) problem. Feldman et al. relaxed this IP problem and presented Linear Programming (LP) based decoding algorithm for linear block codes. In this paper, we propose a new IP formulation of the ML decoding problem and solve the IP with generic methods. The formulation uses indicator variables to detect violated parity checks. We derive Gomory cuts from our formulation and use them in a separation algorithm to find ML codewords. We further propose an efficient method of finding cuts induced by redundant parity checks (RPC). Under certain circumstances we can guarantee that these RPC cuts are valid and cut off the fractional optimal solutions of LP decoding. We demonstrate on two LDPC codes and one BCH code that our separation algorithm performs significantly better than LP decoding.

arXiv:0812.2559•Dec 13, 2008•2 citations

A Separation Algorithm for Improved LP-Decoding of Linear Block Codes

Akın Tanatmis, Stefan Ruzika, Horst W. Hamacher +3 more

Maximum likelihood (ML) decoding is the optimal decoding algorithm for arbitrary linear block codes and can be written as an integer programming (IP) problem. Feldman relaxed this IP problem and presented linear programming (LP) based decoding. In this paper, we propose a new separation algorithm to improve the error-correcting performance of LP decoding for binary linear block codes. We use an IP formulation with indicator variables that help in detecting the violated parity checks. We derive Gomory cuts from the IP and use them in our separation algorithm. An efficient method of finding cuts induced by redundant parity checks (RPC) is also proposed. Under certain circumstances we can guarantee that these RPC cuts are valid and cut off the fractional optimal solutions of LP decoding. It is demonstrated on three LDPC codes and two BCH codes that our separation algorithm performs significantly better than LP decoding and belief propagation (BP) decoding.

IEEE Transactions on Information Theory•Jun 23, 2010•48 citations

Maximum-Likelihood Channel Decoding with Quantum Annealing Machine

Naoki Ide, Tetsuya Asayama, Hiroshi Ueno +1 more

We formulate maximum likelihood (ML) channel decoding as a quadratic unconstraint binary optimization (QUBO) and simulate the decoding by the current commercial quantum annealing machine, D-Wave 2000Q. We prepared two implementations with Ising model formulations, generated from the generator matrix and the parity-check matrix respectively. We evaluated these implementations of ML decoding for low-density parity-check (LDPC) codes, analyzing the number of spins and connections and comparing the decoding performance with belief propagation (BP) decoding and brute-force ML decoding with classical computers. The results show that these implementations are superior to BP decoding in relatively short length codes, and while the performance in the long length codes deteriorates, the implementation from the parity-check matrix formulation still works up to 1k length with fewer spins and connections than that of the generator matrix formulation due to the sparseness of parity-check matrices of LDPC.

arXiv:2007.08689•Jul 16, 2020•14 citations

Pivoting Algorithms for Maximum Likelihood Decoding of LDPC Codes over Erasure Channels

Gianluigi Liva, Balázs Matuz, Enrico Paolini +1 more

This paper investigates efficient maximum-likelihood (ML) decoding algorithms for low-density parity-check (LDPC) codes over erasure channels. In particular, enhancements to a previously proposed structured Gaussian elimination approach are presented. The improvements are achieved by developing a set of algorithms, here referred to as pivoting algorithms, aiming to limit the average number of reference variables (or pivots) from which the erased symbols can be recovered. Four pivoting algorithms are compared, which exhibit different trade-offs between the complexity of the pivoting phase and the average number of pivots. Numerical results on the performance of LDPC codes under ML erasure decoding complete the analysis, confirming that a near-optimum performance can be obtained with an affordable decoding complexity, up to very high data rates. For example, for one of the presented algorithms, a software implementation has been developed, which is capable to provide data rates above 1.5 Gbps on a commercial computing platform.

Globecom•Nov 1, 2009•22 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 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
Maximum-likelihood (ML) decoding is an important and powerful method in communications to obtain the optimal performance of a channel code. However, ML decoding is a challenging problem whose complexity grows exponentially with the blocklength of the code, making it unfeasible to decode optimally for large codes. In this paper, we present a new approach to accelerate ML decoding by minimizing the number of ones in the code's underlying matrix representation. We formulate this minimization problem as an integer program and use a heuristic algorithm to solve it. Using these minimized matrices, we significantly reduce the runtime of different ML decoders for various codes, resulting in speedups of up to 81% compared to the runtime on the original matrices.
Maximum Likelihood (ML) decoding is the optimal decoding algorithm for arbitrary linear block codes and can be written as an Integer Programming (IP) problem. Feldman et al. relaxed this IP problem and presented Linear Programming (LP) based decoding algorithm for linear block codes. In this paper, we propose a new IP formulation of the ML decoding problem and solve the IP with generic methods. The formulation uses indicator variables to detect violated parity checks. We derive Gomory cuts from our formulation and use them in a separation algorithm to find ML codewords. We further propose an efficient method of finding cuts induced by redundant parity checks (RPC). Under certain circumstances we can guarantee that these RPC cuts are valid and cut off the fractional optimal solutions of LP decoding. We demonstrate on two LDPC codes and one BCH code that our separation algorithm performs significantly better than LP decoding.
Maximum likelihood (ML) decoding is the optimal decoding algorithm for arbitrary linear block codes and can be written as an integer programming (IP) problem. Feldman relaxed this IP problem and presented linear programming (LP) based decoding. In this paper, we propose a new separation algorithm to improve the error-correcting performance of LP decoding for binary linear block codes. We use an IP formulation with indicator variables that help in detecting the violated parity checks. We derive Gomory cuts from the IP and use them in our separation algorithm. An efficient method of finding cuts induced by redundant parity checks (RPC) is also proposed. Under certain circumstances we can guarantee that these RPC cuts are valid and cut off the fractional optimal solutions of LP decoding. It is demonstrated on three LDPC codes and two BCH codes that our separation algorithm performs significantly better than LP decoding and belief propagation (BP) decoding.
We formulate maximum likelihood (ML) channel decoding as a quadratic unconstraint binary optimization (QUBO) and simulate the decoding by the current commercial quantum annealing machine, D-Wave 2000Q. We prepared two implementations with Ising model formulations, generated from the generator matrix and the parity-check matrix respectively. We evaluated these implementations of ML decoding for low-density parity-check (LDPC) codes, analyzing the number of spins and connections and comparing the decoding performance with belief propagation (BP) decoding and brute-force ML decoding with classical computers. The results show that these implementations are superior to BP decoding in relatively short length codes, and while the performance in the long length codes deteriorates, the implementation from the parity-check matrix formulation still works up to 1k length with fewer spins and connections than that of the generator matrix formulation due to the sparseness of parity-check matrices of LDPC.
This paper investigates efficient maximum-likelihood (ML) decoding algorithms for low-density parity-check (LDPC) codes over erasure channels. In particular, enhancements to a previously proposed structured Gaussian elimination approach are presented. The improvements are achieved by developing a set of algorithms, here referred to as pivoting algorithms, aiming to limit the average number of reference variables (or pivots) from which the erased symbols can be recovered. Four pivoting algorithms are compared, which exhibit different trade-offs between the complexity of the pivoting phase and the average number of pivots. Numerical results on the performance of LDPC codes under ML erasure decoding complete the analysis, confirming that a near-optimum performance can be obtained with an affordable decoding complexity, up to very high data rates. For example, for one of the presented algorithms, a software implementation has been developed, which is capable to provide data rates above 1.5 Gbps on a commercial computing platform.
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 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.