    August  2020, 14(3): 437-453. doi: 10.3934/amc.2020047

## A construction of $\mathbb{F}_2$-linear cyclic, MDS codes

 1 Instituto de Matemática, Estatística e Computação Científica, Universidade Estadual de Campinas, Campinas, Brazil 2 Departament de Matemàtiques, Universitat d'Alacant, Alacant, Spain 3 School of Mathematics and Statistics, Carleton University, Ottawa, Canada

Received  November 2018 Revised  June 2019 Published  November 2019

Fund Project: The first author was supported by CAPES (Brazil). The work of the second author was partially supported by Spanish grants AICO/2017/128 of the Generalitat Valenciana and VIGROB-287 of the Universitat d'Alacant. The third and fourth authors were supported by NSERC (Canada). The first, third and fourth authors acknowledge support from FAPESP SPRINT grant 2016/50476-0

In this paper we construct $\mathbb{F}_2$-linear codes over $\mathbb{F}_{2}^{b}$ with length $n$ and dimension $n-r$ where $n = rb$. These codes have good properties, namely cyclicity, low density parity-check matrices and maximum distance separation in some cases. For the construction, we consider an odd prime $p$, let $n = p-1$ and utilize a partition of $\mathbb{Z}_n$. Then we apply a Zech logarithm to the elements of these sets and use the results to construct an index array which represents the parity-check matrix of the code. These codes are always cyclic and the density of the parity-check and the generator matrices decreases to $0$ as $n$ grows (for a fixed $r$). When $r = 2$ we prove that these codes are always maximum distance separable. For higher $r$ some of them retain this property.

Citation: Sara D. Cardell, Joan-Josep Climent, Daniel Panario, Brett Stevens. A construction of $\mathbb{F}_2$-linear cyclic, MDS codes. Advances in Mathematics of Communications, 2020, 14 (3) : 437-453. doi: 10.3934/amc.2020047
##### References:
  M. Barbier, C. Chabot and G. Quintin, On quasi-cyclic codes as a generalization of cyclic codes, Finite Fields and Their Applications, 18 (2012), 904-919.  doi: 10.1016/j.ffa.2012.06.003.  Google Scholar  R. Barbulescu, C. Bouvier, J. Detrey, P. Gaudry, H. Jeljeli, E. Thomé, M. Videau and P. Zimmermann, Discrete logarithm in $GF(2^{809})$ with FFS, PKC 2014: Public-Key Cryptography-PKC 2014, (2014), 221–238, http://dx.doi.org/10.1007/978-3-642-54631-0_13. doi: 10.1007/978-3-642-54631-0.  Google Scholar  M. Blaum, J. Brady, J. Bruck and J. Menon, EVENODD: An efficient scheme for tolerating double disk failures in RAID architectures, IEEE Transactions on Computers, 44 (1995), 192-202.  doi: 10.1109/12.364531. Google Scholar  M. Blaum and J. Bruck, Decoding the Golay code with Venn diagrams, IEEE Transactions on Information Theory, 36 (1990), 906-910.  doi: 10.1109/18.53756.  Google Scholar  M. Blaum, J. Bruck and A. Vardy, MDS array codes with independent parity symbols, IEEE Transactions on Information Theory, 42 (1995), 529-542.  doi: 10.1109/ISIT.1995.535761. Google Scholar  M. Blaum, P. G. Farrell and H. C. A. van Tilborg, Array codes, in Handbook of Coding Theory, North-Holland, Amsterdam, 1/2 (1998), 1855–1909. Google Scholar  M. Blaum and R. M. Roth, New array codes for multiple phased burst correction, IEEE Transactions on Information Theory, 39 (1993), 66-77.  doi: 10.1109/18.179343.  Google Scholar  M. Blaum and R. M. Roth, On lowest density MDS codes, IEEE Transactions on Information Theory, 45 (1999), 46-59.  doi: 10.1109/18.746771.  Google Scholar  S. D. Cardell, Constructions of MDS Codes over Extension Alphabets, PhD thesis, Departamento de Ciencia de la Computación e Inteligencia Artificial, Universidad de Alicante, Alicante, España, 2012. Google Scholar  S. D. Cardell, J.-J. Climent and V. Requena, A construction of MDS array codes, WIT Transactions on Information and Communication Technologies, 45 (2013), 47-58.  doi: 10.2495/DATA130051. Google Scholar  S. D. Cardell and A. Fúster-Sabater, Recovering decimation-based cryptographic sequences by means of linear CAs, (2018), https://arXiv.org/abs/1802.02206. Google Scholar  G. A. Gibson, Redundant Disk Arrays: Reliable, Parallel Secondary Storage, Cambridge, MA: MIT Press, 1992.   Google Scholar  K. Huber, Some comments on Zech's logarithms, IEEE Transactions on Information Theory, 36 (1990), 946-950.  doi: 10.1109/18.53764.  Google Scholar  A. Kotzig, Hamilton graphs and Hamilton circuits, Theory of Graphs and its Applications, Publ. House Czechoslovak Acad. Sci., Prague, (1964), 63–82. Google Scholar  E. Louidor and R. M. Roth, Lowest density MDS codes over extension alphabets, IEEE Transactions on Information Theory, 52 (2006), 3186-3197.  doi: 10.1109/TIT.2006.876235.  Google Scholar  F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes. I, North-Holland Mathematical Library, Vol. 16. North-Holland Publishing Co., Amsterdam-New York-Oxford, 1977. Google Scholar  E. Mendelsohn and A. Rosa, One-factorizations of the complete graph-A survey, Journal of Graph Theory, 9 (1985), 43-65.  doi: 10.1002/jgt.3190090104.  Google Scholar  M. Sudan, Algorithmic Introduction to Coding Theory, 2002, https://people.csail.mit.edu/madhu/FT02/scribe/lect16.ps. Google Scholar  L. H. Xu and J. Bruck, X-code: MDS array codes with optimal encoding, IEEE Transactions on Information Theory, 45 (1999), 272-276.  doi: 10.1109/18.746809.  Google Scholar  G. V. Zaitzev, V. A. Zinov'ev and N. V. Semakov, Minimum-check-density codes for correcting bytes of errors, erasures, or defects, Problems of Information Transmission, 19 (1983), 197-204. Google Scholar

