American Institute of Mathematical Sciences

Advanced
February  2007, 1(1): 93-97. doi: 10.3934/amc.2007.1.93

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, France
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, United States

Received  May 2006 Revised  June 2006 Published  January 2007

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: coverings, packings, duality., Coding theory.
Mathematics Subject Classification: 94B05, 94B75, 05D15, 05C1.
Citation: Gérard Cohen, Alexander Vardy. Duality between packings and coverings of the Hamming space. Advances in Mathematics of Communications, 2007, 1 (1) : 93-97. doi: 10.3934/amc.2007.1.93
[1]

Carla Mascia, Giancarlo Rinaldo, Massimiliano Sala. Hilbert quasi-polynomial for order domains and application to coding theory. Advances in Mathematics of Communications, 2018, 12 (2) : 287-301. doi: 10.3934/amc.2018018
[2]

Carlos F. Daganzo. On the variational theory of traffic flow: well-posedness, duality and applications. Networks & Heterogeneous Media, 2006, 1 (4) : 601-619. doi: 10.3934/nhm.2006.1.601
[3]

David Grant, Mahesh K. Varanasi. Duality theory for space-time codes over finite fields. Advances in Mathematics of Communications, 2008, 2 (1) : 35-54. doi: 10.3934/amc.2008.2.35
[4]

Marcello Trovati, Peter Ashwin, Nigel Byott. Packings induced by piecewise isometries cannot contain the arbelos. Discrete & Continuous Dynamical Systems, 2008, 22 (3) : 791-806. doi: 10.3934/dcds.2008.22.791
[5]

Ghislain Fourier, Gabriele Nebe. Degenerate flag varieties in network coding. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021027
[6]

Alex Kontorovich. The local-global principle for integral Soddy sphere packings. Journal of Modern Dynamics, 2019, 15: 209-236. doi: 10.3934/jmd.2019019
[7]

Daniele Bartoli, Alexander A. Davydov, Massimo Giulietti, Stefano Marcugini, Fernanda Pambianco. Further results on multiple coverings of the farthest-off points. Advances in Mathematics of Communications, 2016, 10 (3) : 613-632. doi: 10.3934/amc.2016030
[8]

Arseny Egorov. Morse coding for a Fuchsian group of finite covolume. Journal of Modern Dynamics, 2009, 3 (4) : 637-646. doi: 10.3934/jmd.2009.3.637
[9]

Min Ye, Alexander Barg. Polar codes for distributed hierarchical source coding. Advances in Mathematics of Communications, 2015, 9 (1) : 87-103. doi: 10.3934/amc.2015.9.87
[10]

Miguel Mendes. A note on the coding of orbits in certain discontinuous maps. Discrete & Continuous Dynamical Systems, 2010, 27 (1) : 369-382. doi: 10.3934/dcds.2010.27.369
[11]

Keisuke Minami, Takahiro Matsuda, Tetsuya Takine, Taku Noguchi. Asynchronous multiple source network coding for wireless broadcasting. Numerical Algebra, Control & Optimization, 2011, 1 (4) : 577-592. doi: 10.3934/naco.2011.1.577
[12]

Regina S. Burachik, Xiaoqi Yang. Asymptotic strong duality. Numerical Algebra, Control & Optimization, 2011, 1 (3) : 539-548. doi: 10.3934/naco.2011.1.539
[13]

Shiri Artstein-Avidan and Vitali Milman. A characterization of the concept of duality. Electronic Research Announcements, 2007, 14: 42-59. doi: 10.3934/era.2007.14.42
[14]

Qinghong Zhang, Gang Chen, Ting Zhang. Duality formulations in semidefinite programming. Journal of Industrial & Management Optimization, 2010, 6 (4) : 881-893. doi: 10.3934/jimo.2010.6.881
[15]

Adel Alahmadi, Steven Dougherty, André Leroy, Patrick Solé. On the duality and the direction of polycyclic codes. Advances in Mathematics of Communications, 2016, 10 (4) : 921-929. doi: 10.3934/amc.2016049
[16]

Daniele Bartoli, Alexander A. Davydov, Massimo Giulietti, Stefano Marcugini, Fernanda Pambianco. Multiple coverings of the farthest-off points with small density from projective geometry. Advances in Mathematics of Communications, 2015, 9 (1) : 63-85. doi: 10.3934/amc.2015.9.63
[17]

Radu Strugariu, Mircea D. Voisei, Constantin Zălinescu. Counter-examples in bi-duality, triality and tri-duality. Discrete & Continuous Dynamical Systems, 2011, 31 (4) : 1453-1468. doi: 10.3934/dcds.2011.31.1453
[18]

Vincent Astier, Thomas Unger. Galois extensions, positive involutions and an application to unitary space-time coding. Advances in Mathematics of Communications, 2019, 13 (3) : 513-516. doi: 10.3934/amc.2019032
[19]

T. Jäger. Neuronal coding of pacemaker neurons -- A random dynamical systems approach. Communications on Pure & Applied Analysis, 2011, 10 (3) : 995-1009. doi: 10.3934/cpaa.2011.10.995
[20]

Qian Guo, Thomas Johansson, Erik Mårtensson, Paul Stankovski Wagner. Some cryptanalytic and coding-theoretic applications of a soft stern algorithm. Advances in Mathematics of Communications, 2019, 13 (4) : 559-578. doi: 10.3934/amc.2019035

2020 Impact Factor: 0.935

Tools

Metrics

  • PDF downloads (81)
  • HTML views (0)
  • Cited by (1)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences