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)$
-
Previous Article
On complementary dual additive cyclic codes
- AMC Home
- This Issue
-
Next Article
A multi-dimensional block-circulant perfect array construction
May
2017, 11(2): 359-366.
doi: 10.3934/amc.2017029
Minimum dimensional Hamming embeddings
University of Campinas, São Paulo, Brazil |
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.
|
| [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. |
| [3] |
R. G. L. D'Oliveira and M. Firer, Channel metrization, preprint, arXiv: 1510.03104 |
| [4] |
F. Eisenbrand, Fast Integer Programming in Fixed Dimension, Springer, Berlin, 2003.
doi: 10.1007/978-3-540-39658-1_20.
|
| [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. |
| [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. |
show all references
References:
| [1] |
V. Chvétal,
Recognizing intersection patterns, Ann. Discrete Math., 8 (1980), 249-251.
|
| [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. |
| [3] |
R. G. L. D'Oliveira and M. Firer, Channel metrization, preprint, arXiv: 1510.03104 |
| [4] |
F. Eisenbrand, Fast Integer Programming in Fixed Dimension, Springer, Berlin, 2003.
doi: 10.1007/978-3-540-39658-1_20.
|
| [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. |
| [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. |
| [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] |
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 |
| [7] |
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 |
| [8] |
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 |
| [9] |
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 |
| [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
Other articles
by authors
[Back to Top]