Title: Iterated local search and constructive heuristics for error correcting code design

Authors: Christian Blum

Addresses: ALBCOM, LSI, Universitat Politecnica de Catalunya, Jordi Girona 1-3, Campus Nord, Barcelona 08034, Spain

Abstract: Error Correcting Codes (ECCs) play an important role, for example, in the transmission of messages over telecommunication networks or in reading information from digital data media such as DVDs or CDs. The design of ECCs is computationally a hard problem. Due to its hardness, several metaheuristic approaches for its solution have been proposed in the literature. In this paper, we present different algorithms based on solution construction and iterated local search. The experimental evaluation shows that a simple multistart constructive heuristic is often between two and three orders of magnitude faster than current state-of-the-art metaheuristics when applied to rather small problem instances. When bigger problem instances are concerned, the proposed iterated local search algorithm has advantages over both the multistart constructive heuristic and state-of-the-art metaheuristics.

Keywords: iterated local search; constructive heuristics; error correcting codes; code design; ECCs; nonlinear binary block codes; metaheuristics.

DOI: 10.1504/IJICA.2007.013398

International Journal of Innovative Computing and Applications, 2007 Vol.1 No.1, pp.14 - 22

Published online: 25 Apr 2007 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article