Random construction of partial MDS codes | Designs, Codes and Cryptography Skip to main content
Springer Nature Link
Log in

Random construction of partial MDS codes

  • Published:
Designs, Codes and Cryptography Aims and scope Submit manuscript

Abstract

This work deals with partial MDS (PMDS) codes, a special class of locally repairable codes, used for distributed storage systems. We first show that a known construction of these codes, using Gabidulin codes, can be extended to use any maximum rank distance code. Then we define a standard form for the generator matrices of PMDS codes and use this form to give an algebraic description of PMDS generator matrices. This implies that over a sufficiently large finite field a randomly chosen generator matrix in PMDS standard form generates a PMDS code with high probability. This also provides sufficient conditions on the field size for the existence of PMDS codes.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Blaum M., Hafner J.L., Hetzler S.: Partial-MDS codes and their application to RAID type of architectures. IEEE Trans. Inform. Theory 59(7), 4510–4519 (2013). https://doi.org/10.1109/TIT.2013.2252395.

    Article  MathSciNet  MATH  Google Scholar 

  2. Blaum M., Plank J.S., Schwartz M., Yaakobi E.: Partial MDS (PMDS) and sector-disk (SD) codes that tolerate the erasure of two random sectors. In: 2014 IEEE International Symposium on Information Theory, pp. 1792–1796 (2014). https://doi.org/10.1109/ISIT.2014.6875142.

  3. Blaum M., Plank J.S., Schwartz M., Yaakobi E.: Construction of partial MDS and sector-disk codes with two global parity symbols. IEEE Trans. Inform. Theory 62(5), 2673–2681 (2016). https://doi.org/10.1109/TIT.2016.2536720.

    Article  MathSciNet  MATH  Google Scholar 

  4. Calis G., Koyluoglu O.O.: A general construction for PMDS codes. IEEE Commun. Lett. 21(3), 452–455 (2017). https://doi.org/10.1109/LCOMM.2016.2627569.

    Article  Google Scholar 

  5. Chen J., Shum K.W., Yu Q., Sung C.W.: Sector-disk codes and partial MDS codes with up to three global parities. In: 2015 IEEE International Symposium on Information Theory (ISIT), pp. 1876–1880 (2015). https://doi.org/10.1109/ISIT.2015.7282781.

  6. Chen M., Huang C., Li J.: On the maximally recoverable property for multi-protection group codes. In: 2007 IEEE International Symposium on Information Theory (ISIT), pp. 486–490 (2007). https://doi.org/10.1109/ISIT.2007.4557272.

  7. Gabidulin E.M.: Theory of codes with maximum rank distance. Probl. Inf. Transm. 21(1), 3–16 (1985).

    MathSciNet  MATH  Google Scholar 

  8. Gopalan P., Huang C., Jenkins B., Yekhanin S.: Explicit maximally recoverable codes with locality. IEEE Trans. Inform. Theory 60(9), 5245–5256 (2014). https://doi.org/10.1109/TIT.2014.2332338.

    Article  MathSciNet  MATH  Google Scholar 

  9. Guruswami V., Jin L., Xing C.: Constructions of maximally recoverable local reconstruction codes via function fields. ArXiv E-prints. arXiv:1808.04539 (2018).

  10. Hartshorne R.: Algebraic Geometry, vol. 52. Springer, Berlin (2013).

    MATH  Google Scholar 

  11. Horlemann-Trautmann A.L., Marshall K.: New criteria for MRD and Gabidulin codes and some rank-metric code constructions. Adv. Math. Commun. 11(3), 533–548 (2017).

    Article  MathSciNet  Google Scholar 

  12. Horlemann-Trautmann A.L., Neri A.: A complete classification of partial-MDS (maximally recoverable) codes with one global parity. Adv. Math. Commun. 14(1), 69–88 (2020). https://doi.org/10.3934/amc.2020006.

    Article  MathSciNet  MATH  Google Scholar 

  13. Lewin D., Vadhan S.: Checking polynomial identities over any field: towards a derandomization? In: Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, pp. 438–447. ACM (1998).

  14. Neri A., Horlemann-Trautmann A.L., Randrianarisoa T., Rosenthal J.: On the genericity of maximum rank distance and Gabidulin codes. Des. Codes Cryptogr. 86(2), 341–363 (2018).

    Article  MathSciNet  Google Scholar 

  15. Roth R.: Maximum-rank array codes and their application to crisscross error correction. IEEE Trans. Inform. Theory 37(2), 328–336 (1991). https://doi.org/10.1109/18.75248.

    Article  MathSciNet  MATH  Google Scholar 

  16. Schwartz J.T.: Fast probabilistic algorithms for verification of polynomial identities. J. ACM 27(4), 701–717 (1980).

    Article  MathSciNet  Google Scholar 

  17. Sheekey J.: A new family of linear maximum rank distance codes. Adv. Math. Commun. 10(3), 475–488 (2016).

    Article  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Inria Saclay Île-de-France, Palaiseau, 91120, France

    Alessandro Neri

  2. Faculty of Mathematics and Statistics, University of St. Gallen, St. Gallen, Switzerland

    Anna-Lena Horlemann-Trautmann

Authors
  1. Alessandro Neri
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Anna-Lena Horlemann-Trautmann
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Anna-Lena Horlemann-Trautmann.

Additional information

Communicated by V. A. Zinoviev.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

A. Neri was partially supported by Swiss National Science Foundation Grants No. 169510 and 187711.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Neri, A., Horlemann-Trautmann, AL. Random construction of partial MDS codes. Des. Codes Cryptogr. 88, 711–725 (2020). https://doi.org/10.1007/s10623-019-00705-x

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10623-019-00705-x

Keywords

Search

Navigation