doi: 10.3934/amc.2020019

Locally recoverable codes from algebraic curves with separated variables

1. 

Department of Applied Mathematics, University of Valladolid, Avda Salamanca SN, 47014, Valladolid, Castilla, Spain

2. 

Departamento de Matemática, Universidade Federal de Mato Grosso, Av. F. C. Costa 2367, 78060-900, Cuiabá, Brazil

3. 

Institute of Mathematics, Statistics and Computer Science, University of Campinas, Cidade Universitaria "Zeferino Vaz", Barão Geraldo, 13083-859, Campinas, Brazil

* Corresponding author

Received  June 2018 Published  September 2019

Fund Project: The first author was supported by Spanish Ministerio de Economía y Competitividad under grant MTM2015-65764-C3-1-P MINECO/FEDER. The second author was supported by CNPq-Brazil, under grants 201584/2015-8 and 159852/2014-5. The third author was supported by CNPq-Brazil under grant 310623/2017-0

A Locally Recoverable code is an error-correcting code such that any erasure in a single coordinate of a codeword can be recovered from a small subset of other coordinates. We study Locally Recoverable Algebraic Geometry codes arising from certain curves defined by equations with separated variables. The recovery of erasures is obtained by means of Lagrangian interpolation in general, and simply by one addition in some particular cases.

Citation: Carlos Munuera, Wanderson Tenório, Fernando Torres. Locally recoverable codes from algebraic curves with separated variables. Advances in Mathematics of Communications, doi: 10.3934/amc.2020019
References:
[1]

E. Ballico and C. Marcolla, Higher Hamming weights for locally recoverable codes on algebraic curves, Finite Fields and Their Applications, 40 (2016), 61-72.  doi: 10.1016/j.ffa.2016.03.004.  Google Scholar

[2]

A. BargI. Tamo and S. Vlǎduţ, Locally recoverable codes on algebraic curves, IEEE Trans. Inform. Theory, 63 (2015), 4928-4939.  doi: 10.1109/TIT.2017.2700859.  Google Scholar

[3]

D. Cox, J. Little and D. O'Shea, Ideals, Varieties, and Algorithms, Undergraduate Texts in Mathematics, Springer, New York, 1992. doi: 10.1007/978-1-4757-2181-2.  Google Scholar

[4]

P. GopalanC. HuangH. Simitci and S. Yekhanin, On the locality of codeword symbols, IEEE Transactions on Information Theory, 58 (2012), 6925-6934.  doi: 10.1109/TIT.2012.2208937.  Google Scholar

[5]

K. HaymakerB. Malmskog and G. L. Matthews, Locally recoverable codes with availability $t\geq 2$ from fiber products of curves, Advances in Mathematics of Communications, 12 (2018), 317-336.  doi: 10.3934/amc.2018020.  Google Scholar

[6] J. W. P. HirschfeldG. Korchmáros and F. Torres, Algebraic Curves Over a Finite Field, Princeton University Press, Princeton, NJ, 2008.   Google Scholar
[7]

S. KondoT. Katagiri and T. Ogihara, Automorphism groups of one-point codes from the curves $y^{q}+y = x^{q^r+1}$, IEEE Transactions on Information Theory, 47 (2001), 2573-2579.  doi: 10.1109/18.945272.  Google Scholar

[8]

O. Kolosov, A. Barg, I. Tamo and G. Yadgar, Optimal LRC codes for all lengths $n\leq q$, preprint, (2018), arXiv: 1802.00157. Google Scholar

[9]

R. Lidl and H. Niederreiter, Finite Fields, Encyclopedia of Mathematics and its Applications, 20. Addison-Wesley Publishing Company, Advanced Book Program, Reading, MA, 1983.  Google Scholar

[10]

S. Miura, Algebraic geometric codes on certain plane curves, IEICE Transactions on Fundamentals, 75 (1992), 1735-1745.  doi: 10.1002/ecjc.4430761201.  Google Scholar

