    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  August 2020 Early access  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 ×
  Emily McMillon, Allison Beemer, Christine A. Kelley. Extremal absorbing sets in low-density parity-check codes. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021003  W. Cary Huffman. On the theory of $\mathbb{F}_q$-linear $\mathbb{F}_{q^t}$-codes. Advances in Mathematics of Communications, 2013, 7 (3) : 349-378. doi: 10.3934/amc.2013.7.349  Thomas Westerbäck. Parity check systems of nonlinear codes over finite commutative Frobenius rings. Advances in Mathematics of Communications, 2017, 11 (3) : 409-427. doi: 10.3934/amc.2017035  Anna-Lena Horlemann-Trautmann, Alessandro Neri. A complete classification of partial MDS (maximally recoverable) codes with one global parity. Advances in Mathematics of Communications, 2020, 14 (1) : 69-88. doi: 10.3934/amc.2020006  W. Cary Huffman. Self-dual $\mathbb{F}_q$-linear $\mathbb{F}_{q^t}$-codes with an automorphism of prime order. Advances in Mathematics of Communications, 2013, 7 (1) : 57-90. doi: 10.3934/amc.2013.7.57  Yun Gao, Shilin Yang, Fang-Wei Fu. Some optimal cyclic $\mathbb{F}_q$-linear $\mathbb{F}_{q^t}$-codes. Advances in Mathematics of Communications, 2021, 15 (3) : 387-396. doi: 10.3934/amc.2020072  Karim Samei, Arezoo Soufi. Quadratic residue codes over $\mathbb{F}_{p^r}+{u_1}\mathbb{F}_{p^r}+{u_2}\mathbb{F}_{p^r}+...+{u_t}\mathbb{F}_ {p^r}$. Advances in Mathematics of Communications, 2017, 11 (4) : 791-804. doi: 10.3934/amc.2017058  Delphine Boucher. Construction and number of self-dual skew codes over $\mathbb{F}_{p^2}$. Advances in Mathematics of Communications, 2016, 10 (4) : 765-795. doi: 10.3934/amc.2016040  Taher Abualrub, Steven T. Dougherty. Additive and linear conjucyclic codes over ${\mathbb{F}}_4$. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020096  Fengwei Li, Qin Yue, Xiaoming Sun. The values of two classes of Gaussian periods in index 2 case and weight distributions of linear codes. Advances in Mathematics of Communications, 2021, 15 (1) : 131-153. doi: 10.3934/amc.2020049  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  Fatmanur Gursoy, Irfan Siap, Bahattin Yildiz. Construction of skew cyclic codes over $\mathbb F_q+v\mathbb F_q$. Advances in Mathematics of Communications, 2014, 8 (3) : 313-322. doi: 10.3934/amc.2014.8.313  Minjia Shi, Yaqi Lu. Cyclic DNA codes over $\mathbb{F}_2[u,v]/\langle u^3, v^2-v, vu-uv\rangle$. Advances in Mathematics of Communications, 2019, 13 (1) : 157-164. doi: 10.3934/amc.2019009  Evangeline P. Bautista, Philippe Gaborit, Jon-Lark Kim, Judy L. Walker. s-extremal additive $\mathbb F_4$ codes. Advances in Mathematics of Communications, 2007, 1 (1) : 111-130. doi: 10.3934/amc.2007.1.111  Olof Heden, Faina I. Solov’eva. Partitions of $\mathbb F$n into non-parallel Hamming codes. Advances in Mathematics of Communications, 2009, 3 (4) : 385-397. doi: 10.3934/amc.2009.3.385  W. Cary Huffman. Additive cyclic codes over $\mathbb F_4$. Advances in Mathematics of Communications, 2008, 2 (3) : 309-343. doi: 10.3934/amc.2008.2.309  W. Cary Huffman. Additive cyclic codes over $\mathbb F_4$. Advances in Mathematics of Communications, 2007, 1 (4) : 427-459. doi: 10.3934/amc.2007.1.427  Fanghui Ma, Jian Gao, Fang-Wei Fu. New non-binary quantum codes from constacyclic codes over $\mathbb{F}_q[u,v]/\langle u^{2}-1, v^{2}-v, uv-vu\rangle$. Advances in Mathematics of Communications, 2019, 13 (3) : 421-434. doi: 10.3934/amc.2019027  Fernando Hernando, Diego Ruano. New linear codes from matrix-product codes with polynomial units. Advances in Mathematics of Communications, 2010, 4 (3) : 363-367. doi: 10.3934/amc.2010.4.363  Hongwei Liu, Jingge Liu. On $\sigma$-self-orthogonal constacyclic codes over $\mathbb F_{p^m}+u\mathbb F_{p^m}$. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020127

2020 Impact Factor: 0.935