American Institute of Mathematical Sciences

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

Minimum dimensional Hamming embeddings

Rafael G. L. D'Oliveira , and  Marcelo Firer

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.

Keywords: Coding theory, hypercube embeddings, maximum-likelihood decoding, minimum distance decoding.
Mathematics Subject Classification: 94A24.
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)$
Figure Options

Download full-size image

Download as PowerPoint slide

[1]

Sihem Guerarra. Maximum and minimum ranks and inertias of the Hermitian parts of the least rank solution of the matrix equation AXB = C. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 75-86. doi: 10.3934/naco.2020016
[2]

Liping Tang, Ying Gao. Some properties of nonconvex oriented distance function and applications to vector optimization problems. Journal of Industrial & Management Optimization, 2021, 17 (1) : 485-500. doi: 10.3934/jimo.2020117
[3]

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, 2020  doi: 10.3934/dcdss.2020451
[4]

Giuseppina Guatteri, Federica Masiero. Stochastic maximum principle for problems with delay with dependence on the past through general measures. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020048
[5]

Cheng Peng, Zhaohui Tang, Weihua Gui, Qing Chen, Jing He. A bidirectional weighted boundary distance algorithm for time series similarity computation based on optimized sliding window size. Journal of Industrial & Management Optimization, 2021, 17 (1) : 205-220. doi: 10.3934/jimo.2019107
[6]

Pierre-Etienne Druet. A theory of generalised solutions for ideal gas mixtures with Maxwell-Stefan diffusion. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020458
[7]

Juan Pablo Pinasco, Mauro Rodriguez Cartabia, Nicolas Saintier. Evolutionary game theory in mixed strategies: From microscopic interactions to kinetic equations. Kinetic & Related Models, , () : -. doi: 10.3934/krm.2020051
[8]

Sergey Rashkovskiy. Hamilton-Jacobi theory for Hamiltonian and non-Hamiltonian systems. Journal of Geometric Mechanics, 2020, 12 (4) : 563-583. doi: 10.3934/jgm.2020024
[9]

Stefan Doboszczak, Manil T. Mohan, Sivaguru S. Sritharan. Pontryagin maximum principle for the optimal control of linearized compressible navier-stokes equations with state constraints. Evolution Equations & Control Theory, 2020  doi: 10.3934/eect.2020110
[10]

Claudianor O. Alves, Rodrigo C. M. Nemer, Sergio H. Monari Soares. The use of the Morse theory to estimate the number of nontrivial solutions of a nonlinear Schrödinger equation with a magnetic field. Communications on Pure & Applied Analysis, 2021, 20 (1) : 449-465. doi: 10.3934/cpaa.2020276

2019 Impact Factor: 0.734

Tools

Metrics

  • PDF downloads (86)
  • HTML views (60)
  • Cited by (4)

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences