Lower bounds for \(q\)-ary coverings by spheres of radius one. (English) Zbl 0815.94021

Let \(C\) be a \(q\)-ary covering code with covering radius one. The author shows that if \((q - 1)n + 1\) does not divide \(q^ n\) and if \((q,n) \notin \{(2,2), (2,4)\}\), the sphere covering bound is not reached. The author characterizes the cases where the sphere covering bound is attained, when \(q\) is a prime power. The author also presents some improvements of lower bounds for binary and ternary codes.


94B75 Applications of the theory of convex sets and geometry of numbers (covering radius, etc.) to coding theory
94B65 Bounds on codes
Full Text: DOI


[1] Chen, W.; Honkala, I. S., Lower bounds for \(q\)-ary covering codes, IEEE Trans. Inform. Theory, IT-36, 664-671 (1990) · Zbl 0703.94014
[2] Cohen, G. D.; Karpovsky, M. G.; Mattson, H. F.; Schatz, J. R., Covering radiu—Survey and recent results, IEEE Trans. Inform. Theory, IT-31, 328-343 (1985) · Zbl 0586.94014
[3] Cohen, G. D.; Lobstein, A. C.; Sloane, N. J.A, Further results on the covering radius of codes, IEEE Trans. Inform. Theory, IT-32, 680-694 (1986) · Zbl 0618.94014
[4] Honkala, I. S., Modified bounds for binary covering codes, IEEE Trans. Inform. Theory, IT-37, 351-365 (1991) · Zbl 0721.94023
[5] Kalbfleisch, J. G.; Stanton, R. G., A combinatorial problem in matching, J. London Math. Soc., 1, 398 (1969) · Zbl 0182.02803
[6] Kamps, H. J.L; Van Lint, J. H., The football pool problem for 5 matches, J. Combin. Theory Ser. A, 3, 315-325 (1967) · Zbl 0153.32602
[7] Losey, G., Note on a theorem of Zaremba, J. Combin. Theory Ser. A, 6, 208-209 (1969) · Zbl 0172.01402
[8] Stanton, R. G.; Horton, J. D.; Kalbfleisch, J. G., Covering theorems for vectors with special reference to the case of four and five components, J. London Math. Soc., 2, 493-499 (1969) · Zbl 0191.00505
[9] Stanton, R. G.; Kalbfleisch, J. G., Covering problems for dichotomized matchings, Aequationes Math., 1, 94-103 (1968) · Zbl 0159.03004
[10] Van Wee, G. J.M, Improved sphere bounds on the covering radius of codes, IEEE Trans. Inform. Theory, IT-34, 237-245 (1988) · Zbl 0653.94014
[11] Van Wee, G. J.M, Bounds on packings and coverings by spheres in \(q\)-ary and mixed Hamming spaces, J. Combin. Theory Ser. A, 57, 117-129 (1991) · Zbl 0755.94013
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.