Constructing covering codes with given automorphisms (Q1283221)

The authors consider the problem of finding upper bounds on \(K(n,r)\), the minimum number of words in a binary code of length \(n\) and covering radius \(r\). Constructions of covering codes give these bounds on \(K(n,r)\). It is shown how computer searches for covering codes can be speed up by requiring that the code has a given (not necessarily full) automorphism group. The optimization method used is tabu search. A new code is presented which proves a new record \(K(13,1)\leq 704\). This code has a very large full automorphism group and several other interesting properties.