doi: 10.3934/amc.2021036
Online First

Online First articles are published articles within a journal that have not yet been assigned to a formal issue. This means they do not yet have a volume number, issue number, or page numbers assigned to them, however, they can still be found and cited using their DOI (Digital Object Identifier). Online First publication benefits the research community by making new scientific discoveries known as quickly as possible.

Readers can access Online First articles via the “Online First” tab for the selected journal.

Domination mappings into the hamming ball: Existence, constructions, and algorithms

1. 

Department of Industrial Systems Engineering and Management, National University of Singapore, Singapore

2. 

Department of Computer Science, Technion — Israel Institute of Technology, Haifa, Israel

3. 

School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore

4. 

Department of Electrical & Computer Engineering, University of California San Diego, LA Jolla, CA, USA

Received  January 2021 Revised  May 2021 Early access August 2021

Fund Project: The research of Y. M. Chee is supported by the Singapore Ministry of Education under grant MOE2017-T3-1-007. T. Etzion and A. Vardy were supported in part by the United States — Israel Binational Science Foundation (BSF), Jerusalem, Israel, under Grant 2012016

The Hamming ball of radius $ w $ in $ \{0,1\}^n $ is the set $ \mathcal{B}(n,w) $ of all binary words of length $ n $ and Hamming weight at most $ w $. We consider injective mappings $ \varphi : \{0,1\}^m \to \mathcal{B}(n,w) $ with the following domination property: every position $ j \in [n] $ is dominated by some position $ i \in [m] $, in the sense that if position $ i $ in $ {\mathit{\boldsymbol{x}}} \in \{0,1\}^m $ is "switched off" (equal zero), then necessarily position $ j $ in its image $ \varphi({\mathit{\boldsymbol{x}}}) $ is switched off. This property may be described more precisely in terms of a bipartite domination graph $ G = \bigl([m] \cup [n], E\bigr) $ with no isolated vertices; for all $ (i,j) \in E $ and all $ {\mathit{\boldsymbol{x}}}\in \{0,1\}^m $, we require that $ x_i = 0 $ implies $ y_j = 0 $, where $ {\mathit{\boldsymbol{y}}} = \varphi({\mathit{\boldsymbol{x}}}) $. Although such domination mappings recently found applications in the context of coding for high-performance interconnects, to the best of our knowledge, they were not previously studied. The concept of domination mapping is thus interesting from both practical and combinatorial points of view.

In this paper, we begin with simple necessary conditions for the existence of an $ (m,n,w) $-domination mapping $ \varphi : \{0,1\}^m \to \mathcal{B}(n,w) $. We then provide several explicit constructions of such mappings, which show that the necessary conditions are also sufficient when $ w = 1 $, when $ w = 2 $ and $ m $ is odd, or when $ m \leqslant 3w $. One of our main results herein is a proof that the trivial necessary condition $ | \mathcal{B}(n,w)| \geqslant 2^m $ is, in fact, sufficient for the existence of an $ (m,n,w) $-domination mapping whenever $ m $ is sufficiently large. We also present a polynomial-time algorithm that, given any $ m $, $ n $, and $ w $, determines whether an $ (m,n,w) $-domination mapping exists for a domination graph with an equitable degree distribution.

Citation: Yeow Meng Chee, Tuvi Etzion, Han Mao Kiah, Alexander Vardy. Domination mappings into the hamming ball: Existence, constructions, and algorithms. Advances in Mathematics of Communications, doi: 10.3934/amc.2021036
References:
[1]

A. H. Ajami, K. Banerjee, M. Pedram and L. P. P. P. van Ginneken, Analysis of non-uniform temperature-dependent interconnect performance in high performance ICs, DAC 2001: Proceedings of the 38-th Annual Design Automation Conference, ACM Press, (2001), 567–572. Google Scholar

[2]

R. Bodi and K. Herr, Symmetries in linear and integer programs, arXiv: 0908.3329, preprint, (2009). Google Scholar

[3]

Y. M. CheeT. EtzionH. M. Kiah and A. Vardy, Cooling codes: Thermal-management coding for high-performance interconnects, IEEE Trans. Inform. Theory, 64 (2018), 3062-3085.  doi: 10.1109/TIT.2017.2771245.  Google Scholar

