No label defined (Q4242015)

\{ For the entire collection see Zbl 0907.94001 \}. The covering radius of a block code \(C\subseteq F^n_q\) is the smallest integer \(r\) such that every vector in \(F^n_q\) is within Hamming distance \(r\) from at least one codeword. The study of this parameter has attracted a lot of attention, in particular since 1985, when the two papers \textit{G. D. Cohen}, \textit{M. G. Karpovsky}, \textit{H. F. Mattson} jun., and \textit{J. R. Schatz} [IEEE Trans. Inf. Theory IT-31, 328-343 (1985; Zbl 0586.94014) and \textit{R. L. Graham} and \textit{N. J. A. Sloane}, ibid. 385-401 (1985; Zbl 0585.94012)] appeared. After basic results, the authors discuss various constructions including direct sum, amalgamated direct sum (and the related normality concepts), piecewise constant codes, \((u,u+v)\) construction, matrix construction, and cascading. Various techniques are described to obtain lower bounds (= nonexistence results), like the use of embedded codes, linear programming, and excess techniques. This is followed by a number of upper bounds on the covering radius of a given code, including the Norse bounds; the study of descendants and orphans, and bounds on subcodes of a given code. The section on the best known linear codes includes a table of bounds for \(\ell(m,r)\), the smallest length of a binary linear code with codimension \(m\) \((=n-k\), where \(k\) is the dimension) and covering radius \(r\). The next two sections present the known results about the covering radius of Reed-Muller codes, and BCH codes and their duals, and Goppa codes. The last two sections discuss the asymptotical aspects and various generalizations of the basic covering radius problem. Other recent surveys on the topic include \textit{G. D. Cohen}, \textit{S. Litsyn}, \textit{A. C. Lobstein} and \textit{H. F. Mattson} jun. [Appl. Algebra Eng. Commun. Comput. 8, No. 3, 171-239 (1997; Zbl 0873.94025)] and \textit{G. Cohen}, \textit{I. Honkala}, \textit{S. Litsyn} and \textit{A. Lobstein} [Covering codes, Elsevier, Amsterdam (1997; Zbl 0874.94001)].