Journal of Shanghai Jiao Tong University

Journal of Shanghai Jiaotong University >

2024 , Vol. 58 >Issue 10: 1596 - 1605

DOI: https://doi.org/10.16183/j.cnki.jsjtu.2023.151

Original article

Construction of Optimal Locally Repairable Codes of Triangular Association Schemes

  • WANG Jing ,
  • LI Jinghui ,
  • YANG Jiarong ,
  • WANG E
Expand
  • School of Information Engineering, Chang’an University, Xi’an 710018, China

Received date: 2023-04-21

  Revised date: 2023-09-22

  Accepted date: 2023-09-25

  Online published: 2023-10-09

Fold

Abstract

As a new erasure code for distributed storage systems, locally repairable codes (LRCs) can effectively realize the reliable and efficient storage of massive data. The construction of locally repairable codes with (r,t) locality has become a research hotspot recently. Therefore, the construction methods of locally repairable codes based on triangular association schemes are proposed, which can construct optimal binary locally repairable codes with arbitrary (r,t) locality. Performance analyses show that the LRCs constructed with availability t=2 reach the optimal code rate bound, the LRCs constructed with arbitrary locality r>2 and availability t>2 reach the optimal minimum distance bound. The LRC constructed in this paper performs better in terms of code rate and more flexible parameter selection than those constructed based on near-regular graphs and direct product codes, etc.

Key words： distributed storage system; locally repairable code (LRC); triangular association schemes; minimum distance

Cite this article

WANG Jing , LI Jinghui , YANG Jiarong , WANG E . Construction of Optimal Locally Repairable Codes of Triangular Association Schemes[J]. Journal of Shanghai Jiaotong University, 2024 , 58(10) : 1596 -1605 . DOI: 10.16183/j.cnki.jsjtu.2023.151

References

[1] FANG W J, CHEN B, XIA S T, et al. Singleton-optimal LRCs and perfect LRCs via cyclic codes[C]// 2021 IEEE International Symposium on Information Theory. Melbourne, Australia: IEEE, 2021: 3261-3266.
[2] YAVARI E, ESMAEILI M. Locally repairable codes: Joint sequential-parallel repair for multiple node failures[J]. IEEE Transactions on Information Theory, 2020, 66(1): 222-232.
[3] PAPAILIOPOULOS D S, DIMAKIS A G. Locally repairable codes[J]. IEEE Transactions on Information Theory, 2014, 60(10): 5843-5855.
[4] WANG A Y, ZHANG Z F, LIN D D. Bounds for binary linear locally repairable codes via a sphere-packing approach[J]. IEEE Transactions on Information Theory, 2019, 65(7): 4167-4179.
[5] GOPALAN P, HUANG C, SIMITCI H, et al. On the locality of codeword symbols[J]. IEEE Transactions on Information Theory, 2012, 58(11): 6925-6934.
[6] LUO Y, XING C P, YUAN C. Optimal locally repairable codes of distance 3 and 4 via cyclic codes[J]. IEEE Transactions on Information Theory, 2019, 65(2): 1048-1053.
[7] JIN L F. Explicit construction of optimal locally recoverable codes of distance 5 and 6 via binary constant weight codes[J]. IEEE Transactions on Information Theory, 2019, 65(8): 4658-4663.
[8] HAO J, XIA S T, SHUM K W, et al. Bounds and constructions of locally repairable codes: Parity-check matrix approach[J]. IEEE Transactions on Information Theory, 2020, 66(12): 7465-7474.
[9] FU Q, GUO L B, LI R H, et al. On the locality of some optimal ternary codes with dimension 6[C]// 2020 13th International Symposium on Computational Intelligence and Design. Hangzhou, China: IEEE, 2020: 155-158.
[10] CAI H, CHENG M Q, FAN C L, et al. Optimal locally repairable systematic codes based on packings[J]. IEEE Transactions on Communications, 2019, 67(1): 39-49.
[11] RAWAT A S, PAPAILIOPOULOS D S, DIMAKIS A G, et al. Locality and availability in distributed storage[J]. IEEE Transactions on Information Theory, 2016, 62(8): 4481-4493.
[12] TAMO I, BARG A. Bounds on locally recoverable codes with multiple recovering sets[C]// 2014 IEEE International Symposium on Information Theory. Honolulu, USA: IEEE, 2014: 691-695.
[13] WANG A Y, ZHANG Z F, LIN D D. Two classes of (r, t)-locally repairable codes[C]// 2016 IEEE International Symposium on Information Theory. Barcelona, Spain:IEEE, 2016: 445-449.
[14] HAO J, XIA S T, CHEN B. On the single-parity locally repairable codes with availability[C]// 2016 IEEE/CIC International Conference on Communications in China. Chengdu, China: IEEE, 2016: 1-4.
[15] BALAJI S B, KUMAR P V. Bounds on the rate and minimum distance of codes with availability[C]// 2017 IEEE International Symposium on Information Theory. Aachen, Germany: IEEE, 2017: 3155-3159.
[16] KIM J H, SONG H Y. Hypergraph-based binary locally repairable codes with availability[J]. IEEE Communications Letters, 2017, 21(11): 2332-2335.
[17] TAN P, ZHOU Z C, SIDORENKO V, et al. Two classes of optimal LRCs with information (r, t)-locality[J]. Designs, Codes and Cryptography, 2020, 88(9): 1741-1757.
[18] PRAKASH N, LALITHA V, BALAJI S B, et al. Codes with locality for two erasures[J]. IEEE Transactions on Information Theory, 2019, 65(12): 7771-7789.
[19] BALAJI S B, PRASANTH K P, KUMAR P V. Binary codes with locality for multiple erasures having short block length[C]// 2016 IEEE International Symposium on Information Theory. Barcelona, Spain:IEEE, 2016: 655-659.
[20] BAILEY R. Association schemes: Designed experiments, algebra, and combinatorics[M]. Cambridge: Cambridge University Press, 2004.
[21] WANG J, SHEN K Q, LIU X Y, et al. Construction of binary locally repairable codes with optimal distance and code rate[J]. IEEE Communications Letters, 2021, 25(7): 2109-2113.
[22] WANG A Y, ZHANG Z F, LIU M L. Achieving arbitrary locality and availability in binary codes[C]// 2015 IEEE International Symposium on Information Theory. Hong Kong, China: IEEE, 2015: 1866-1870.
Options
Outlines

/

〈 〉