Heuristic algorithms for constructing binary constant weight codes

Derek Smith, R. Montemanni

Research output: Contribution to journalArticlepeer-review

1 Downloads (Pure)


Constant weight binary codes are used in a number of applications. Constructions based on mathematical structure are known for many codes. However, heuristic constructions unrelated to any mathematical structure can become of greater importance when the parameters of the code are larger. This paper considers the problem of finding constant weight codes with the maximum number of codewords from a purely algorithmic perspective. A set of heuristic and metaheuristic methods is presented and developed into a variable neighborhood search framework. The proposed method is applied to 383 previously studied cases with lengths between 29 and 63. For these cases it generates 153 new codes, with significantly increased numbers of codewords in comparison with existing constructions. For 10 of these new codes the number of codewords meets a known upper bound, and so these 10 codes are optimal. As well as the ability to generate new best codes, the approach has the advantage that it is a single method capable of addressing many sets of parameters in a uniform way.
Original languageEnglish
Pages (from-to)4651 - 4656
Number of pages5
JournalIEEE Transactions on Information Theory
Issue number10
Publication statusPublished - 1 Oct 2009


  • clique search (cs)
  • constant weight binary codes
  • heuristic algorithms
  • seed building
  • variable neighborhood search (vns)


Dive into the research topics of 'Heuristic algorithms for constructing binary constant weight codes'. Together they form a unique fingerprint.

Cite this