show all references

##### References:
  M. Barbier, C. Chabot and G. Quintin, On quasi-cyclic codes as a generalization of cyclic codes, Finite Fields and Their Applications, 18 (2012), 904-919.  doi: 10.1016/j.ffa.2012.06.003.  Google Scholar  R. Barbulescu, C. Bouvier, J. Detrey, P. Gaudry, H. Jeljeli, E. Thomé, M. Videau and P. Zimmermann, Discrete logarithm in $GF(2^{809})$ with FFS, PKC 2014: Public-Key Cryptography-PKC 2014, (2014), 221–238, http://dx.doi.org/10.1007/978-3-642-54631-0_13. doi: 10.1007/978-3-642-54631-0.  Google Scholar  M. Blaum, J. Brady, J. Bruck and J. Menon, EVENODD: An efficient scheme for tolerating double disk failures in RAID architectures, IEEE Transactions on Computers, 44 (1995), 192-202.  doi: 10.1109/12.364531. Google Scholar  M. Blaum and J. Bruck, Decoding the Golay code with Venn diagrams, IEEE Transactions on Information Theory, 36 (1990), 906-910.  doi: 10.1109/18.53756.  Google Scholar  M. Blaum, J. Bruck and A. Vardy, MDS array codes with independent parity symbols, IEEE Transactions on Information Theory, 42 (1995), 529-542.  doi: 10.1109/ISIT.1995.535761. Google Scholar  M. Blaum, P. G. Farrell and H. C. A. van Tilborg, Array codes, in Handbook of Coding Theory, North-Holland, Amsterdam, 1/2 (1998), 1855–1909. Google Scholar  M. Blaum and R. M. Roth, New array codes for multiple phased burst correction, IEEE Transactions on Information Theory, 39 (1993), 66-77.  doi: 10.1109/18.179343.  Google Scholar  M. Blaum and R. M. Roth, On lowest density MDS codes, IEEE Transactions on Information Theory, 45 (1999), 46-59.  doi: 10.1109/18.746771.  Google Scholar  S. D. Cardell, Constructions of MDS Codes over Extension Alphabets, PhD thesis, Departamento de Ciencia de la Computación e Inteligencia Artificial, Universidad de Alicante, Alicante, España, 2012. Google Scholar  S. D. Cardell, J.-J. Climent and V. Requena, A construction of MDS array codes, WIT Transactions on Information and Communication Technologies, 45 (2013), 47-58.  doi: 10.2495/DATA130051. Google Scholar  S. D. Cardell and A. Fúster-Sabater, Recovering decimation-based cryptographic sequences by means of linear CAs, (2018), https://arXiv.org/abs/1802.02206. Google Scholar  G. A. Gibson, Redundant Disk Arrays: Reliable, Parallel Secondary Storage, Cambridge, MA: MIT Press, 1992.   Google Scholar  K. Huber, Some comments on Zech's logarithms, IEEE Transactions on Information Theory, 36 (1990), 946-950.  doi: 10.1109/18.53764.  Google Scholar  A. Kotzig, Hamilton graphs and Hamilton circuits, Theory of Graphs and its Applications, Publ. House Czechoslovak Acad. Sci., Prague, (1964), 63–82. Google Scholar  E. Louidor and R. M. Roth, Lowest density MDS codes over extension alphabets, IEEE Transactions on Information Theory, 52 (2006), 3186-3197.  doi: 10.1109/TIT.2006.876235.  Google Scholar  F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes. I, North-Holland Mathematical Library, Vol. 16. North-Holland Publishing Co., Amsterdam-New York-Oxford, 1977. Google Scholar  E. Mendelsohn and A. Rosa, One-factorizations of the complete graph-A survey, Journal of Graph Theory, 9 (1985), 43-65.  doi: 10.1002/jgt.3190090104.  Google Scholar  M. Sudan, Algorithmic Introduction to Coding Theory, 2002, https://people.csail.mit.edu/madhu/FT02/scribe/lect16.ps. Google Scholar  L. H. Xu and J. Bruck, X-code: MDS array codes with optimal encoding, IEEE Transactions on Information Theory, 45 (1999), 272-276.  doi: 10.1109/18.746809.  Google Scholar  G. V. Zaitzev, V. A. Zinov'ev and N. V. Semakov, Minimum-check-density codes for correcting bytes of errors, erasures, or defects, Problems of Information Transmission, 19 (1983), 197-204. Google Scholar
