A new approach to the covering radius of codes (Q1086543)

A new approach is given for determining the covering radius of a binary linear code. Let C be a binary linear [n,k] code in which every column is distinct and nonzero. The covering radius R of the code is \(\max_{x\in F^ N_ 2}\min_{c\in C}d(x,c)\), where d(.,.) is Hamming distance. By choosing suitable multiplicities \(m_ i\), \(i=1,2,...,n\), and taking \(m_ i\) copies of the ith column of C, \(i=1,2,...,n\), a new code \(C^*\) is obtained, of length \(\sum m_ i\). As the multiplicities may be 0 or any positive integer, any code can be obtained in this way. It is shown that the covering radius \(R^*\) of \(C^*\) is at least \(\sum [m_ i/2]\) and so the normalized covering radius of \(C^*\) is defined as \(\rho =R^*-\sum^{n}_{i=1}[m_ i/2]\). Notice that \(\rho =R\) when the multiplicities are unity. It is shown that the computation of \(\rho\) is an integer programming problem which results in an upper bound. Other upper and lower bounds are also given. It is shown that if the code dimension is at most four then the covering radius may be found exactly. A generalization of the Berlekamp-Gale switching game is also discussed.