Advanced Search
Article Contents
Article Contents

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

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

Abstract Full Text(HTML) Figure(1) Related Papers Cited by
  • 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.

    Mathematics Subject Classification: Primary: 68R01, 68R05, 68R10.


    \begin{equation} \\ \end{equation}
  • 加载中
  • Figure 1.  Bounds, constructions, and existence of $ (m,n,w) $-domination mappings for $ w = 3 $

  • [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.
    [2] R. Bodi and K. Herr, Symmetries in linear and integer programs, arXiv: 0908.3329, preprint, (2009).
    [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.
    [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.
    [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.
    [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.
    [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.
    [8] P. Hall, On representatives of subsets, J. London Math. Society, 10 (1935), 26-30. 
    [9] O. Heden, A survey of perfect codes, Adv. Math. Commun., 2 (2008), 223-247.  doi: 10.3934/amc.2008.2.223.
    [10] D. König, Gráfok és mátrixok, Matematikai és Fizikai Lapok, 38 (1931), 116-119. 
    [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.
    [12] F. Margot, Exploiting orbits in symmetric ILP, Math. Program., 98 (2003), 3-21.  doi: 10.1007/s10107-003-0394-6.
    [13] SageMath, Sage Mathematics Software System (Version 7.6), Sage Developers, 2017, http://www.sagemath.org.
    [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.
    [15] F. I. Solov'eva, On perfect binary codes, Discrete Appl. Math., 156 (2008), 1488-1498.  doi: 10.1016/j.dam.2005.10.023.
    [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.
    [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. 
    [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.
  • 加载中



Article Metrics

HTML views(1201) PDF downloads(612) Cited by(0)

Access History



    DownLoad:  Full-Size Img  PowerPoint