[11]

C. Munuera and W. Olaya-León, An introduction to algebraic geometry codes, in Algebra for Secure and Reliable Communication Modelling, AMS-Contemporary Mathematics, Providence, RI, 642 (2015), 87–117. doi: 10.1090/conm/642/12882.  Google Scholar

[12]

C. MunueraA. Sepúlveda and F. Torres, Castle curves and codes, Advances in Mathematics of Communications, 3 (2009), 399-408.  doi: 10.3934/amc.2009.3.399.  Google Scholar

[13]

C. Munuera and W. Tenório, Locally Recoverable codes from rational maps, Finite Fields and Their Applications, 54 (2018), 80-100.  doi: 10.1016/j.ffa.2018.07.005.  Google Scholar

[14] R. PellikaanX. W. WuS. Bulygin and R. Jurrius, Codes, Cryptology and Curves with Computer Algebra, Cambridge University Press, Cambridge, 2017.   Google Scholar
[15]

A. Sepulveda and G. Tizziotti, Weierstrass semigroups and codes over the curve $y^{q}+y = x^{q^r+1}$, Advances in Mathematics of Communications, 8 (2014), 67-72.  doi: 10.3934/amc.2014.8.67.  Google Scholar

[16]

H. Stichtenoth, Algebraic Function Fields and Codes, Graduate Texts in Mathematics, 254. Springer-Verlag, Berlin, 2009.  Google Scholar

[17]

I. Tamo and A. Barg, A family of optimal locally recoverable codes, IEEE Transactions on Information Theory, 60 (2014), 4661-4676.  doi: 10.1109/TIT.2014.2321280.  Google Scholar

[18]

V. K. Wei, Generalized Hamming weights for linear codes, IEEE Transactions on Information Theory, 37 (1991), 1412-1418.  doi: 10.1109/18.133259.  Google Scholar

show all references

References:
[1]

E. Ballico and C. Marcolla, Higher Hamming weights for locally recoverable codes on algebraic curves, Finite Fields and Their Applications, 40 (2016), 61-72.  doi: 10.1016/j.ffa.2016.03.004.  Google Scholar

[2]

A. BargI. Tamo and S. Vlǎduţ, Locally recoverable codes on algebraic curves, IEEE Trans. Inform. Theory, 63 (2015), 4928-4939.  doi: 10.1109/TIT.2017.2700859.  Google Scholar

[3]

D. Cox, J. Little and D. O'Shea, Ideals, Varieties, and Algorithms, Undergraduate Texts in Mathematics, Springer, New York, 1992. doi: 10.1007/978-1-4757-2181-2.  Google Scholar

[4]

P. GopalanC. HuangH. Simitci and S. Yekhanin, On the locality of codeword symbols, IEEE Transactions on Information Theory, 58 (2012), 6925-6934.  doi: 10.1109/TIT.2012.2208937.  Google Scholar

[5]

K. HaymakerB. Malmskog and G. L. Matthews, Locally recoverable codes with availability $t\geq 2$ from fiber products of curves, Advances in Mathematics of Communications, 12 (2018), 317-336.  doi: 10.3934/amc.2018020.  Google Scholar

[6] J. W. P. HirschfeldG. Korchmáros and F. Torres, Algebraic Curves Over a Finite Field, Princeton University Press, Princeton, NJ, 2008.   Google Scholar
[7]

S. KondoT. Katagiri and T. Ogihara, Automorphism groups of one-point codes from the curves $y^{q}+y = x^{q^r+1}$, IEEE Transactions on Information Theory, 47 (2001), 2573-2579.  doi: 10.1109/18.945272.  Google Scholar

[8]

O. Kolosov, A. Barg, I. Tamo and G. Yadgar, Optimal LRC codes for all lengths $n\leq q$, preprint, (2018), arXiv: 1802.00157. Google Scholar

[9]

