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

Ahmet B. Keha, Tolga M. Duman

Research output: Contribution to journalArticlepeer-review

15 Scopus citations


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.

Original languageEnglish (US)
Article number5439310
Pages (from-to)1072-1079
Number of pages8
JournalIEEE Transactions on Communications
Issue number4
StatePublished - Apr 2010


  • Branchand-cut
  • Linear block codes
  • Low density parity checkcodes
  • Mixed-integer programming modelling
  • Turbo codes

ASJC Scopus subject areas

  • Electrical and Electronic Engineering


Dive into the research topics of 'Minimum distance computation of LDPC codes using a branch and cut algorithm'. Together they form a unique fingerprint.

Cite this