Genetic Algorithms in Coding Theory 2 A Table for A3(n,d)

We consider the problem of finding values of A3(n, d), i.e. the maximal size of a ternary code of length n and minimum distance d. Our approach is based on a search for good lower bounds and a comparison of these bounds with known upper bounds. Several lower bounds are obtained using a genetic local search algorithm. Other lower bounds are obtained by constructing codes. For those cases in which lower and upper bounds coincide, this yields exact values of A3(n, d). A table is included containing the known values of the upper and lower bounds for A3(n, d), with n::; 16. For some values of nand d the corresponding codes are given. 1 Introd uction We consider the problem of finding values of Aq ( n, d), i.e. the maximal size of a code of length n over an alphabet of q elements, having minimum distance d. A code has minimum distance d, if d is the smallest number of positions in which two distinct codewords differ. To prove that Aq ( n, d) is equal to a certain value, say M, one has to verify the following two conditions. • There are no codes of length n and minimum distance d over a q-ary alphabet having more than M codewords. • There exists a code of length n and minimum distance d over a q-ary alphabet having M codewords. To verify the first condition, one has to prove that every q-ary code of length n and minimum distance d has at most M codewords. Since for most parameters q, nand d, the number of such codes is very large, it is impracticable to construct all these codes and show that they have at most M codewords. Therefore one resorts to estimating upper bounds for Aq ( n, d). In the literature many upper bounds are known and we will give some of them below