Duality between packings and coverings of the Hamming space

Gérard Cohen; Alexander Vardy

doi:10.3934/amc.2007.1.93

Article Contents

2007, Volume 1, Issue 1: 93-97. Doi: 10.3934/amc.2007.1.93

This issue Previous Article A new upper bound on the rate of non-binary codes Next Article Gilbert-Varshamov type bounds for linear codes over finite chain rings

Duality between packings and coverings of the Hamming space

Gérard Cohen^1, and
Alexander Vardy^2,

1.
Département Informatique, Ecole Nationale Supérieure des Télécommunications, 46 rue Barrault, 75634 Paris
2.
Department of Electrical and Computer Engineering, Department of Computer Science and Engineering, Department of Mathematics, University of California San Diego, 9500 Gilman Drive, La Jolla, CA92093

Received: April 30, 2006

Revised: May 31, 2006

Published: January 2007

Abstract Related Papers Cited by

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.

Keywords:

Mathematics Subject Classification: 94B05, 94B75, 05D15, 05C15.

Citation:

Article Metrics

HTML views() PDF downloads(147) Cited by(0)

Duality between packings and coverings of the Hamming space

Abstract

Access History

Article Metrics

Access History

Other Articles By Authors

Catalog

Duality between packings and coverings of the Hamming space

Abstract

Access History

SHARE

Article Metrics

Access History

Other Articles By Authors

Catalog

Export File

Citation

Format

Content