[4]

Y. M. CheeT. EtzionH. M. KiahA. Vardy and H. Wei, Low-power cooling codes with efficient encoding and decoding, IEEE Trans. Inform. Theory, 66 (2020), 4804-4818.  doi: 10.1109/TIT.2020.2977871.  Google Scholar

[5]

W. J. Cook, W. H. Cunningham, W. R. Pulleyblank and A. Schrijver, Combinatorial Optimization, Wiley-Interscience Series in Discrete Mathematics and Optimization. A Wiley-Interscience Publication. John Wiley & Sons, Inc., New York, 1998.  Google Scholar

[6]

T. Etzion and L. Storme, Galois geometries and coding theory, Des. Codes Cryptogr., 78 (2016), 311-350.  doi: 10.1007/s10623-015-0156-5.  Google Scholar

[7]

A. FazeliA. Vardy and E. Yaakobi, Generalized sphere packing bound, IEEE Trans. Inform. Theory, 61 (2015), 2313-2334.  doi: 10.1109/TIT.2015.2413418.  Google Scholar

[8]

P. Hall, On representatives of subsets, J. London Math. Society, 10 (1935), 26-30.   Google Scholar

[9]

O. Heden, A survey of perfect codes, Adv. Math. Commun., 2 (2008), 223-247.  doi: 10.3934/amc.2008.2.223.  Google Scholar

[10]

D. König, Gráfok és mátrixok, Matematikai és Fizikai Lapok, 38 (1931), 116-119.   Google Scholar

[11]

F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, North-Holland Mathematical Library, Vol. 16. North-Holland Publishing Co., Amsterdam-New York-Oxford, 1977.  Google Scholar

[12]

F. Margot, Exploiting orbits in symmetric ILP, Math. Program., 98 (2003), 3-21.  doi: 10.1007/s10107-003-0394-6.  Google Scholar

[13]

SageMath, Sage Mathematics Software System (Version 7.6), Sage Developers, 2017, http://www.sagemath.org. Google Scholar

[14]

P. Sithambaram, A. Macii and E. Macii, New adaptive encoding schemes for switching activity balancing in on-chip buses, PATMOS 2007: Proceedings of the 17-th International Workshop on Power and Timing Modeling, Optimization and Simulation, Gothenburg, Sweden, (2007), 232–241. Google Scholar

[15]

F. I. Solov'eva, On perfect binary codes, Discrete Appl. Math., 156 (2008), 1488-1498.  doi: 10.1016/j.dam.2005.10.023.  Google Scholar

[16]

E. Nǎstase and P. A. Sissokho, The maximum size of a partial spread in a finite projective space, J. Combin. Theory Ser. A, 152 (2017), 353-362.  doi: 10.1016/j.jcta.2017.06.012.  Google Scholar

[17]

F. WangM. D. BoleX. WuY. XieN. Vijaykrishnan and M. J. Irwin, On-chip bus thermal analysis and optimization, IET Computers & Digital Techniques, 1 (2007), 590-599.   Google Scholar

[18]

F. Wang, Y. Xie, N. Vijaykrishnan and M. J. Irwin, On-chip bus thermal analysis and optimization, DATE 2006: Proceedings of the Conference on Design, Automation, and Test in Europe, Munich, Germany, 2006, 850–855. Google Scholar

show all references

References:
[1]

A. H. Ajami, K. Banerjee, M. Pedram and L. P. P. P. van Ginneken, Analysis of non-uniform temperature-dependent interconnect performance in high performance ICs, DAC 2001: Proceedings of the 38-th Annual Design Automation Conference, ACM Press, (2001), 567–572. Google Scholar

[2]

R. Bodi and K. Herr, Symmetries in linear and integer programs, arXiv: 0908.3329, preprint, (2009). Google Scholar

[3]

Y. M. CheeT. EtzionH. M. Kiah and A. Vardy, Cooling codes: Thermal-management coding for high-performance interconnects, IEEE Trans. Inform. Theory, 64 (2018), 3062-3085.  doi: 10.1109/TIT.2017.2771245.  Google Scholar

[4]

