On the size of optimal binary codes of length 9 and covering radius 1
P. Östergård, Uri Blass · IEEE Transactions on Information Theory · 2001
The minimum number of codewords in a binary code with length n and covering radius R is denoted by K(n, R). The values of K(n, 1) are known up to length 8, and the corresponding optimal codes have been classified. It is known that 57/spl les/K(9, 1)/spl les/62. In the current work, the lower bound is improved to settle K(9, 1)=62. In the approach, which is computer-aided, possible distributions of codewords in subspaces are refined until each subspace is of dimension zero (consists of only one word). Repeatedly, a linear programming problem is solved considering only inequivalent distributions. A connection between this approach and weighted coverings is also presented; the computations give new results for such coverings as a by-product.