A tabu search approach to the minimum distance of error-correcting codes

Abstract

Tabu search is a deterministic combinatorial optimization technique. In this paper an implementation in an error-correcting code context is presented and then used to investigate the minimum distances of some linear block (BCH) codes. Of the two search strategies (both are implementation aspects of tabu search), the one involving sets of moves and a ‘back-tracking’ facility is found to give better upper bounds for the minimum distances. Computational results obtained using tabu search show that it is a useful and effective optimization technique for providing good minimum distance values of linear block codes. A limited comparison with recent results, obtained using simulated annealing, reveals that tabu search may give lower minimum distances in much shorter execution times.