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
A multi-dimensional block-circulant perfect array construction
- AMC Home
- This Issue
-
Next Article
On complementary dual additive cyclic codes
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 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. |
| [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 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. |
| [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] |
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] |
Anna-Lena Horlemann-Trautmann, Violetta Weger. Information set decoding in the Lee metric with applications to cryptography. Advances in Mathematics of Communications, 2020 doi: 10.3934/amc.2020089 |
| [10] |
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 |
| [11] |
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 |
| [12] |
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 |
| [13] |
Saroja Kumar Singh. Moderate deviation for maximum likelihood estimators from single server queues. Probability, Uncertainty and Quantitative Risk, 2020, 5 (0) : 2-. doi: 10.1186/s41546-020-00044-z |
| [14] |
San Ling, Buket Özkaya. New bounds on the minimum distance of cyclic codes. Advances in Mathematics of Communications, 2021, 15 (1) : 1-8. doi: 10.3934/amc.2020038 |
| [15] |
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 |
| [16] |
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 |
| [17] |
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 |
| [18] |
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 |
| [19] |
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 |
| [20] |
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 |
2020 Impact Factor: 0.935
Tools
Metrics
Other articles
by authors
[Back to Top]