Duality between packings and coverings of the Hamming space

DOI10.3934/AMC.2007.1.93zbMATH Open1198.94176arXivcs/0507015OpenAlexW2039734956MaRDI QIDQ874419FDOQ874419

Gérard Cohen, Alexander Vardy

Publication date: 5 April 2007

Published in: Advances in Mathematics of Communications (Search for Journal in Brave)

Abstract: We investigate the packing and covering densities of linear and nonlinear binary codes, and establish a number of duality relationships between the packing and covering problems. Specifically, we prove that if almost all codes (in the class of linear or nonlinear codes) are good packings, then only a vanishing fraction of codes are good coverings, and vice versa: if almost all codes are good coverings, then at most a vanishing fraction of codes are good packings. We also show that any specific maximal binary code is either a good packing or a good covering, in a certain well-defined sense.

Full work available at URL: https://arxiv.org/abs/cs/0507015

zbMATH Keywords

dualitycoveringspackingscoding theory

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Linear codes (general theory) (94B05) Applications of the theory of convex sets and geometry of numbers (covering radius, etc.) to coding theory (94B75)

Cited In (2)

• Resolving the Existence of Full-Rank Tilings of Binary Hamming Spaces
• Unit sphere packings and coverings of the Hamming space

   Recommendations

• Good coverings of Hamming spaces with spheres 👍 👎
• Weighted coverings and packings 👍 👎
• Linear programming bounds for codes via a covering argument 👍 👎
• Unit sphere packings and coverings of the Hamming space 👍 👎
• Title not available (Why is that?) 👍 👎

This page was built for publication: Duality between packings and coverings of the Hamming space

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q874419)