Construction Methods for Covering Codes

摘要

A covering code in a Hamming space is a set of codewords with the property thatany word in the space is within a specified Hamming distance, the covering radius, from at least one codeword. In this thesis, efficient construction methods for such codes are considered. The constructions work, with some exceptions, for codes over alphabets consisting of any number of symbols. Codes over mixed alphabets are also discussed. Most of the methods are developed in order to determine values of Kq (n, R), the minimum number of codewords in a q-ary code of length n and covering radius R. Codes obtained by the constructions prove upper bounds on this function. In many of the constructions simulated annealing, a probabilistic optimization method, has turned out to perform very well. Simulated annealing cannot be used to prove optimality of codes found; in that case, the problem is viewed and solved as a set covering problem. For larger codes, a direct approach is not generally feasible; it is shown how good such codes can be found by combining existing codes, or by imposing some structure on the codes. A matrix method that is presented follows the latter principle; a code constructed by this method consists of cosets of a linear code. Finally, some families of combinatorial methods are presented.