# American Institute of Mathematical Sciences

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:
 [1] 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 [2] 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 [3] 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 [4] 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 [5] 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 [6] 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 [7] 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 [8] 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 [9] 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 [10] 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 [11] 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 [12] G. A. Gibson, Redundant Disk Arrays: Reliable, Parallel Secondary Storage, Cambridge, MA: MIT Press, 1992.   Google Scholar [13] K. Huber, Some comments on Zech's logarithms, IEEE Transactions on Information Theory, 36 (1990), 946-950.  doi: 10.1109/18.53764.  Google Scholar [14] A. Kotzig, Hamilton graphs and Hamilton circuits, Theory of Graphs and its Applications, Publ. House Czechoslovak Acad. Sci., Prague, (1964), 63–82.  Google Scholar [15] 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 [16] 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 [17] 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 [18] M. Sudan, Algorithmic Introduction to Coding Theory, 2002, https://people.csail.mit.edu/madhu/FT02/scribe/lect16.ps. Google Scholar [19] 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 [20] 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:
 [1] 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 [2] 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 [3] 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 [4] 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 [5] 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 [6] 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 [7] 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 [8] 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 [9] 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 [10] 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 [11] 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 [12] G. A. Gibson, Redundant Disk Arrays: Reliable, Parallel Secondary Storage, Cambridge, MA: MIT Press, 1992.   Google Scholar [13] K. Huber, Some comments on Zech's logarithms, IEEE Transactions on Information Theory, 36 (1990), 946-950.  doi: 10.1109/18.53764.  Google Scholar [14] A. Kotzig, Hamilton graphs and Hamilton circuits, Theory of Graphs and its Applications, Publ. House Czechoslovak Acad. Sci., Prague, (1964), 63–82.  Google Scholar [15] 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 [16] 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 [17] 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 [18] M. Sudan, Algorithmic Introduction to Coding Theory, 2002, https://people.csail.mit.edu/madhu/FT02/scribe/lect16.ps. Google Scholar [19] 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 [20] 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 ×
 [1] 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 [2] 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 [3] Hai Q. Dinh, Bac T. Nguyen, Paravee Maneejuk. Constacyclic codes of length $8p^s$ over $\mathbb F_{p^m} + u\mathbb F_{p^m}$. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020123 [4] Yuan Cao, Yonglin Cao, Hai Q. Dinh, Ramakrishna Bandi, Fang-Wei Fu. An explicit representation and enumeration for negacyclic codes of length $2^kn$ over $\mathbb{Z}_4+u\mathbb{Z}_4$. Advances in Mathematics of Communications, 2021, 15 (2) : 291-309. doi: 10.3934/amc.2020067 [5] 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 [6] 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, 2021, 15 (1) : 159-183. doi: 10.3934/ipi.2020076 [7] Vito Napolitano, Ferdinando Zullo. Codes with few weights arising from linear sets. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020129 [8] Dandan Wang, Xiwang Cao, Gaojun Luo. A class of linear codes and their complete weight enumerators. Advances in Mathematics of Communications, 2021, 15 (1) : 73-97. doi: 10.3934/amc.2020044 [9] Huyuan Chen, Dong Ye, Feng Zhou. On gaussian curvature equation in $\mathbb{R}^2$ with prescribed nonpositive curvature. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3201-3214. doi: 10.3934/dcds.2020125 [10] Guoyuan Chen, Yong Liu, Juncheng Wei. Nondegeneracy of harmonic maps from ${{\mathbb{R}}^{2}}$ to ${{\mathbb{S}}^{2}}$. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3215-3233. doi: 10.3934/dcds.2019228 [11] Shudi Yang, Xiangli Kong, Xueying Shi. Complete weight enumerators of a class of linear codes over finite fields. Advances in Mathematics of Communications, 2021, 15 (1) : 99-112. doi: 10.3934/amc.2020045 [12] Jong Yoon Hyun, Boran Kim, Minwon Na. Construction of minimal linear codes from multi-variable functions. Advances in Mathematics of Communications, 2021, 15 (2) : 227-240. doi: 10.3934/amc.2020055 [13] 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 [14] Yueh-Cheng Kuo, Huan-Chang Cheng, Jhih-You Syu, Shih-Feng Shieh. On the nearest stable $2\times 2$ matrix, dedicated to Prof. Sze-Bi Hsu in appreciation of his inspiring ideas. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020358 [15] Ivan Bailera, Joaquim Borges, Josep Rifà. On Hadamard full propelinear codes with associated group $C_{2t}\times C_2$. Advances in Mathematics of Communications, 2021, 15 (1) : 35-54. doi: 10.3934/amc.2020041 [16] Hongming Ru, Chunming Tang, Yanfeng Qi, Yuxiao Deng. A construction of $p$-ary linear codes with two or three weights. Advances in Mathematics of Communications, 2021, 15 (1) : 9-22. doi: 10.3934/amc.2020039 [17] 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 [18] 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 [19] 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 [20] Mingchao Zhao, You-Wei Wen, Michael Ng, Hongwei Li. A nonlocal low rank model for poisson noise removal. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2021003

2019 Impact Factor: 0.734