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

Sara D. Cardell; Joan-Josep Climent; Daniel Panario; Brett Stevens

doi:10.3934/amc.2020047

Article Contents

2020, Volume 14, Issue 3: 437-453. Doi: 10.3934/amc.2020047

This issue Previous Article On the non-Abelian group code capacity of memoryless channels Next Article On polycyclic codes over a finite chain ring

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: October 31, 2018

Revised: May 31, 2019

Early access: November 2019

Published: August 2020

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

Abstract Full Text(HTML) Figure(0) / Table(5) Related Papers Cited by

Abstract

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.

Keywords:

Mathematics Subject Classification: Primary: 94B05, 94B15; Secondary: 94B60.

Citation:

Full Text(HTML)

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 $

| Show Table

DownLoad: CSV

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 $

| Show Table

DownLoad: CSV

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 $

| Show Table

DownLoad: CSV

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 $

| Show Table

DownLoad: CSV

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									×

| Show Table

DownLoad: CSV

Related Papers

Cited by

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