May  2017, 11(2): 359-366. doi: 10.3934/amc.2017029

Minimum dimensional Hamming embeddings

University of Campinas, São Paulo, Brazil

* Corresponding author

Received  February 2016 Revised  March 2016 Published  May 2017

We consider two metrics decoding equivalent if they impose the same minimum distance decoding for every code. It is known that, up to this equivalence, every metric is isometrically embeddable into the Hamming cube.

We present an algorithm which for any translation invariant metric gives an upper bound on the minimum dimension of such an embedding. We also give lower and upper bounds for this embedding dimension over the set of all such metrics.

Citation: Rafael G. L. D'Oliveira, Marcelo Firer. Minimum dimensional Hamming embeddings. Advances in Mathematics of Communications, 2017, 11 (2) : 359-366. doi: 10.3934/amc.2017029
References:
[1]

V. Chvétal, Recognizing intersection patterns, Ann. Discrete Math., 8 (1980), 249-251.   Google Scholar

[2]

M. Deza and M. Laurent, Geometric properties, in Geometry of Cuts and Metrics, Springer-Verlag, 1997,511-550. doi: 10.1007/978-3-642-04295-9_31.  Google Scholar

[3]

R. G. L. D'Oliveira and M. Firer, Channel metrization, preprint, arXiv: 1510.03104 Google Scholar

[4] F. Eisenbrand, Fast Integer Programming in Fixed Dimension, Springer, Berlin, 2003.  doi: 10.1007/978-3-540-39658-1_20.  Google Scholar
[5]

M. Firer and J. L. Walker, Matched metrics and channels, IEEE Trans. Inf. Theory, 62 (2016), 1150-1156.  doi: 10.1109/TIT.2015.2512596.  Google Scholar

[6]

H. W. Lenstra Jr., Integer programming with a fixed number of variables, Math. Oper. Res., 8 (1983), 538-548.  doi: 10.1287/moor.8.4.538.  Google Scholar

show all references

References:
[1]

V. Chvétal, Recognizing intersection patterns, Ann. Discrete Math., 8 (1980), 249-251.   Google Scholar

[2]

M. Deza and M. Laurent, Geometric properties, in Geometry of Cuts and Metrics, Springer-Verlag, 1997,511-550. doi: 10.1007/978-3-642-04295-9_31.  Google Scholar

[3]

R. G. L. D'Oliveira and M. Firer, Channel metrization, preprint, arXiv: 1510.03104 Google Scholar

[4] F. Eisenbrand, Fast Integer Programming in Fixed Dimension, Springer, Berlin, 2003.  doi: 10.1007/978-3-540-39658-1_20.  Google Scholar
[5]

M. Firer and J. L. Walker, Matched metrics and channels, IEEE Trans. Inf. Theory, 62 (2016), 1150-1156.  doi: 10.1109/TIT.2015.2512596.  Google Scholar

[6]

H. W. Lenstra Jr., Integer programming with a fixed number of variables, Math. Oper. Res., 8 (1983), 538-548.  doi: 10.1287/moor.8.4.538.  Google Scholar

Figure 1.  The partition of $\mathbb{R}_{> 0}^3$ by the $\mathit{Cone}$ function into $13$ cones: six $3$-dimensional, six $2$-dimensional, and one $1$-dimensional (the ray $(\lambda,\lambda,\lambda)$ with $\lambda > 0)$
[1]

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

[2]

Christopher Bose, Rua Murray. Minimum 'energy' approximations of invariant measures for nonsingular transformations. Discrete & Continuous Dynamical Systems, 2006, 14 (3) : 597-615. doi: 10.3934/dcds.2006.14.597

[3]

Enkhbat Rentsen, N. Tungalag, J. Enkhbayar, O. Battogtokh, L. Enkhtuvshin. Application of survival theory in Mining industry. Numerical Algebra, Control & Optimization, 2021, 11 (3) : 443-448. doi: 10.3934/naco.2020036

[4]

Shi'an Wang, N. U. Ahmed. Optimal control and stabilization of building maintenance units based on minimum principle. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1713-1727. doi: 10.3934/jimo.2020041

[5]

Muberra Allahverdi, Harun Aydilek, Asiye Aydilek, Ali Allahverdi. A better dominance relation and heuristics for Two-Machine No-Wait Flowshops with Maximum Lateness Performance Measure. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1973-1991. doi: 10.3934/jimo.2020054

[6]

Mario Bukal. Well-posedness and convergence of a numerical scheme for the corrected Derrida-Lebowitz-Speer-Spohn equation using the Hellinger distance. Discrete & Continuous Dynamical Systems, 2021, 41 (7) : 3389-3414. doi: 10.3934/dcds.2021001

[7]

Guillaume Bal, Wenjia Jing. Homogenization and corrector theory for linear transport in random media. Discrete & Continuous Dynamical Systems, 2010, 28 (4) : 1311-1343. doi: 10.3934/dcds.2010.28.1311

[8]

Felix Finster, Jürg Fröhlich, Marco Oppio, Claudio F. Paganini. Causal fermion systems and the ETH approach to quantum theory. Discrete & Continuous Dynamical Systems - S, 2021, 14 (5) : 1717-1746. doi: 10.3934/dcdss.2020451

[9]

Fioralba Cakoni, Shixu Meng, Jingni Xiao. A note on transmission eigenvalues in electromagnetic scattering theory. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2021025

[10]

W. Cary Huffman. On the theory of $\mathbb{F}_q$-linear $\mathbb{F}_{q^t}$-codes. Advances in Mathematics of Communications, 2013, 7 (3) : 349-378. doi: 10.3934/amc.2013.7.349

[11]

Qi Lü, Xu Zhang. A concise introduction to control theory for stochastic partial differential equations. Mathematical Control & Related Fields, 2021  doi: 10.3934/mcrf.2021020

[12]

John Leventides, Costas Poulios, Georgios Alkis Tsiatsios, Maria Livada, Stavros Tsipras, Konstantinos Lefcaditis, Panagiota Sargenti, Aleka Sargenti. Systems theory and analysis of the implementation of non pharmaceutical policies for the mitigation of the COVID-19 pandemic. Journal of Dynamics & Games, 2021  doi: 10.3934/jdg.2021004

[13]

Beom-Seok Han, Kyeong-Hun Kim, Daehan Park. A weighted Sobolev space theory for the diffusion-wave equations with time-fractional derivatives on $ C^{1} $ domains. Discrete & Continuous Dynamical Systems, 2021, 41 (7) : 3415-3445. doi: 10.3934/dcds.2021002

2019 Impact Factor: 0.734

Metrics

  • PDF downloads (95)
  • HTML views (61)
  • Cited by (4)

Other articles
by authors

[Back to Top]