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]

José Joaquín Bernal, Diana H. Bueno-Carreño, Juan Jacobo Simón. Cyclic and BCH codes whose minimum distance equals their maximum BCH bound. Advances in Mathematics of Communications, 2016, 10 (2) : 459-474. doi: 10.3934/amc.2016018
[2]

Kwankyu Lee. Decoding of differential AG codes. Advances in Mathematics of Communications, 2016, 10 (2) : 307-319. doi: 10.3934/amc.2016007
[3]

Elisa Gorla, Felice Manganiello, Joachim Rosenthal. An algebraic approach for decoding spread codes. Advances in Mathematics of Communications, 2012, 6 (4) : 443-466. doi: 10.3934/amc.2012.6.443
[4]

Washiela Fish, Jennifer D. Key, Eric Mwambene. Partial permutation decoding for simplex codes. Advances in Mathematics of Communications, 2012, 6 (4) : 505-516. doi: 10.3934/amc.2012.6.505
[5]

Alexander Barg, Arya Mazumdar, Gilles Zémor. Weight distribution and decoding of codes on hypergraphs. Advances in Mathematics of Communications, 2008, 2 (4) : 433-450. doi: 10.3934/amc.2008.2.433
[6]

Terasan Niyomsataya, Ali Miri, Monica Nevins. Decoding affine reflection group codes with trellises. Advances in Mathematics of Communications, 2012, 6 (4) : 385-400. doi: 10.3934/amc.2012.6.385
[7]

Heide Gluesing-Luerssen, Uwe Helmke, José Ignacio Iglesias Curto. Algebraic decoding for doubly cyclic convolutional codes. Advances in Mathematics of Communications, 2010, 4 (1) : 83-99. doi: 10.3934/amc.2010.4.83
[8]

Robert F. Bailey, John N. Bray. Decoding the Mathieu group M12. Advances in Mathematics of Communications, 2007, 1 (4) : 477-487. doi: 10.3934/amc.2007.1.477
[9]

Qun Lin, Antoinette Tordesillas. Towards an optimization theory for deforming dense granular materials: Minimum cost maximum flow solutions. Journal of Industrial & Management Optimization, 2014, 10 (1) : 337-362. doi: 10.3934/jimo.2014.10.337
[10]

Hannes Bartz, Antonia Wachter-Zeh. Efficient decoding of interleaved subspace and Gabidulin codes beyond their unique decoding radius using Gröbner bases. Advances in Mathematics of Communications, 2018, 12 (4) : 773-804. doi: 10.3934/amc.2018046
[11]

Jie Huang, Xiaoping Yang, Yunmei Chen. A fast algorithm for global minimization of maximum likelihood based on ultrasound image segmentation. Inverse Problems & Imaging, 2011, 5 (3) : 645-657. doi: 10.3934/ipi.2011.5.645
[12]

Joan-Josep Climent, Diego Napp, Raquel Pinto, Rita Simões. Decoding of $2$D convolutional codes over an erasure channel. Advances in Mathematics of Communications, 2016, 10 (1) : 179-193. doi: 10.3934/amc.2016.10.179
[13]

Johan Rosenkilde. Power decoding Reed-Solomon codes up to the Johnson radius. Advances in Mathematics of Communications, 2018, 12 (1) : 81-106. doi: 10.3934/amc.2018005
[14]

Irene I. Bouw, Sabine Kampf. Syndrome decoding for Hermite codes with a Sugiyama-type algorithm. Advances in Mathematics of Communications, 2012, 6 (4) : 419-442. doi: 10.3934/amc.2012.6.419
[15]

Anas Chaaban, Vladimir Sidorenko, Christian Senger. On multi-trial Forney-Kovalev decoding of concatenated codes. Advances in Mathematics of Communications, 2014, 8 (1) : 1-20. doi: 10.3934/amc.2014.8.1
[16]

Vladimir Sidorenko, Christian Senger, Martin Bossert, Victor Zyablov. Single-trial decoding of concatenated codes using fixed or adaptive erasing. Advances in Mathematics of Communications, 2010, 4 (1) : 49-60. doi: 10.3934/amc.2010.4.49
[17]

Peter Beelen, Kristian Brander. Efficient list decoding of a class of algebraic-geometry codes. Advances in Mathematics of Communications, 2010, 4 (4) : 485-518. doi: 10.3934/amc.2010.4.485
[18]

Henry Cohn, Nadia Heninger. Ideal forms of Coppersmith's theorem and Guruswami-Sudan list decoding. Advances in Mathematics of Communications, 2015, 9 (3) : 311-339. doi: 10.3934/amc.2015.9.311
[19]

Alexey Frolov, Victor Zyablov. On the multiple threshold decoding of LDPC codes over GF(q). Advances in Mathematics of Communications, 2017, 11 (1) : 123-137. doi: 10.3934/amc.2017007
[20]

Ahmed S. Mansour, Holger Boche, Rafael F. Schaefer. The secrecy capacity of the arbitrarily varying wiretap channel under list decoding. Advances in Mathematics of Communications, 2019, 13 (1) : 11-39. doi: 10.3934/amc.2019002

2018 Impact Factor: 0.879

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2019 American Institute of Mathematical Sciences