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 Conference on Communications

Numerical Comparison of IP Formulations as ML Decoders

Akın Tanatmis, Stefan Ruzika, Mayur Punekar, Frank Kienle

Published May 1, 2010• 7 citations
Publisher

Abstract

For binary linear codes with short and medium block length ML decoding can be achieved by solving the associated integer programming (IP) problem with a general purpose solver. IP also offers algorithms for computing the minimum distance. In this article, we present several IP formulations and computationally compare them on various LDPC and BCH codes. Most of these formulations are obtained by forcing integrality on linear programming (LP) decoding formulations proposed in the literature.

DOI
10.1109/icc.2010.5502303

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

Valid inequalities for binary linear codes

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

We study an integer programming (IP) based separation approach to find the maximum likelihood (ML) codeword for binary linear codes. An algorithm introduced in Tanatmis et al. is extended and improved with respect to decoding performance without increasing the worst case complexity. This is demonstrated on the LDPC and the BCH code classes. Moreover, we propose an integer programming formulation to calculate the minimum distance of a binary linear code. We exemplarily compute the minimum distance of the (204, 102) LDPC code and the (576, 288) WIMAX code. Using the minimum distance of a code, a new class of valid inequalities is introduced.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2009•12 citations

Advances in mathematical programming-based error-correction decoding

Michael Helmling

The formulation of the decoding problem for linear block codes as an integer program (IP) with a rather tight linear programming (LP) relaxation has made a central part of channel coding accessible for the theory and methods of mathematical optimization, especially integer programming, polyhedral combinatorics and also algorithmic graph theory, since the important class of turbo codes exhibits an inherent graphical structure. We present several novel models, algorithms and theoretical results for error-correction decoding based on mathematical optimization. Our contribution includes a partly combinatorial LP decoder for turbo codes, a fast branch-and-cut algorithm for maximum-likelihood (ML) decoding of arbitrary binary linear codes, a theoretical analysis of the LP decoder's performance for 3-dimensional turbo codes, compact IP models for various heuristic algorithms as well as ML decoding in combination with higher-order modulation, and, finally, first steps towards an implementation of the LP decoder in specialized hardware. The scientific contributions are presented in the form of seven revised reprints of papers that appeared in peer-reviewed international journals or conference proceedings. They are accompanied by an extensive introductory part that reviews the basics of mathematical optimization, coding theory, and the previous results on LP decoding that we rely on afterwards.

•Jul 24, 2015•0 citations

Calculating the minimum distance of linear block codes via Integer Programming

Mayur Punekar, Frank Kienle, Norbert Wehn +3 more

In recent years several authors have used Integer Programming (IP) formulations to model the Maximum Likelihood (ML) decoding problem. IP formulation of the ML decoding problem can be modified to calculate the minimum distance of the code also. The IP based approach for MD calculation can be effectively used for small block length codes. However, it is not known if this approach is useful for the moderate and long length codes used in practice. In this paper we demonstrate the usefulness of the IP based approach for the MD calculation by applying it to practically relevant codes. We calculate either the true MD or upper bounds on the MD for 3GPP LTE turbo codes, WiMax duo-binary turbo codes and WiMax & WiFi low density parity-check codes. A new IP formulation is also introduced to calculate the MD of punctured turbo codes. Along with MD calculation, the same IP formulation is used to find multiplicity of low weight codewords. Our results prove that, the IP based approach can estimate the MD of practically relevant codes fairly quickly and can also provide information about the multiplicity of codewords with a given Hamming weight. Also, the IP based method for the MD calculation is independent of the code used and can easily accommodate puncturing schemes.

International Symposium on Turbo Codes and Iterative Information Processing•Sep 1, 2010•16 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

A New Linear Programming Approach to Decoding Linear Block Codes

Kai Yang, Xiaodong Wang, Jon Feldman

In this paper, we propose a new linear programming formulation for the decoding of general linear block codes. Different from the original formulation given by Feldman, the number of total variables to characterize a parity-check constraint in our formulation is less than twice the degree of the corresponding check node. The equivalence between our new formulation and the original formulation is proven. The new formulation facilitates to characterize the structure of linear block codes, and leads to new decoding algorithms. In particular, we show that any fundamental polytope is simply the intersection of a group of the so-called minimum polytopes, and this simplified formulation allows us to formulate the problem of calculating the minimum Hamming distance of any linear block code as a simple linear integer programming problem with much less auxiliary variables. We then propose a branch-and-bound method to compute a lower bound to the minimum distance of any linear code by solving a corresponding linear integer programming problem. In addition, we prove that, for the family of single parity-check (SPC) product codes, the fractional distance and the pseudodistance are both equal to the minimum distance. Finally, we propose an efficient algorithm for decoding SPC product codes with low complexity and maximum-likelihood (ML) decoding performance.