Index array constructed in Section 3
 $0$ $1$ $2$ $\cdots$ $p-3$ $p-2$ $D_0$ $D_0+1$ $D_0+2$ $\cdots$ $D_0+p-3$ $D_0+p-2$ $D_1$ $D_1+1$ $D_1+2$ $\cdots$ $D_1+p-3$ $D_1+p-2$ $\vdots$ $\vdots$ $\vdots$  $\vdots$ $\vdots$ $D_{u-1}$ $D_{u-1}+1$ $D_{u-1}+2$ $\cdots$ $D_{u-1}+p-3$ $D_{u-1}+p-2$ $D_{u+1}$ $D_{u+1}+1$ $D_{u+1}+2$ $\cdots$ $D_{u+1}+p-3$ $D_{u+1}+p-2$ $\vdots$ $\vdots$ $\vdots$  $\vdots$ $\vdots$ $D_{b-1}$ $D_{b-1}+1$ $D_{b-1}+2$ $\cdots$ $D_{b-1}+p-3$ $D_{b-1}+p-2$
 $0$ $1$ $2$ $\cdots$ $p-3$ $p-2$ $D_0$ $D_0+1$ $D_0+2$ $\cdots$ $D_0+p-3$ $D_0+p-2$ $D_1$ $D_1+1$ $D_1+2$ $\cdots$ $D_1+p-3$ $D_1+p-2$ $\vdots$ $\vdots$ $\vdots$  $\vdots$ $\vdots$ $D_{u-1}$ $D_{u-1}+1$ $D_{u-1}+2$ $\cdots$ $D_{u-1}+p-3$ $D_{u-1}+p-2$ $D_{u+1}$ $D_{u+1}+1$ $D_{u+1}+2$ $\cdots$ $D_{u+1}+p-3$ $D_{u+1}+p-2$ $\vdots$ $\vdots$ $\vdots$  $\vdots$ $\vdots$ $D_{b-1}$ $D_{b-1}+1$ $D_{b-1}+2$ $\cdots$ $D_{b-1}+p-3$ $D_{b-1}+p-2$
Index array representing the parity-check matrix when $r = 2$
 $0$ $1$ $2$ $\cdots$ $p-3$ $p-2$ $D_1$ $D_1+1$ $D_1+2$ $\cdots$ $D_1+p-3$ $D_1+p-2$ $D_2$ $D_2+1$ $D_2+2$ $\cdots$ $D_2+p-3$ $D_2+p-2$ $\vdots$ $\vdots$ $\vdots$  $\vdots$ $\vdots$ $D_{b-1}$ $D_{b-1}+1$ $D_{b-1}+2$ $\cdots$ $D_{b-1}+p-3$ $D_{b-1}+p-2$
 $0$ $1$ $2$ $\cdots$ $p-3$ $p-2$ $D_1$ $D_1+1$ $D_1+2$ $\cdots$ $D_1+p-3$ $D_1+p-2$ $D_2$ $D_2+1$ $D_2+2$ $\cdots$ $D_2+p-3$ $D_2+p-2$ $\vdots$ $\vdots$ $\vdots$  $\vdots$ $\vdots$ $D_{b-1}$ $D_{b-1}+1$ $D_{b-1}+2$ $\cdots$ $D_{b-1}+p-3$ $D_{b-1}+p-2$
