Construction of insertion/deletion error correcting codes using heuristic algorithms

Abstract

Insertion deletion channels are very common and found in unexpected places. Various algorithms have been designed to construct good codes to be used in differ- ent scenarios. This work reports research carried out on these different algorithms and their possible use. One of the most recent construction algorithm (Salmon al- gorithm) which shows great potential is compared to an older algorithm (Simulated Annealing algorithm) which is both simple and e ective. The results indicate that the Salmon algorithm is the better algorithm of the two for the scenarios tested. The result were also compared to published upper bounds of various code sizes (from length n = 5 varying to n = 12) and the Salmon Algorithm managed to find better codes.