IEEE Transactions on Information Theory•Feb 29, 2008•78 citations
For binary linear codes with short and medium block length ML decoding can be achieved by solving the associated integer programming (IP) problem with a general purpose solver. IP also offers algorithms for computing the minimum distance. In this article, we present several IP formulations and computationally compare them on various LDPC and BCH codes. Most of these formulations are obtained by forcing integrality on linear programming (LP) decoding formulations proposed in the literature.
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.
We study an integer programming (IP) based separation approach to find the maximum likelihood (ML) codeword for binary linear codes. An algorithm introduced in Tanatmis et al. is extended and improved with respect to decoding performance without increasing the worst case complexity. This is demonstrated on the LDPC and the BCH code classes. Moreover, we propose an integer programming formulation to calculate the minimum distance of a binary linear code. We exemplarily compute the minimum distance of the (204, 102) LDPC code and the (576, 288) WIMAX code. Using the minimum distance of a code, a new class of valid inequalities is introduced.
The formulation of the decoding problem for linear block codes as an integer program (IP) with a rather tight linear programming (LP) relaxation has made a central part of channel coding accessible for the theory and methods of mathematical optimization, especially integer programming, polyhedral combinatorics and also algorithmic graph theory, since the important class of turbo codes exhibits an inherent graphical structure. We present several novel models, algorithms and theoretical results for error-correction decoding based on mathematical optimization. Our contribution includes a partly combinatorial LP decoder for turbo codes, a fast branch-and-cut algorithm for maximum-likelihood (ML) decoding of arbitrary binary linear codes, a theoretical analysis of the LP decoder's performance for 3-dimensional turbo codes, compact IP models for various heuristic algorithms as well as ML decoding in combination with higher-order modulation, and, finally, first steps towards an implementation of the LP decoder in specialized hardware. The scientific contributions are presented in the form of seven revised reprints of papers that appeared in peer-reviewed international journals or conference proceedings. They are accompanied by an extensive introductory part that reviews the basics of mathematical optimization, coding theory, and the previous results on LP decoding that we rely on afterwards.
In recent years several authors have used Integer Programming (IP) formulations to model the Maximum Likelihood (ML) decoding problem. IP formulation of the ML decoding problem can be modified to calculate the minimum distance of the code also. The IP based approach for MD calculation can be effectively used for small block length codes. However, it is not known if this approach is useful for the moderate and long length codes used in practice. In this paper we demonstrate the usefulness of the IP based approach for the MD calculation by applying it to practically relevant codes. We calculate either the true MD or upper bounds on the MD for 3GPP LTE turbo codes, WiMax duo-binary turbo codes and WiMax & WiFi low density parity-check codes. A new IP formulation is also introduced to calculate the MD of punctured turbo codes. Along with MD calculation, the same IP formulation is used to find multiplicity of low weight codewords. Our results prove that, the IP based approach can estimate the MD of practically relevant codes fairly quickly and can also provide information about the multiplicity of codewords with a given Hamming weight. Also, the IP based method for the MD calculation is independent of the code used and can easily accommodate puncturing schemes.
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.
In this paper, we propose a new linear programming formulation for the decoding of general linear block codes. Different from the original formulation given by Feldman, the number of total variables to characterize a parity-check constraint in our formulation is less than twice the degree of the corresponding check node. The equivalence between our new formulation and the original formulation is proven. The new formulation facilitates to characterize the structure of linear block codes, and leads to new decoding algorithms. In particular, we show that any fundamental polytope is simply the intersection of a group of the so-called minimum polytopes, and this simplified formulation allows us to formulate the problem of calculating the minimum Hamming distance of any linear block code as a simple linear integer programming problem with much less auxiliary variables. We then propose a branch-and-bound method to compute a lower bound to the minimum distance of any linear code by solving a corresponding linear integer programming problem. In addition, we prove that, for the family of single parity-check (SPC) product codes, the fractional distance and the pseudodistance are both equal to the minimum distance. Finally, we propose an efficient algorithm for decoding SPC product codes with low complexity and maximum-likelihood (ML) decoding performance.