Index array representing the generator matrix computed from the index array in Table 2
 $B$ $B+(b-1)$ $B+2(b-1)$ $B+3(b-1)$ $B+4(b-1)$ $\cdots$ $B+(n-1)(b-1)$ $0$ $b-1$ $2(b-1)$ $3(b-1)$ $4(b-1)$ $\cdots$ $(n-1)(b-1)$ $1$ $b$ $2(b-1)+1$ $3(b-1)+1$ $4(b-1)+1$ $\cdots$ $(n-1)(b-1)+1$ $2$ $b+1$ $2(b-1)+2$ $3(b-1)+2$ $4(b-1)+2$ $\cdots$ $(n-1)(b-1)+2$ $\vdots$ $\vdots$ $\vdots$ $\cdots$ $\vdots$  $\vdots$ $b-2$ $2b-3$ $3(b-1)-1$ $4(b-1)-1$ $5(b-1)-1$ $\ldots$ $n(b-1)-1$
 $B$ $B+(b-1)$ $B+2(b-1)$ $B+3(b-1)$ $B+4(b-1)$ $\cdots$ $B+(n-1)(b-1)$ $0$ $b-1$ $2(b-1)$ $3(b-1)$ $4(b-1)$ $\cdots$ $(n-1)(b-1)$ $1$ $b$ $2(b-1)+1$ $3(b-1)+1$ $4(b-1)+1$ $\cdots$ $(n-1)(b-1)+1$ $2$ $b+1$ $2(b-1)+2$ $3(b-1)+2$ $4(b-1)+2$ $\cdots$ $(n-1)(b-1)+2$ $\vdots$ $\vdots$ $\vdots$ $\cdots$ $\vdots$  $\vdots$ $b-2$ $2b-3$ $3(b-1)-1$ $4(b-1)-1$ $5(b-1)-1$ $\ldots$ $n(b-1)-1$
Index array obtained by subtracting $1$ modulo $n$ to every set in the array given in Table 1
 $p-2$ $0$ $1$ $2$ $\cdots$ $p-3$ $D_0+p-2$ $D_0$ $D_0+1$ $D_0+2 %$ $\cdots$ $D_0+p-3$ $D_1+p-2$ $D_1$ $D_1 +1$ $D_1+2 %$ $\cdots$ $D_1+p-3$ $\vdots$ $\vdots$ $\vdots$ $\vdots$  $\vdots$ $D_{u-1}+p-2$ $D_{u-1}$ $D_{u-1}+1$ $D_{u-1}+2 %$ $\cdots$ $D_{u-1}+p-3$ $D_{u+1}+p-2$ $D_{u+1}$ $D_{u+1} +1$ $D_{u+1}+2 %$ $\cdots$ $D_{u+1}+p-3$ $\vdots$ $\vdots$ $\vdots$ $\vdots$  $\vdots$ $D_{b-1}+p-2$ $D_{b-1}$ $D_{b-1} +1$ $D_{b-1}+2$ $\cdots$ $D_{b-1}+p-3$
 $p-2$ $0$ $1$ $2$ $\cdots$ $p-3$ $D_0+p-2$ $D_0$ $D_0+1$ $D_0+2 %$ $\cdots$ $D_0+p-3$ $D_1+p-2$ $D_1$ $D_1 +1$ $D_1+2 %$ $\cdots$ $D_1+p-3$ $\vdots$ $\vdots$ $\vdots$ $\vdots$  $\vdots$ $D_{u-1}+p-2$ $D_{u-1}$ $D_{u-1}+1$ $D_{u-1}+2 %$ $\cdots$ $D_{u-1}+p-3$ $D_{u+1}+p-2$ $D_{u+1}$ $D_{u+1} +1$ $D_{u+1}+2 %$ $\cdots$ $D_{u+1}+p-3$ $\vdots$ $\vdots$ $\vdots$ $\vdots$  $\vdots$ $D_{b-1}+p-2$ $D_{b-1}$ $D_{b-1} +1$ $D_{b-1}+2$ $\cdots$ $D_{b-1}+p-3$
