Covering radius 1985-1994 (Q676007): Difference between revisions

The covering radius of a code is the maximum distance of any vector in the ambient space to the code. The authors give a summary of many works on covering codes during the period 1985-1994 that have appeared since an earlier survey [\textit{G. D. Cohen}, \textit{M. G. Karpovsky}, \textit{H. F. Mattson} jun. and \textit{J. R. Schatz}, IEEE Trans. Inf. Theory 31, 328-343 (1985; Zbl 0586.94014)]. In Section 2 several methods on lower bounds are mentioned. These methods usually improve on the sphere-covering bound. In Section 3 the authors discuss asymptotic density of coverings when the length goes to infinity while the radius remains fixed. Section 4 discusses upper bounds for linear codes and Section 5 upper bounds obtained from constructions. Section 6 studies normality and some of its many offshoots, and the conjecture \(K(n+2, t+1) \leq K(n,t)\), where \(K(n,t)\) means the smallest cardinality of a binary code of length \(n\) and covering radius \(t\). Section 7 is devoted to specific classes of error correcting codes, among them Reed-Muller, BCH and their duals, cyclic, self-dual, and algebraic-geometric codes. Section 8 is a brief account of relations between covering radius and dual distance. In Section 9 generalizations of coverings are treated: mixed, weighted, and multiple coverings. In the last Section 10 the authors discuss the open problems of the earlier survey (see above), add two new ones, and disprove a conjecture. The authors give extensive tables of bounds for coverings. In the bibliography there are 280 items mentioned.