Duality between packings and coverings of the Hamming space

DOI10.3934/AMC.2007.1.93MaRDI QIDQ874419zbMATH OpenOpenAlexFDO

Authors Alexander Vardy, Gérard Cohen

Publication date 5 April 2007

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

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

zbMATH Keywords

coding theorycoveringsdualitypackings

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)

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.

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
• scientific article; zbMATH DE number 3780

Cited in

(4)

• Unit sphere packings and coverings of the Hamming space
• Maximal partial packings of Z₂^n with perfect codes
• Resolving the Existence of Full-Rank Tilings of Binary Hamming Spaces
• Packing densities of randomly constructed codes

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)