Exact Bounds on the Sizes of Covering Codes |
| |
Authors: | Maria Axenovich Zoltán Füredi |
| |
Institution: | (1) Departments of Mathematics, University of Illinois and Iowa State University, Ames, IA, 50011, U.S.A.;(2) Department of Mathematics, University of Illinois, Urbana, IL, 61820;(3) Alfréd Rényi Institute of Mathematics of the Hungarian Academy of Sciences, Budapest, P.O. Box 127, 1364, Hungary |
| |
Abstract: | A code c is a covering code of X with radius r if every element of X is within Hamming distance r from at least one codeword from c. The minimum size of such a c is denoted by c
r(X). Answering a question of Hämäläinen et al. 10], we show further connections between Turán theory and constant weight covering codes. Our main tool is the theory of supersaturated hypergraphs. In particular, for n > n
0(r) we give the exact minimum number of Hamming balls of radius r required to cover a Hamming ball of radius r + 2 in {0, 1}n. We prove that c
r(B
n(0, r + 2)) = 1 i r + 1 ( (n + i – 1) / (r + 1) 2) + n / (r + 1) and that the centers of the covering balls B(x, r) can be obtained by taking all pairs in the parts of an (r + 1)-partition of the n-set and by taking the singletons in one of the parts. |
| |
Keywords: | binary codes covering radius supersaturated hypergraphs Turá n theorem |
本文献已被 SpringerLink 等数据库收录! |
|