Y. M. CheeT. EtzionH. M. KiahA. Vardy and H. Wei, Low-power cooling codes with efficient encoding and decoding, IEEE Trans. Inform. Theory, 66 (2020), 4804-4818.  doi: 10.1109/TIT.2020.2977871.  Google Scholar

[5]

W. J. Cook, W. H. Cunningham, W. R. Pulleyblank and A. Schrijver, Combinatorial Optimization, Wiley-Interscience Series in Discrete Mathematics and Optimization. A Wiley-Interscience Publication. John Wiley & Sons, Inc., New York, 1998.  Google Scholar

[6]

T. Etzion and L. Storme, Galois geometries and coding theory, Des. Codes Cryptogr., 78 (2016), 311-350.  doi: 10.1007/s10623-015-0156-5.  Google Scholar

[7]

A. FazeliA. Vardy and E. Yaakobi, Generalized sphere packing bound, IEEE Trans. Inform. Theory, 61 (2015), 2313-2334.  doi: 10.1109/TIT.2015.2413418.  Google Scholar

[8]

P. Hall, On representatives of subsets, J. London Math. Society, 10 (1935), 26-30.   Google Scholar

[9]

O. Heden, A survey of perfect codes, Adv. Math. Commun., 2 (2008), 223-247.  doi: 10.3934/amc.2008.2.223.  Google Scholar

[10]

D. König, Gráfok és mátrixok, Matematikai és Fizikai Lapok, 38 (1931), 116-119.   Google Scholar

[11]

F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, North-Holland Mathematical Library, Vol. 16. North-Holland Publishing Co., Amsterdam-New York-Oxford, 1977.  Google Scholar

[12]

F. Margot, Exploiting orbits in symmetric ILP, Math. Program., 98 (2003), 3-21.  doi: 10.1007/s10107-003-0394-6.  Google Scholar

[13]

SageMath, Sage Mathematics Software System (Version 7.6), Sage Developers, 2017, http://www.sagemath.org. Google Scholar

[14]

P. Sithambaram, A. Macii and E. Macii, New adaptive encoding schemes for switching activity balancing in on-chip buses, PATMOS 2007: Proceedings of the 17-th International Workshop on Power and Timing Modeling, Optimization and Simulation, Gothenburg, Sweden, (2007), 232–241. Google Scholar

[15]

F. I. Solov'eva, On perfect binary codes, Discrete Appl. Math., 156 (2008), 1488-1498.  doi: 10.1016/j.dam.2005.10.023.  Google Scholar

[16]

E. Nǎstase and P. A. Sissokho, The maximum size of a partial spread in a finite projective space, J. Combin. Theory Ser. A, 152 (2017), 353-362.  doi: 10.1016/j.jcta.2017.06.012.  Google Scholar

[17]

F. WangM. D. BoleX. WuY. XieN. Vijaykrishnan and M. J. Irwin, On-chip bus thermal analysis and optimization, IET Computers & Digital Techniques, 1 (2007), 590-599.   Google Scholar

[18]

F. Wang, Y. Xie, N. Vijaykrishnan and M. J. Irwin, On-chip bus thermal analysis and optimization, DATE 2006: Proceedings of the Conference on Design, Automation, and Test in Europe, Munich, Germany, 2006, 850–855. Google Scholar

Figure 1.  Bounds, constructions, and existence of $ (m,n,w) $-domination mappings for $ w = 3 $
[1]

B. K. Dass, Namita Sharma, Rashmi Verma. Characterization of extended Hamming and Golay codes as perfect codes in poset block spaces. Advances in Mathematics of Communications, 2018, 12 (4) : 629-639. doi: 10.3934/amc.2018037

[2]

Olof Heden. A survey of perfect codes. Advances in Mathematics of Communications, 2008, 2 (2) : 223-247. doi: 10.3934/amc.2008.2.223

[3]

Luciano Panek, Jerry Anderson Pinheiro, Marcelo Muniz Alves, Marcelo Firer. On perfect poset codes. Advances in Mathematics of Communications, 2020, 14 (3) : 477-489. doi: 10.3934/amc.2020061

[4]

Olof Heden. The partial order of perfect codes associated to a perfect code. Advances in Mathematics of Communications, 2007, 1 (4) : 399-412. doi: 10.3934/amc.2007.1.399

