Article Contents

2020, Volume 14, Issue 1: 69-88. Doi: 10.3934/amc.2020006

This issue Previous Article Skew constacyclic codes over the local Frobenius non-chain rings of order 16 Next Article New doubly even self-dual codes having minimum weight 20

A complete classification of partial MDS (maximally recoverable) codes with one global parity

Anna-Lena Horlemann-Trautmann^1, and
Alessandro Neri^2, ,

1.
Faculty of Mathematics and Statistics, University of St. Gallen, Dufourstrasse 50, 9000 St. Gallen, Switzerland
2.
Institute of Mathematics, University of Zurich, Winterthurerstrasse 190, 8057 Zurich, Switzerland

^* Corresponding author: Alessandro Neri
^* Corresponding author: Alessandro Neri

Received: August 2018

Revised: February 2019

Published: August 2019

The second author is supported by Swiss National Science Foundation grant no. 169510

Abstract / Introduction Full Text(HTML) Related Papers Cited by

Abstract

We generalize the definition of partial MDS codes to locality blocks of various length and show that these codes are maximally recoverable. Then we focus on partial MDS codes with exactly one global parity. We derive a general construction for such codes by describing a suitable parity check matrix. Then we give a construction of generator matrices of such codes. Afterwards we show that all partial MDS codes with one global parity have a generator matrix (or parity check matrix) of this form. This gives a complete classification and hence also a sufficient and necessary condition on the underlying field size for the existence of such codes. This condition is related to the classical MDS conjecture. Moreover, we investigate the decoding of such codes and give some comments on partial MDS codes with more than one global parity.

Keywords:

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

Citation:

Full Text(HTML)

Related Papers

Cited by

References

[1]	E. R. Berlekamp, Algebraic Coding Theory, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1968.
[2]	M. Blaum, J. L. Hafner and S. Hetzler, Partial-MDS codes and their application to RAID type of architectures, IEEE Transactions on Information Theory, 59 (2013), 4510-4519. doi: 10.1109/TIT.2013.2252395.
[3]	M. Blaum, J. S. Plank, M. Schwartz and E. Yaakobi, Partial MDS (PMDS) and sector-disk (SD) codes that tolerate the erasure of two random sectors, in IEEE International Symposium on Information Theory, (2014), 1792-1796. doi: 10.1109/ISIT.2014.6875142.
[4]	M. Blaum, J. S. Plank, M. Schwartz and E. Yaakobi, Construction of partial MDS and sector-disk codes with two global parity symbols, IEEE Transactions on Information Theory, 62 (2016), 2673-2681. doi: 10.1109/TIT.2016.2536720.
[5]	G. Calis and O. O. Koyluoglu, A general construction for PMDS codes, IEEE Communications Letters, 21 (2017), 452-455. doi: 10.1109/LCOMM.2016.2627569.
[6]	J. Chen, K. W. Shum, Q. Yu and C. W. Sung, Sector-disk codes and partial MDS codes with up to three global parities, in IEEE International Symposium on Information Theory, (2015), 1876-1880. doi: 10.1109/ISIT.2015.7282781.
[7]	M. H. Chen, C. Huang and J. Li, On the maximally recoverable property for multi-protection group codes, in 2007 IEEE International Symposium on Information Theory, (2007), 486-490. doi: 10.1109/ISIT.2007.4557272.
[8]	P. Gopalan, C. Huang, B. Jenkins and S. Yekhanin, Explicit maximally recoverable codes with locality, IEEE Transactions on Information Theory, 60 (2014), 5245-5256. doi: 10.1109/TIT.2014.2332338.
[9]	S.-J. Lin, W.-H. Chung and Y. S. Han, Novel polynomial basis and its application to Reed-Solomon erasure codes, in IEEE 55th Annual Symposium on Foundations of Computer Science, (2014), 316-325. doi: 10.1109/FOCS.2014.41.
[10]	F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, North-Holland Mathematical Library, Vol. 16. North-Holland Publishing Co., Amsterdam-New York-Oxford, 1977.
[11]	J. L. Massey, Shift-register synthesis and BCH decoding, IEEE Transactions on Information Theory, 15 (1969), 122-127. doi: 10.1109/tit.1969.1054260.
[12]	A. Neri and A.-L. Horlemann-Trautmann, Random construction of partial MDS codes, preprint, arXiv: 1801.05848.
[13]	R. M. Roth, Introduction to Coding Theory, Cambridge University Press, New York, NY, USA, 2006.
[14]	R. M. Roth and G. Seroussi, On generator matrices of MDS codes (corresp.), IEEE Transactions on Information Theory, 31 (1985), 826-830. doi: 10.1109/TIT.1985.1057113.
[15]	B. Segre, Curve razionali normali e k-archi negli spazi finiti, Annali di Matematica Pura ed Applicata, 39 (1955), 357-379. doi: 10.1007/BF02410779.