R. Lidl and H. Niederreiter, Finite Fields, Encyclopedia of Mathematics and its Applications, 20. Addison-Wesley Publishing Company, Advanced Book Program, Reading, MA, 1983.  Google Scholar

[10]

S. Miura, Algebraic geometric codes on certain plane curves, IEICE Transactions on Fundamentals, 75 (1992), 1735-1745.  doi: 10.1002/ecjc.4430761201.  Google Scholar

[11]

C. Munuera and W. Olaya-León, An introduction to algebraic geometry codes, in Algebra for Secure and Reliable Communication Modelling, AMS-Contemporary Mathematics, Providence, RI, 642 (2015), 87–117. doi: 10.1090/conm/642/12882.  Google Scholar

[12]

C. MunueraA. Sepúlveda and F. Torres, Castle curves and codes, Advances in Mathematics of Communications, 3 (2009), 399-408.  doi: 10.3934/amc.2009.3.399.  Google Scholar

[13]

C. Munuera and W. Tenório, Locally Recoverable codes from rational maps, Finite Fields and Their Applications, 54 (2018), 80-100.  doi: 10.1016/j.ffa.2018.07.005.  Google Scholar

[14] R. PellikaanX. W. WuS. Bulygin and R. Jurrius, Codes, Cryptology and Curves with Computer Algebra, Cambridge University Press, Cambridge, 2017.   Google Scholar
[15]

A. Sepulveda and G. Tizziotti, Weierstrass semigroups and codes over the curve $y^{q}+y = x^{q^r+1}$, Advances in Mathematics of Communications, 8 (2014), 67-72.  doi: 10.3934/amc.2014.8.67.  Google Scholar

[16]

H. Stichtenoth, Algebraic Function Fields and Codes, Graduate Texts in Mathematics, 254. Springer-Verlag, Berlin, 2009.  Google Scholar

[17]

I. Tamo and A. Barg, A family of optimal locally recoverable codes, IEEE Transactions on Information Theory, 60 (2014), 4661-4676.  doi: 10.1109/TIT.2014.2321280.  Google Scholar

[18]

V. K. Wei, Generalized Hamming weights for linear codes, IEEE Transactions on Information Theory, 37 (1991), 1412-1418.  doi: 10.1109/18.133259.  Google Scholar

Table 1.  Hamming weights of Example 5
$ t $ 1 2 3 4 5 6
lower bound (9) 10 12 13 14 15 16
upper bound (8) 11 12 14 15 17 18
$ t $ 1 2 3 4 5 6
lower bound (9) 10 12 13 14 15 16
upper bound (8) 11 12 14 15 17 18
[1]

Andrew Klapper, Andrew Mertz. The two covering radius of the two error correcting BCH code. Advances in Mathematics of Communications, 2009, 3 (1) : 83-95. doi: 10.3934/amc.2009.3.83

[2]

Laura Luzzi, Ghaya Rekaya-Ben Othman, Jean-Claude Belfiore. Algebraic reduction for the Golden Code. Advances in Mathematics of Communications, 2012, 6 (1) : 1-26. doi: 10.3934/amc.2012.6.1

[3]

Selim Esedoḡlu, Fadil Santosa. Error estimates for a bar code reconstruction method. Discrete & Continuous Dynamical Systems - B, 2012, 17 (6) : 1889-1902. doi: 10.3934/dcdsb.2012.17.1889

[4]

José Gómez-Torrecillas, F. J. Lobillo, Gabriel Navarro. Information--bit error rate and false positives in an MDS code. Advances in Mathematics of Communications, 2015, 9 (2) : 149-168. doi: 10.3934/amc.2015.9.149

[5]

Irene Márquez-Corbella, Edgar Martínez-Moro, Emilio Suárez-Canedo. On the ideal associated to a linear code. Advances in Mathematics of Communications, 2016, 10 (2) : 229-254. doi: 10.3934/amc.2016003

[6]

Serhii Dyshko. On extendability of additive code isometries. Advances in Mathematics of Communications, 2016, 10 (1) : 45-52. doi: 10.3934/amc.2016.10.45

