American Institute of Mathematical Sciences

Advanced
doi: 10.3934/amc.2020099

Locally repairable codes with high availability based on generalised quadrangles

Michel Lavrauw 1, and  Geertrui Van de Voorde 2,,

1. 

Faculty of Engineering and Natural Sciences, Sabancı University, 34956 Orhanlı, Tuzla, Istanbul, Turkey
2. 

School of Mathematics and Statistics, University of Canterbury, Private Bag 4800, 8140 Christchurch, New Zealand

* Corresponding author: Geertrui Van de Voorde

Received  January 2020 Revised  May 2020 Published  July 2020

Locally Repairable Codes (LRC's) based on generalised quadrangles were introduced by Pamies-Juarez, Hollmann and Oggier in [3], and bounds on the repairability and availability were derived. In this paper, we determine the values of the repairability and availability of such LRC's for a large portion of the currently known generalised quadrangles. In order to do so, we determine the minimum weight of the codes of translation generalised quadrangles and characterise the codewords of minimum weight.

Keywords: linear code, LRC code, generalised quadrangle, egg.
Mathematics Subject Classification: 51E12, 51E20, 94B05.
Citation: Michel Lavrauw, Geertrui Van de Voorde. Locally repairable codes with high availability based on generalised quadrangles. Advances in Mathematics of Communications, doi: 10.3934/amc.2020099
References:
[1] E. F. Assmus, Jr. and J. D. Key, Designs and Their Codes, Cambridge University Press, Cambridge, 1992.  doi: 10.1017/CBO9781316529836.  Google Scholar
[2]

B. Bagchi and N. S. N. Sastry, Codes associated with generalized polygons, Geom. Dedicata, 27 (1988), 1-8.  doi: 10.1007/BF00181609.  Google Scholar

[3]

L. Pamies-Juarez, H. D. L. Hollmann and F. Oggier, Locally repairable codes with multiple repair alternatives, In IEEE International Symposium on Information Theory - Proceedings (ISIT), 2013,892–896. doi: 10.1109/ISIT.2013.6620355.  Google Scholar

[4]

P. Delsarte, J. M. Goethals and F. J. MacWilliams, On generalized Reed-Muller codes and their relatives, Information and Control, 16 (1970), 403-442.  doi: 10.1016/S0019-9958(70)90214-7.  Google Scholar

[5]

P. Gopalan, C. Huang, H. Simitci and and S. Yekhanin, On the locality of codeword symbols, IEEE Trans. Inform. Theory, 58 (2012), 6925-6934.  doi: 10.1109/TIT.2012.2208937.  Google Scholar

[6]

S. J. Johnson and S. R. Weller, Codes for iterative decoding from partial geometries, IEEE Trans. Comm., 52 (2004), 236-243.  doi: 10.1109/ISIT.2002.1023582.  Google Scholar

[7]

T. Kasami and N. Tokura, On the weight structure of Reed-Muller codes, IEEE Trans. Inf. Theory, 16 (1970), 752-759.  doi: 10.1109/tit.1970.1054545.  Google Scholar

[8]

J. L. Kim, K. E. Mellinger and L. Storme, Small weight codewords in LDPC codes defined by (dual) classical generalised quadrangles, Des. Codes Cryptogr., 42 (2007), 73-92.  doi: 10.1007/s10623-006-9017-6.  Google Scholar

[9]

M. Lavrauw, Scattered Subspaces with Respect to Spreads and Eggs in Finite Projective Spaces, PhD thesis, Technical University of Eindhoven, The Netherlands, 2001.  Google Scholar

[10]

M. Lavrauw and G. Van de Voorde, Field reduction and linear sets in finite geometry, Topics in Finite Fields, Contemp. Math., volume 632, Amer. Math. Soc., Providence, RI, 2015,271–293. doi: 10.1090/conm/632/12633.  Google Scholar

[11]

S. E. Payne and J. A. Thas, Finite Generalized Quadrangles, Pitman Advanced Publishing Program, Boston, MA, 1984.  Google Scholar

[12]

V. Pepe, L. Storme and G. Van de Voorde, Small weight codewords in the LDPC codes arising from linear representations of geometries, J. Combin. Des., 17 (2009), 1-24.  doi: 10.1002/jcd.20179.  Google Scholar

[13]

R. Rolland, The second weight of generalized Reed–Muller codes in most cases, Cryptogr. Commun., 2 (2010), 19-40.  doi: 10.1007/s12095-009-0014-2.  Google Scholar

[14]

I. Tamo, A. Barg and A. Frolov, Bounds on the parameters of locally recoverable codes, IEEE Trans. Inform. Theory, 62 (2016), 3070-3083.  doi: 10.1109/TIT.2016.2518663.  Google Scholar

[15]

G. Van de Voorde, Blocking Sets in Finite Projective Spaces and Coding Theory, PhD thesis, Ghent University, Belgium, 2010. Google Scholar

show all references

References:
[1] E. F. Assmus, Jr. and J. D. Key, Designs and Their Codes, Cambridge University Press, Cambridge, 1992.  doi: 10.1017/CBO9781316529836.  Google Scholar
[2]

B. Bagchi and N. S. N. Sastry, Codes associated with generalized polygons, Geom. Dedicata, 27 (1988), 1-8.  doi: 10.1007/BF00181609.  Google Scholar

[3]

L. Pamies-Juarez, H. D. L. Hollmann and F. Oggier, Locally repairable codes with multiple repair alternatives, In IEEE International Symposium on Information Theory - Proceedings (ISIT), 2013,892–896. doi: 10.1109/ISIT.2013.6620355.  Google Scholar

[4]

P. Delsarte, J. M. Goethals and F. J. MacWilliams, On generalized Reed-Muller codes and their relatives, Information and Control, 16 (1970), 403-442.  doi: 10.1016/S0019-9958(70)90214-7.  Google Scholar

[5]

P. Gopalan, C. Huang, H. Simitci and and S. Yekhanin, On the locality of codeword symbols, IEEE Trans. Inform. Theory, 58 (2012), 6925-6934.  doi: 10.1109/TIT.2012.2208937.  Google Scholar

[6]

S. J. Johnson and S. R. Weller, Codes for iterative decoding from partial geometries, IEEE Trans. Comm., 52 (2004), 236-243.  doi: 10.1109/ISIT.2002.1023582.  Google Scholar

[7]

T. Kasami and N. Tokura, On the weight structure of Reed-Muller codes, IEEE Trans. Inf. Theory, 16 (1970), 752-759.  doi: 10.1109/tit.1970.1054545.  Google Scholar

[8]

J. L. Kim, K. E. Mellinger and L. Storme, Small weight codewords in LDPC codes defined by (dual) classical generalised quadrangles, Des. Codes Cryptogr., 42 (2007), 73-92.  doi: 10.1007/s10623-006-9017-6.  Google Scholar

[9]

M. Lavrauw, Scattered Subspaces with Respect to Spreads and Eggs in Finite Projective Spaces, PhD thesis, Technical University of Eindhoven, The Netherlands, 2001.  Google Scholar

[10]

M. Lavrauw and G. Van de Voorde, Field reduction and linear sets in finite geometry, Topics in Finite Fields, Contemp. Math., volume 632, Amer. Math. Soc., Providence, RI, 2015,271–293. doi: 10.1090/conm/632/12633.  Google Scholar

[11]

S. E. Payne and J. A. Thas, Finite Generalized Quadrangles, Pitman Advanced Publishing Program, Boston, MA, 1984.  Google Scholar

[12]

V. Pepe, L. Storme and G. Van de Voorde, Small weight codewords in the LDPC codes arising from linear representations of geometries, J. Combin. Des., 17 (2009), 1-24.  doi: 10.1002/jcd.20179.  Google Scholar

[13]

R. Rolland, The second weight of generalized Reed–Muller codes in most cases, Cryptogr. Commun., 2 (2010), 19-40.  doi: 10.1007/s12095-009-0014-2.  Google Scholar

[14]

I. Tamo, A. Barg and A. Frolov, Bounds on the parameters of locally recoverable codes, IEEE Trans. Inform. Theory, 62 (2016), 3070-3083.  doi: 10.1109/TIT.2016.2518663.  Google Scholar

[15]

G. Van de Voorde, Blocking Sets in Finite Projective Spaces and Coding Theory, PhD thesis, Ghent University, Belgium, 2010. Google Scholar

[1]

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
[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]

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
[4]

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
[5]

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
[6]

Sascha Kurz. The $[46, 9, 20]_2$ code is unique. Advances in Mathematics of Communications, 2021, 15 (3) : 415-422. doi: 10.3934/amc.2020074
[7]

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
[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]

Jorge P. Arpasi. On the non-Abelian group code capacity of memoryless channels. Advances in Mathematics of Communications, 2020, 14 (3) : 423-436. doi: 10.3934/amc.2020058
[10]

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
[11]

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
[12]

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
[13]

Evangelos Evangelou. Approximate Bayesian inference for geostatistical generalised linear models. Foundations of Data Science, 2019, 1 (1) : 39-60. doi: 10.3934/fods.2019002
[14]

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
[15]

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
[16]

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
[17]

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
[18]

Pedro Branco. A post-quantum UC-commitment scheme in the global random oracle model from code-based assumptions. Advances in Mathematics of Communications, 2021, 15 (1) : 113-130. doi: 10.3934/amc.2020046
[19]

Terry Shue Chien Lau, Chik How Tan. Polynomial-time plaintext recovery attacks on the IKKR code-based cryptosystems. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2020132
[20]

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

2019 Impact Factor: 0.734

Tools

Article outline

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences