New Constructions for \(q\)-ary Covering Codes

Upper bounds on \(K_q(n, R)\), the minimum number of codewords in a \(q\)-ary code of length \(n\) and covering radius \(R\), are improved. Such bounds are obtained by constructing corresponding covering codes. In particular, codes of length \(q+1\) are discussed. Good such codes can be obtained from maximum distance separable \((MDS)\) codes. Furthermore, they can often be combined effectively with other covering codes to obtain new ones. Most of the new codes are obtained by computer search using simulated annealing. The new results are collected in updated tables of upper bounds on \(K_q(n, R)\), \(q=3,4,5\).