MDS property of $C(p, r, \alpha)$ for different values of $p$ and $r$
 $p$ 5 7 11 13 17 19 23 29 31 37 41 43 $r$ 2 √ √ √ √ √ √ √ √ √ √ √ √ 3 × √ √ √ √ √ 4 × × √ √ × 5 × × × 6 × × × × × 7 × × 8 × × 9 × × 10 × × 11 × 12 × 13 14 × × 15 ×
 $p$ 5 7 11 13 17 19 23 29 31 37 41 43 $r$ 2 √ √ √ √ √ √ √ √ √ √ √ √ 3 × √ √ √ √ √ 4 × × √ √ × 5 × × × 6 × × × × × 7 × × 8 × × 9 × × 10 × × 11 × 12 × 13 14 × × 15 ×
  Parikshit Upadhyaya, Elias Jarlebring, Emanuel H. Rubensson. A density matrix approach to the convergence of the self-consistent field iteration. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 99-115. doi: 10.3934/naco.2020018  Denis Bonheure, Silvia Cingolani, Simone Secchi. Concentration phenomena for the Schrödinger-Poisson system in $\mathbb{R}^2$. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020447  Dan Zhu, Rosemary A. Renaut, Hongwei Li, Tianyou Liu. Fast non-convex low-rank matrix decomposition for separation of potential field data using minimal memory. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020076  Lei Liu, Li Wu. Multiplicity of closed characteristics on $P$-symmetric compact convex hypersurfaces in $\mathbb{R}^{2n}$. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020378  Agnaldo José Ferrari, Tatiana Miguel Rodrigues de Souza. Rotated $A_n$-lattice codes of full diversity. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020118  Peizhao Yu, Guoshan Zhang, Yi Zhang. Decoupling of cubic polynomial matrix systems. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 13-26. doi: 10.3934/naco.2020012  Shengxin Zhu, Tongxiang Gu, Xingping Liu. AIMS: Average information matrix splitting. Mathematical Foundations of Computing, 2020, 3 (4) : 301-308. doi: 10.3934/mfc.2020012  Luca Battaglia, Francesca Gladiali, Massimo Grossi. Asymptotic behavior of minimal solutions of $-\Delta u = \lambda f(u)$ as $\lambda\to-\infty$. Discrete & Continuous Dynamical Systems - A, 2021, 41 (2) : 681-700. doi: 10.3934/dcds.2020293  Wenbin Li, Jianliang Qian. Simultaneously recovering both domain and varying density in inverse gravimetry by efficient level-set methods. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020073  Awais Younus, Zoubia Dastgeer, Nudrat Ishaq, Abdul Ghaffar, Kottakkaran Sooppy Nisar, Devendra Kumar. On the observability of conformable linear time-invariant control systems. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020444  Touria Karite, Ali Boutoulout. Global and regional constrained controllability for distributed parabolic linear systems: RHUM approach. Numerical Algebra, Control & Optimization, 2020  doi: 10.3934/naco.2020055  Noufel Frikha, Valentin Konakov, Stéphane Menozzi. Well-posedness of some non-linear stable driven SDEs. Discrete & Continuous Dynamical Systems - A, 2021, 41 (2) : 849-898. doi: 10.3934/dcds.2020302  Alberto Bressan, Sondre Tesdal Galtung. A 2-dimensional shape optimization problem for tree branches. Networks & Heterogeneous Media, 2020  doi: 10.3934/nhm.2020031  Kihoon Seong. Low regularity a priori estimates for the fourth order cubic nonlinear Schrödinger equation. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5437-5473. doi: 10.3934/cpaa.2020247  Yongge Tian, Pengyang Xie. Simultaneous optimal predictions under two seemingly unrelated linear random-effects models. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020168  Maoding Zhen, Binlin Zhang, Vicenţiu D. Rădulescu. Normalized solutions for nonlinear coupled fractional systems: Low and high perturbations in the attractive case. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020379  Youming Guo, Tingting Li. Optimal control strategies for an online game addiction model with low and high risk exposure. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020347  Chao Wang, Qihuai Liu, Zhiguo Wang. Periodic bouncing solutions for Hill's type sub-linear oscillators with obstacles. Communications on Pure & Applied Analysis, 2021, 20 (1) : 281-300. doi: 10.3934/cpaa.2020266  Yi-Long Luo, Yangjun Ma. Low Mach number limit for the compressible inertial Qian-Sheng model of liquid crystals: Convergence for classical solutions. Discrete & Continuous Dynamical Systems - A, 2021, 41 (2) : 921-966. doi: 10.3934/dcds.2020304  Mathew Gluck. Classification of solutions to a system of $n^{\rm th}$ order equations on $\mathbb R^n$. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5413-5436. doi: 10.3934/cpaa.2020246

2019 Impact Factor: 0.734