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

M. BarbierC. 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.

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

[3]

M. BlaumJ. BradyJ. 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.

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

[5]

M. BlaumJ. 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.

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

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

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

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

[10]

S. D. CardellJ.-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.

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

[12] G. A. Gibson, Redundant Disk Arrays: Reliable, Parallel Secondary Storage, Cambridge, MA: MIT Press, 1992. 
[13]

K. Huber, Some comments on Zech's logarithms, IEEE Transactions on Information Theory, 36 (1990), 946-950.  doi: 10.1109/18.53764.

[14]

A. Kotzig, Hamilton graphs and Hamilton circuits, Theory of Graphs and its Applications, Publ. House Czechoslovak Acad. Sci., Prague, (1964), 63–82.

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

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

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

[18]

M. Sudan, Algorithmic Introduction to Coding Theory, 2002, https://people.csail.mit.edu/madhu/FT02/scribe/lect16.ps.

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

[20]

G. V. ZaitzevV. 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. 

show all references

References:
[1]

M. BarbierC. 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.

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

[3]

M. BlaumJ. BradyJ. 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.

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

[5]

M. BlaumJ. 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.

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

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

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

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

[10]

S. D. CardellJ.-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.

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

[12] G. A. Gibson, Redundant Disk Arrays: Reliable, Parallel Secondary Storage, Cambridge, MA: MIT Press, 1992. 
[13]

K. Huber, Some comments on Zech's logarithms, IEEE Transactions on Information Theory, 36 (1990), 946-950.  doi: 10.1109/18.53764.

[14]

A. Kotzig, Hamilton graphs and Hamilton circuits, Theory of Graphs and its Applications, Publ. House Czechoslovak Acad. Sci., Prague, (1964), 63–82.

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

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

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

[18]

M. Sudan, Algorithmic Introduction to Coding Theory, 2002, https://people.csail.mit.edu/madhu/FT02/scribe/lect16.ps.

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

[20]

G. V. ZaitzevV. 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. 

Table 1.  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 $
Table 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 $
Table 3.  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 $
Table 4.  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 $
Table 5.  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]

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

[2]

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

[3]

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

[4]

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

[5]

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

[6]

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

[7]

Adrian Korban, Serap Sahinkaya, Deniz Ustun. New type I binary $[72, 36, 12]$ self-dual codes from $M_6(\mathbb{F}_2)G$ - Group matrix rings by a hybrid search technique based on a neighbourhood-virus optimisation algorithm. Advances in Mathematics of Communications, 2022  doi: 10.3934/amc.2022032

[8]

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

[9]

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

[10]

Roghayeh Mohammadi Hesari, Mahboubeh Hosseinabadi, Rashid Rezaei, Karim Samei. $\mathbb{F}_{p^{m}}\mathbb{F}_{p^{m}}{[u^2]}$-additive skew cyclic codes of length $2p^s $. Advances in Mathematics of Communications, 2022  doi: 10.3934/amc.2022023

[11]

Taher Abualrub, Steven T. Dougherty. Additive and linear conjucyclic codes over $ {\mathbb{F}}_4 $. Advances in Mathematics of Communications, 2022, 16 (1) : 1-15. doi: 10.3934/amc.2020096

[12]

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

[13]

Yuan Cao, Yonglin Cao, Hai Q. Dinh, Fanghui Ma. Representation and matrix-product structure of Type-1 constacyclic codes over $ \mathbb{F}_{p^m}[u]/\langle u^e\rangle $. Advances in Mathematics of Communications, 2022  doi: 10.3934/amc.2022060

[14]

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

[15]

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

[16]

Wei Qi. On the polycyclic codes over $ \mathbb{F}_q+u\mathbb{F}_q $. Advances in Mathematics of Communications, 2022  doi: 10.3934/amc.2022015

[17]

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

[18]

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

[19]

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

[20]

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

2021 Impact Factor: 1.015

Metrics

  • PDF downloads (3115)
  • HTML views (453)
  • Cited by (0)

[Back to Top]