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 International Symposium on Information Theory (ISIT)

Valid inequalities for binary linear codes

Akın Tanatmis, Stefan Ruzika, Horst W. Hamacher, Mayur Punekar, Frank Kienle, Norbert Wehn

Published Jun 1, 2009• 12 citations
Publisher

Abstract

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.

DOI
10.1109/isit.2009.5205846

Related papers

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

We present improvements in linear programming decoding introduced by Feldman et al. with the help of generic integer programming methods. We propose a new IP formulation of the maximum likelihood decoding problem. This formulation makes use of indicator variables which help in detecting violated parity checks immediately. We derive Gomory cuts from our formulation and use them in a separation algorithm to find maximum likelihood codewords. We further propose a novel method of finding cuts induced by redundant parity checks. Under certain circumstances we can guarantee that these RPC cuts are valid and cut off the fractional optimal solutions of LP decoding. We demonstrate the performance of our separation algorithm on two LDPC codes and one BCH code.

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

Numerical Comparison of IP Formulations as ML Decoders

Akın Tanatmis, Stefan Ruzika, Mayur Punekar +1 more

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.

International Conference on Communications•May 1, 2010•7 citations

Minimum distance computation of LDPC codes using a branch and cut algorithm

Ahmet Burak Keha, Tolga M. Duman

We give a branch-and-cut algorithm for finding the minimum distance of a binary linear block code. We give two integer programming (IP) models and study the convex hull of the single constraint relaxation of these IP models. We use the new inequalities as cuts in a branch-and-cut scheme. Finally, we report computational results based on turbo and low density parity check (LDPC) codes that demonstrate the effectiveness of our cuts. We demonstrate that our IP formulation and specific cuts are efficient tools for determining the minimum distance of moderate size linear block codes, specifically, they are very efficient for LDPC codes, and provide us with an additional tool for solving this important problem.

IEEE Transactions on Communications•Mar 30, 2010•20 citations
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.
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 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 present improvements in linear programming decoding introduced by Feldman et al. with the help of generic integer programming methods. We propose a new IP formulation of the maximum likelihood decoding problem. This formulation makes use of indicator variables which help in detecting violated parity checks immediately. We derive Gomory cuts from our formulation and use them in a separation algorithm to find maximum likelihood codewords. We further propose a novel method of finding cuts induced by redundant parity checks. Under certain circumstances we can guarantee that these RPC cuts are valid and cut off the fractional optimal solutions of LP decoding. We demonstrate the performance of our separation algorithm on two LDPC codes and one BCH code.
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 give a branch-and-cut algorithm for finding the minimum distance of a binary linear block code. We give two integer programming (IP) models and study the convex hull of the single constraint relaxation of these IP models. We use the new inequalities as cuts in a branch-and-cut scheme. Finally, we report computational results based on turbo and low density parity check (LDPC) codes that demonstrate the effectiveness of our cuts. We demonstrate that our IP formulation and specific cuts are efficient tools for determining the minimum distance of moderate size linear block codes, specifically, they are very efficient for LDPC codes, and provide us with an additional tool for solving this important problem.