Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Optimal ternary locally repairable codes

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

Abstract

Locally repairable codes (LRCs) are linear codes with locality properties for code symbols, which have important applications in distributed storage systems. In this paper, we completely classify all the possible code parameters of optimal ternary LRCs achieving the Singleton-like bound proposed by Gopalan et al. Explicit constructions of optimal ternary LRCs are given for each group of possible code parameters. Moreover, it is also proved that optimal ternary LRCs with maximal minimum distance 6 are unique up to the equivalence of linear 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
$34.99 /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 excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Bosma W., Cannon J., Playoust C.: The Magma algebra system. I: the user language. J. Symb. Comput. 24(3–4), 235–265 (1997).

    Article  MathSciNet  Google Scholar 

  2. Cai H., Miao Y., Schwartz M., Tang X.: On optimal locally repairable codes with super-linear length. IEEE Trans. Inf. Theory 66(8), 4853–4868 (2020).

    Article  MathSciNet  Google Scholar 

  3. Chen B., Fang W., Xia S.-T., Hao J., Fu F.-W.: Improved bounds and Singleton-optimal constructions of locally repairable codes with minimum distance 5 and 6. IEEE Trans. Inf. Theory 67(1), 217–231 (2021).

    Article  MathSciNet  Google Scholar 

  4. Chen B., Xia S.-T., Hao J., Fu F.-W.: Constructions of optimal cyclic \((r,\delta )\) locally repairable codes. IEEE Trans. Inf. Theory 64(4), 2499–2511 (2018).

    Article  MathSciNet  Google Scholar 

  5. de Boer M.A.: Almost MDS codes. Des. Codes Cryptogr. 9(2), 143–155 (1996).

    Article  MathSciNet  Google Scholar 

  6. Dodunekov S.M.: A comment on the weight structure of generator matrices of linear codes. Probl. Inf. Transm. 26(2), 101–104 (1990).

    MathSciNet  Google Scholar 

  7. Dodunekov S., Landgev I.: On near-MDS codes. J. Geom. 54(1), 30–43 (1995).

    Article  MathSciNet  Google Scholar 

  8. Dodunekov S., Landgev I.: Near-MDS codes over some small fields. Discret. Math. 213(1–3), 55–65 (2000).

    Article  MathSciNet  Google Scholar 

  9. Gopalan P., Huang C., Simitci H., Yekhanin S.: On the locality of codeword symbols. IEEE Trans. Inf. Theory 58(11), 6925–6934 (2012).

    Article  MathSciNet  Google Scholar 

  10. Guruswami V., Xing C., Yuan C.: How long can optimal locally repairable codes be? IEEE Trans. Inf. Theory 65(6), 3662–3670 (2019).

    Article  MathSciNet  Google Scholar 

  11. Hao J., Shum K.W., Xia S.-T., Fu F.-W., Yang Y.: On optimal quaternary locally repairable codes. In: The IEEE International Symposium on Information Theory (ISIT), Melbourne, VIC, Australia, pp. 3267–3272 (2021).

  12. Hao, J., Xia, S.-T., Chen, B.: On optimal ternary locally repairable codes. In: IEEE Int. Symp. Inf. Theory (ISIT), Aachen, Germany, pp. 171– 175 ( 2017)

  13. Hao J., Xia S.-T., Shum K.W., Chen B., Fu F.-W., Yang Y.: Bounds and constructions of locally repairable codes: parity-check matrix approach. IEEE Trans. Inf. Theory 66(12), 7465–7474 (2020).

    Article  MathSciNet  Google Scholar 

  14. Hao J., Zhang J., Xia S.-T., Fu F.-W., Yang Y.: Constructions and weight distributions of optimal locally repairable codes. IEEE Trans. Commun. 70(5), 2895–2908 (2022).

    Article  Google Scholar 

  15. Huang P., Yaakobi E., Uchikawa H., Siegel P.H.: Binary linear locally repairable codes. IEEE Trans. Inf. Theory 62(11), 6268–6283 (2016).

    Article  MathSciNet  Google Scholar 

  16. Jin L.: Explicit construction of optimal locally recoverable codes of distance 5 and 6 via binary constant weight codes. IEEE Trans. Inf. Theory 65(8), 4658–4663 (2019).

    Article  MathSciNet  Google Scholar 

  17. Jin L., Ma L., Xing C.: Construction of optimal locally repairable codes via automorphism groups of rational function fields. IEEE Trans. Inf. Theory 66(1), 210–221 (2019).

    Article  MathSciNet  Google Scholar 

  18. Li X., Ma L., Xing C.: Optimal locally repairable codes via elliptic curves. IEEE Trans. Inf. Theory 65(1), 108–117 (2019).

    Article  MathSciNet  Google Scholar 

  19. Luo G., Cao X.: Optimal cyclic codes with hierarchical locality. IEEE Trans. Commun. 68(6), 3302–3310 (2020).

    Article  Google Scholar 

  20. Luo G., Ezerman M.F., Ling S.: Three new infinite families of optimal locally repairable codes from matrix-product codes. IEEE Trans. Inf. Theory 69(1), 75–85 (2023).

    Article  Google Scholar 

  21. Luo G., Ling S.: Application of optimal p-ary linear codes to alphabet-optimal locally repairable codes. Des. Codes Cryptogr. 90(5), 1271–1287 (2022).

    Article  MathSciNet  Google Scholar 

  22. Luo Y., Xing C., Yuan C.: Optimal locally repairable codes of distance 3 and 4 via cyclic codes. IEEE Trans. Inf. Theory 65(2), 1048–1053 (2019).

    Article  MathSciNet  Google Scholar 

  23. MacWilliams F.J., Sloane N.J.A.: The Theory of Error-Correcting Codes. North-Holland, Amsterdam (1977).

    Google Scholar 

  24. Papailiopoulos D.S., Dimakis A.G.: Locally repairable codes. IEEE Trans. Inf. Theory 60(10), 5843–5855 (2014).

    Article  MathSciNet  Google Scholar 

  25. Pless V.: On the uniqueness of the Golay codes. J. Combin. Theory 5(3), 215–228 (1968).

    Article  MathSciNet  Google Scholar 

  26. Pless V.: More on the uniqueness of the Golay codes. Discret. Math. 106(1), 391–398 (1992).

    Article  MathSciNet  Google Scholar 

  27. Rawat A.S., Papailiopoulos D.S., Dimakis A.G., Vishwanath S.: Locality and availability in distributed storage. IEEE Trans. Inf. Theory 62(8), 4481–4493 (2016).

    Article  MathSciNet  Google Scholar 

  28. Silberstein N., Zeh A.: Anticode-based locally repairable codes with high availability. Des. Codes Cryptogr. 86(2), 419–445 (2018).

    Article  MathSciNet  Google Scholar 

  29. Tamo I., Barg A.: A family of optimal locally recoverable codes. IEEE Trans. Inf. Theory 60(8), 4661–4676 (2014).

    Article  MathSciNet  Google Scholar 

  30. Tamo I., Barg A., Goparaju S., Calderbank R.: Cyclic LRC codes, binary LRC codes, and upper bounds on the distance of cyclic codes. Int. J. Inf. Coding Theory 3(4), 345–364 (2016).

    MathSciNet  Google Scholar 

  31. Wang A., Zhang Z.: Repair locality with multiple erasure tolerance. IEEE Trans. Inf. Theory 60(11), 6979–6987 (2014).

    Article  MathSciNet  Google Scholar 

  32. Wang A., Zhang Z.: An integer programming-based bound for locally repairable codes. IEEE Trans. Inf. Theory 61(10), 5280–5294 (2015).

    Article  MathSciNet  Google Scholar 