[7]

Olof Heden. The partial order of perfect codes associated to a perfect code. Advances in Mathematics of Communications, 2007, 1 (4) : 399-412. doi: 10.3934/amc.2007.1.399

[8]

M. Delgado Pineda, E. A. Galperin, P. Jiménez Guerra. MAPLE code of the cubic algorithm for multiobjective optimization with box constraints. Numerical Algebra, Control & Optimization, 2013, 3 (3) : 407-424. doi: 10.3934/naco.2013.3.407

[9]

Masaaki Harada, Takuji Nishimura. An extremal singly even self-dual code of length 88. Advances in Mathematics of Communications, 2007, 1 (2) : 261-267. doi: 10.3934/amc.2007.1.261

[10]

M. De Boeck, P. Vandendriessche. On the dual code of points and generators on the Hermitian variety $\mathcal{H}(2n+1,q^{2})$. Advances in Mathematics of Communications, 2014, 8 (3) : 281-296. doi: 10.3934/amc.2014.8.281

[11]

Michael Kiermaier, Johannes Zwanzger. A $\mathbb Z$4-linear code of high minimum Lee distance derived from a hyperoval. Advances in Mathematics of Communications, 2011, 5 (2) : 275-286. doi: 10.3934/amc.2011.5.275

[12]

Sihuang Hu, Gabriele Nebe. There is no $[24,12,9]$ doubly-even self-dual code over $\mathbb F_4$. Advances in Mathematics of Communications, 2016, 10 (3) : 583-588. doi: 10.3934/amc.2016027

[13]

Anna-Lena Horlemann-Trautmann, Kyle Marshall. New criteria for MRD and Gabidulin codes and some Rank-Metric code constructions. Advances in Mathematics of Communications, 2017, 11 (3) : 533-548. doi: 10.3934/amc.2017042

[14]

Masaaki Harada, Ethan Novak, Vladimir D. Tonchev. The weight distribution of the self-dual $[128,64]$ polarity design code. Advances in Mathematics of Communications, 2016, 10 (3) : 643-648. doi: 10.3934/amc.2016032

[15]

Denis S. Krotov, Patric R. J.  Östergård, Olli Pottonen. Non-existence of a ternary constant weight $(16,5,15;2048)$ diameter perfect code. Advances in Mathematics of Communications, 2016, 10 (2) : 393-399. doi: 10.3934/amc.2016013

[16]

Jianying Fang. 5-SEEDs from the lifted Golay code of length 24 over Z4. Advances in Mathematics of Communications, 2017, 11 (1) : 259-266. doi: 10.3934/amc.2017017

[17]

Pedro Branco. A post-quantum UC-commitment scheme in the global random oracle model from code-based assumptions. Advances in Mathematics of Communications, 2019, 0 (0) : 0-0. doi: 10.3934/amc.2020046

[18]

Daniel Heinlein, Michael Kiermaier, Sascha Kurz, Alfred Wassermann. A subspace code of size $ \bf{333} $ in the setting of a binary $ \bf{q} $-analog of the Fano plane. Advances in Mathematics of Communications, 2019, 13 (3) : 457-475. doi: 10.3934/amc.2019029

[19]

Martino Borello, Francesca Dalla Volta, Gabriele Nebe. The automorphism group of a self-dual $[72,36,16]$ code does not contain $\mathcal S_3$, $\mathcal A_4$ or $D_8$. Advances in Mathematics of Communications, 2013, 7 (4) : 503-510. doi: 10.3934/amc.2013.7.503

[20]

Kathryn Haymaker, Beth Malmskog, Gretchen L. Matthews. Locally recoverable codes with availability t≥2 from fiber products of curves. Advances in Mathematics of Communications, 2018, 12 (2) : 317-336. doi: 10.3934/amc.2018020

2018 Impact Factor: 0.879

Article outline

Figures and Tables

[Back to Top]