[5]

Joaquim Borges, Josep Rifà, Victor Zinoviev. Completely regular codes by concatenating Hamming codes. Advances in Mathematics of Communications, 2018, 12 (2) : 337-349. doi: 10.3934/amc.2018021

[6]

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

[7]

Anuradha Sharma, Saroj Rani. Trace description and Hamming weights of irreducible constacyclic codes. Advances in Mathematics of Communications, 2018, 12 (1) : 123-141. doi: 10.3934/amc.2018008

[8]

Markku Lehtinen, Baylie Damtie, Petteri Piiroinen, Mikko Orispää. Perfect and almost perfect pulse compression codes for range spread radar targets. Inverse Problems & Imaging, 2009, 3 (3) : 465-486. doi: 10.3934/ipi.2009.3.465

[9]

Lassi Roininen, Markku S. Lehtinen. Perfect pulse-compression coding via ARMA algorithms and unimodular transfer functions. Inverse Problems & Imaging, 2013, 7 (2) : 649-661. doi: 10.3934/ipi.2013.7.649

[10]

Sergio R. López-Permouth, Steve Szabo. On the Hamming weight of repeated root cyclic and negacyclic codes over Galois rings. Advances in Mathematics of Communications, 2009, 3 (4) : 409-420. doi: 10.3934/amc.2009.3.409

[11]

Olof Heden, Faina I. Solov’eva. Partitions of $\mathbb F$n into non-parallel Hamming codes. Advances in Mathematics of Communications, 2009, 3 (4) : 385-397. doi: 10.3934/amc.2009.3.385

[12]

Alonso sepúlveda Castellanos. Generalized Hamming weights of codes over the $\mathcal{GH}$ curve. Advances in Mathematics of Communications, 2017, 11 (1) : 115-122. doi: 10.3934/amc.2017006

[13]

Kang-Yu Ni, Shankar Rao, Yuri Owechko. Foveated compressive imaging for low power vehicle fingerprinting and tracking in aerial imagery. Inverse Problems & Imaging, 2017, 11 (1) : 177-202. doi: 10.3934/ipi.2017009

[14]

Limengnan Zhou, Daiyuan Peng, Hongyu Han, Hongbin Liang, Zheng Ma. Construction of optimal low-hit-zone frequency hopping sequence sets under periodic partial Hamming correlation. Advances in Mathematics of Communications, 2018, 12 (1) : 67-79. doi: 10.3934/amc.2018004

[15]

Olof Heden, Fabio Pasticci, Thomas Westerbäck. On the existence of extended perfect binary codes with trivial symmetry group. Advances in Mathematics of Communications, 2009, 3 (3) : 295-309. doi: 10.3934/amc.2009.3.295

[16]

Olof Heden, Denis S. Krotov. On the structure of non-full-rank perfect $q$-ary codes. Advances in Mathematics of Communications, 2011, 5 (2) : 149-156. doi: 10.3934/amc.2011.5.149

[17]

Helena Rifà-Pous, Josep Rifà, Lorena Ronquillo. $\mathbb{Z}_2\mathbb{Z}_4$-additive perfect codes in Steganography. Advances in Mathematics of Communications, 2011, 5 (3) : 425-433. doi: 10.3934/amc.2011.5.425

[18]

Nupur Patanker, Sanjay Kumar Singh. Generalized Hamming weights of toric codes over hypersimplices and squarefree affine evaluation codes. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021013

[19]

Vy Khoi Le. Existence and enclosure of solutions to noncoercive systems of inequalities with multivalued mappings and non-power growths. Discrete & Continuous Dynamical Systems, 2013, 33 (1) : 255-276. doi: 10.3934/dcds.2013.33.255

[20]

Gokhan Calis, O. Ozan Koyluoglu. Architecture-aware coding for distributed storage: Repairable block failure resilient codes. Advances in Mathematics of Communications, 2018, 12 (3) : 465-503. doi: 10.3934/amc.2018028

2020 Impact Factor: 0.935

Metrics

  • PDF downloads (16)
  • HTML views (40)
  • Cited by (0)

[Back to Top]