上海交通大学学报

上海交通大学学报 >

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

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

电子信息与电气工程

三角形结合方案的最优局部修复码构造

  • 王静 ,
  • 李静辉 ,
  • 杨佳蓉 ,
  • 王娥
展开
  • 长安大学 信息工程学院,西安 710018
王 静(1982—),博士,教授,从事网络编码及分布式存储编码等方面的研究; E-mail:jingwang@chd.edu.cn.

收稿日期: 2023-04-21

  修回日期: 2023-09-22

  录用日期: 2023-09-25

  网络出版日期: 2023-10-09

基金资助

国家自然科学基金(62001059);陕西省自然科学基金资助项目(2022JM-056);长安大学大学生创新创业训练计划项目(S202310710121)

收起

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

摘要

局部修复码(LRCs)为用于分布式存储系统中的新型纠删码,能够有效实现海量数据的可靠高效存储,构造具有(r, t)局部性的LRCs已成为当前研究热点.为此,提出基于三角形结合方案的LRCs构造方法,可构造具有任意(r, t)局部性的二元最优LRCs.性能分析结果表明,构造的可用性t=2的LRCs达到了最优码率界,构造的具有任意局部性r>2和可用性t>2的LRCs达到了最优最小距离界.与基于近正则图及基于直积码等构造方法相比,本文构造出的LRCs在码率上表现更优且参数选择更灵活.

关键词： 分布式存储系统; 局部修复码; 三角形结合方案; 最小距离

本文引用格式

王静 , 李静辉 , 杨佳蓉 , 王娥 . 三角形结合方案的最优局部修复码构造[J]. 上海交通大学学报, 2024 , 58(10) : 1596 -1605 . DOI: 10.16183/j.cnki.jsjtu.2023.151

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

参考文献

[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
文章导航

/

〈 〉