On the covering radius of codes

The covering radiusRof a code is the maximal distance of any vector from the code. This work gives a number of new results concerningt[n, k], the minimal covering radius of any binary code of lengthnand dimensionk. For examplet[n, 4]andt[n, 5]are determined exactly, and reasonably tight bounds ont[n, k]are obtained for anykwhennis large. These results are found by using several new constructions for codes with small covering radius. One construction, the amalgamated direct sum, involves a quantity called the norm of a code. Codes with norm≤ 2 R + 1are called normal, and may be combined efficiently. The paper concludes with a table giving bounds ont[n, k]forn ≤ 64.