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

doi:10.16183/j.cnki.jsjtu.2023.151

上海交通大学学报 ›› 2024, Vol. 58 ›› Issue (10): 1596-1605.doi: 10.16183/j.cnki.jsjtu.2023.151

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

王静(), 李静辉, 杨佳蓉, 王娥

长安大学信息工程学院,西安 710018

收稿日期:2023-04-21 修回日期:2023-09-22 接受日期:2023-09-25 出版日期:2024-10-28 发布日期:2024-11-01
作者简介:王静(1982—),博士,教授,从事网络编码及分布式存储编码等方面的研究; E-mail:jingwang@chd.edu.cn.
基金资助:
国家自然科学基金(62001059);陕西省自然科学基金资助项目(2022JM-056);长安大学大学生创新创业训练计划项目(S202310710121)

Construction of Optimal Locally Repairable Codes of Triangular Association Schemes

WANG Jing(), LI Jinghui, YANG Jiarong, WANG E

School of Information Engineering, Chang’an University, Xi’an 710018, China

Received:2023-04-21 Revised:2023-09-22 Accepted:2023-09-25 Online:2024-10-28 Published:2024-11-01

摘要/Abstract

摘要：

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

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

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

中图分类号:

TN911.2

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

WANG Jing, LI Jinghui, YANG Jiarong, WANG E. Construction of Optimal Locally Repairable Codes of Triangular Association Schemes[J]. Journal of Shanghai Jiao Tong University, 2024, 58(10): 1596-1605.

图/表 8

图1

表1

构造1参数比较分析

构造方式	构造参数	最小距离	相对距离
构造1构造的BLRCs	n= $(r + 1) (r + 2) 2$ , k= $r (r + 1) 2$ , r,t=2	d_min=3	$6 (r + 1) (r + 2)$
基于近正则图构造的BLRCs^[18]	$n=k+\left\lceil\frac{2 k}{r}\right\rceil,\left\lceil\frac{2 k}{r}\right\rceil \geqslant r+2, t=2$	d_min=3	$3 k + 2 k r$
基于单位矩阵变换构造的BLRCs^[21]	n=r²+2r, k=r², r,t=2	d_min=3	$3 r (r + 2)$
基于直积码构造的BLRCs^[12](t=2)	n=(r+1)², k=r², r,t=2	d_min=4	$4 (r + 1) 2$

表1

图2

表2

推论1参数比较分析

构造方式	构造参数	最小距离	相对距离
推论1构造的BLRCs	n= $(t + 1) (t + 2) 2$ , k=t+1, r=2,t	d_min=t+1	$2 t + 2$
基于单纯形码构造的BLRCs^[22]	n=2^m-1, k=m, r=2, t=2^m^-1-1	d_min=t+1	$t + 1 2 t + 1$
基于直积码构造的BLRCs^[12] (r = 2)	n=3^t, k=2^t, r=2,t	d_min=2^t	$23 t$

表2

图3

表3

构造2构造参数比较分析

构造方式	n	k	r	t	R
构造2构造的BLRCs	$(r + 1) (r + 2) … (r + t) t!$	$r (r + 1) … (r + t - 1) t!$	r>2	t>2	$r r + t$
基于迹函数构造的BLRCs^[13]	2^m-1	2^m^-1-1	m-1	m	$2 r - 1 2 r + 1 - 1$
基于超图构造的BLRCs^[16]	v+ $1 r$ vt	v	v≥t(r-1)+1, r\|vt		$r r + t$
基于阵列LDPC码构造的BLRCs^[14]	r²+rt+1	r²	r(奇素数)	t(偶数)	$r 2 r 2 + r t + 1$
基于直积码构造的BLRCs^[12]	(r+1)^t	r^t	r	t	$r r + 1 t$

表3

图4

图5

参考文献 22

[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.

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

Construction of Optimal Locally Repairable Codes of Triangular Association Schemes

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

图/表 8

参考文献 22

相关文章 3

编辑推荐

Metrics

本文评价

[1]	许亮业, 石连星, 单蓉胜. 一种纠删码条带化数据的一致性检查方法[J]. 上海交通大学学报, 2024, 58(4): 579-584.
[2]	黄鹤, 熊武, 吴琨, 王会峰, 茹锋, 王珺. 基于记忆传递旗鱼优化的K均值混合迭代聚类[J]. 上海交通大学学报, 2022, 56(12): 1638-1648.
[3]	邓凯, 郭洪. 求解导管架相贯线最小距离的编程方法[J]. 海洋工程装备与技术, 2018, 5(增刊): 313-316.