Advanced Search
Article Contents
Article Contents

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

  • * Corresponding author: Alessandro Neri

    * Corresponding author: Alessandro Neri

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

Abstract / Introduction Full Text(HTML) Related Papers Cited by
  • 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.

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


    \begin{equation} \\ \end{equation}
  • 加载中
  • [1] E. R. Berlekamp, Algebraic Coding Theory, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1968.
    [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.
    [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. 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.
    [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. 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.
    [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. RothIntroduction 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.
  • 加载中

Article Metrics

HTML views(1751) PDF downloads(445) Cited by(0)

Access History

Other Articles By Authors



    DownLoad:  Full-Size Img  PowerPoint