February  2020, 14(1): 69-88. doi: 10.3934/amc.2020006

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

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

Received  August 2018 Revised  February 2019 Published  August 2019

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

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.

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

E. R. Berlekamp, Algebraic Coding Theory, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1968. Google Scholar

[2]

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

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

[4]

M. BlaumJ. S. PlankM. 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. Google Scholar

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

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

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

[8]

P. GopalanC. HuangB. 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. Google Scholar

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

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

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

[12]

A. Neri and A.-L. Horlemann-Trautmann, Random construction of partial MDS codes, preprint, arXiv: 1801.05848.Google Scholar

[13] R. M. Roth, Introduction to Coding Theory, Cambridge University Press, New York, NY, USA, 2006. Google Scholar
[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. Google Scholar

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

show all references

References:
[1]

E. R. Berlekamp, Algebraic Coding Theory, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1968. Google Scholar

[2]

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

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

[4]

M. BlaumJ. S. PlankM. 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. Google Scholar

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

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

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

[8]

P. GopalanC. HuangB. 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. Google Scholar

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

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

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

[12]

A. Neri and A.-L. Horlemann-Trautmann, Random construction of partial MDS codes, preprint, arXiv: 1801.05848.Google Scholar

[13] R. M. Roth, Introduction to Coding Theory, Cambridge University Press, New York, NY, USA, 2006. Google Scholar
[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. Google Scholar

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

[1]

Janne I. Kokkala, Patric R. J.  Östergård. Further results on the classification of MDS codes. Advances in Mathematics of Communications, 2016, 10 (3) : 489-498. doi: 10.3934/amc.2016020

[2]

Ilias S. Kotsireas, Christos Koukouvinos, Dimitris E. Simos. MDS and near-MDS self-dual codes over large prime fields. Advances in Mathematics of Communications, 2009, 3 (4) : 349-361. doi: 10.3934/amc.2009.3.349

[3]

Diego Napp, Roxana Smarandache. Constructing strongly-MDS convolutional codes with maximum distance profile. Advances in Mathematics of Communications, 2016, 10 (2) : 275-290. doi: 10.3934/amc.2016005

[4]

Kathryn Haymaker, Beth Malmskog, Gretchen L. Matthews. Locally recoverable codes with availability t≥2 from fiber products of curves. Advances in Mathematics of Communications, 2018, 12 (2) : 317-336. doi: 10.3934/amc.2018020

[5]

Carlos Munuera, Wanderson Tenório, Fernando Torres. Locally recoverable codes from algebraic curves with separated variables. Advances in Mathematics of Communications, 2019, 0 (0) : 0-0. doi: 10.3934/amc.2020019

[6]

Washiela Fish, Jennifer D. Key, Eric Mwambene. Partial permutation decoding for simplex codes. Advances in Mathematics of Communications, 2012, 6 (4) : 505-516. doi: 10.3934/amc.2012.6.505

[7]

Ettore Fornasini, Telma Pinho, Raquel Pinto, Paula Rocha. Composition codes. Advances in Mathematics of Communications, 2016, 10 (1) : 163-177. doi: 10.3934/amc.2016.10.163

[8]

Michael Braun. On lattices, binary codes, and network codes. Advances in Mathematics of Communications, 2011, 5 (2) : 225-232. doi: 10.3934/amc.2011.5.225

[9]

Alexis Eduardo Almendras Valdebenito, Andrea Luigi Tironi. On the dual codes of skew constacyclic codes. Advances in Mathematics of Communications, 2018, 12 (4) : 659-679. doi: 10.3934/amc.2018039

[10]

Olof Heden. The partial order of perfect codes associated to a perfect code. Advances in Mathematics of Communications, 2007, 1 (4) : 399-412. doi: 10.3934/amc.2007.1.399

[11]

Jop Briët, Assaf Naor, Oded Regev. Locally decodable codes and the failure of cotype for projective tensor products. Electronic Research Announcements, 2012, 19: 120-130. doi: 10.3934/era.2012.19.120

[12]

Gokhan Calis, O. Ozan Koyluoglu. Architecture-aware coding for distributed storage: Repairable block failure resilient codes. Advances in Mathematics of Communications, 2018, 12 (3) : 465-503. doi: 10.3934/amc.2018028

[13]

Joaquim Borges, Josep Rifà, Victor Zinoviev. Completely regular codes by concatenating Hamming codes. Advances in Mathematics of Communications, 2018, 12 (2) : 337-349. doi: 10.3934/amc.2018021

[14]

Carolyn Mayer, Kathryn Haymaker, Christine A. Kelley. Channel decomposition for multilevel codes over multilevel and partial erasure channels. Advances in Mathematics of Communications, 2018, 12 (1) : 151-168. doi: 10.3934/amc.2018010

[15]

Srimathy Srinivasan, Andrew Thangaraj. Codes on planar Tanner graphs. Advances in Mathematics of Communications, 2012, 6 (2) : 131-163. doi: 10.3934/amc.2012.6.131

[16]

M. B. Paterson, D. R. Stinson, R. Wei. Combinatorial batch codes. Advances in Mathematics of Communications, 2009, 3 (1) : 13-27. doi: 10.3934/amc.2009.3.13

[17]

Noam Presman, Simon Litsyn. Recursive descriptions of polar codes. Advances in Mathematics of Communications, 2017, 11 (1) : 1-65. doi: 10.3934/amc.2017001

[18]

Sergio Estrada, J. R. García-Rozas, Justo Peralta, E. Sánchez-García. Group convolutional codes. Advances in Mathematics of Communications, 2008, 2 (1) : 83-94. doi: 10.3934/amc.2008.2.83

[19]

Kwankyu Lee. Decoding of differential AG codes. Advances in Mathematics of Communications, 2016, 10 (2) : 307-319. doi: 10.3934/amc.2016007

[20]

Olof Heden. A survey of perfect codes. Advances in Mathematics of Communications, 2008, 2 (2) : 223-247. doi: 10.3934/amc.2008.2.223

2018 Impact Factor: 0.879

Article outline

[Back to Top]