Construction of Optimal Locally Repairable Codes of Triangular Association Schemes

doi:10.16183/j.cnki.jsjtu.2023.151

Abstract

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

CLC Number:

TN911.2

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.

Figures/Tables 8

Fig.1

Tab.1

Comparative analysis of parameters of Construction 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$

Tab.1

Fig.2

Tab.2

Comparative analysis of parameters of Corollary 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$

Tab.2

Fig.3

Tab.3

Comparative analysis of parameters of Construction 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$

Tab.3

Fig.4

Fig.5

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