Download references

Acknowledgements

The authors would like to express their sincere gratefulness to the Associate Editor and the anonymous reviewers for the valuable suggestions and comments which helped to greatly improve this article. This research is supported in part by the National Key Research and Development Program of China under Grants 2020YFB1805400 and 2022YFA1005000, the National Natural Science Foundation of China under Grants 62171248, 62171400, 62301189, 62371259, 12141108 and 61801049, Shenzhen Science and Technology Program under Grant JCYJ20220818101012025, the PCNL KEY project under Grant PCL2023AS6-1, the Nankai Zhide Foundation, and the Beijing University of Posts and Telecommunications Youth Science and Technology Innovation Talent Support Program.

Author information

Authors and Affiliations

  1. National Engineering Research Center of Disaster Backup and Recovery, Beijing University of Posts and Telecommunications, Beijing, 100876, China

    Jie Hao & Yixian Yang

  2. Tsinghua Shenzhen International Graduate School, Tsinghua University, Shenzhen, 518055, China

    Shu-Tao Xia

  3. School of Science and Engineering, The Chinese University of Hong Kong (Shenzhen), Shenzhen, 518172, China

    Kenneth W. Shum

  4. Department of Computer Science and Technology, Harbin Institute of Technology, Shenzhen, Shenzhen, 518055, China

    Bin Chen

  5. Chern Institute of Mathematics and LPMC, Nankai University, Tianjin, 300071, China

    Fang-Wei Fu

  6. Research Center of Artificial Intelligence, Peng Cheng Laboratory, Shenzhen, 518055, China

    Shu-Tao Xia

Authors
  1. Jie Hao
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Shu-Tao Xia
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Kenneth W. Shum
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Bin Chen
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Fang-Wei Fu
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. Yixian Yang
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Jie Hao.

Additional information

Communicated by T. Etzion.

Publisher's Note

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

This work was presented in part at the IEEE International Symposium on Information Theory (ISIT) 2017 [12].

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Hao, J., Xia, ST., Shum, K.W. et al. Optimal ternary locally repairable codes. Des. Codes Cryptogr. 92, 2685–2704 (2024). https://doi.org/10.1007/s10623-024-01409-7

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10623-024-01409-7

Keywords

Mathematics Subject Classification

Search

Navigation