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

Duality between packings and coverings of the Hamming space

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.
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 - A, 2008, 22 (3) : 791-806. doi: 10.3934/dcds.2008.22.791

[5]

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

[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]

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

[8]

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

[9]

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

[10]

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

[11]

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

[12]

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

[13]

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

[14]

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

[15]

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

[16]

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

[17]

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

[18]

Shinsuke Koyama, Lubomir Kostal. The effect of interspike interval statistics on the information gain under the rate coding hypothesis. Mathematical Biosciences & Engineering, 2014, 11 (1) : 63-80. doi: 10.3934/mbe.2014.11.63

[19]

Stefan Martignoli, Ruedi Stoop. Phase-locking and Arnold coding in prototypical network topologies. Discrete & Continuous Dynamical Systems - B, 2008, 9 (1) : 145-162. doi: 10.3934/dcdsb.2008.9.145

[20]

Giuseppe Bianchi, Lorenzo Bracciale, Keren Censor-Hillel, Andrea Lincoln, Muriel Médard. The one-out-of-k retrieval problem and linear network coding. Advances in Mathematics of Communications, 2016, 10 (1) : 95-112. doi: 10.3934/amc.2016.10.95

2018 Impact Factor: 0.879

Metrics

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

Other articles
by authors

[Back to Top]