Please wait a minute...
浙江大学学报(工学版)  2024, Vol. 58 Issue (3): 501-509    DOI: 10.3785/j.issn.1008-973X.2024.03.007
计算机技术     
基于正交拉丁方的局部修复码构造
刘帅帅(),王静*(),刘哲,徐忠环
1. 长安大学 信息工程学院,陕西 西安 710064
Construction of locally repairable codes based on orthogonal Latin square
Shuaishuai LIU(),Jing WANG*(),Zhe LIU,Zhonghuan XU
1. School of Information Engineering, Chang’an University, Xi’an 710064, China
 全文: PDF(950 KB)   HTML
摘要:

针对目前具有$ \left( {r,t} \right) $局部性的局部修复码码率较低且构造过程中计算复杂度过高的问题,提出基于正交拉丁方的二元局部修复码构造方法. 根据正交拉丁方元素与矩阵位置的对应关系构造关联矩阵,得到具有全符号局部性的局部修复码(AS-LRCs),该码的码率和码长渐近边界条件,且最小距离较大. 利用关联矩阵级联单位矩阵构造信息位具有$ \left( {r,t = 2} \right) $局部性的单校验局部修复码,该码的最小距离和码率均满足最优边界条件,为最优局部修复码. 考虑到实际分布式存储系统中存在高故障率节点,利用正交拉丁方完备组构造具有信息位局部性的高可用性单校验局部修复码(IS-LRCs),可以灵活选择可用性$ t $,提高了系统的鲁棒性与灵活性.

关键词: 分布式存储系统局部修复码正交拉丁方最小距离节点故障率    
Abstract:

The construction of binary locally repairable codes based on orthogonal Latin square was proposed, to resolve the problems of low code rate and high computational complexity of locally repairable codes with $ \left( {r,t} \right) $-locality. The incidence matrix was derived according to the corresponding relationship between the orthogonal Latin square elements and the positions of the digital matrix, and then the all symbol-locally repairable codes (AS-LRCs) were constructed based on the incidence matrix above. The AS-LRCs boasted asymptotically boundary conditions in terms of code rate and code length, and desired minimum distance. The single-check locally repairable codes with information $ \left( {r,t = 2} \right) $-locality were constructed by utilizing the incidence matrix concatenated with an identity matrix. The minimum distance and the code rate of the single-check locally repairable codes reached the optimal boundary conditions, making them be optimal locally repairable codes. Considering that there are nodes with high failure rate in practical distributed storage systems, the single-check information symbol-locally repairable codes (IS-LRCs) with high availability were further constructed through the orthogonal Latin square complete groups, of which the availability parameter $ t $ can be selected flexibly, and the robustness and the flexibility of distributed storage systems were improved.

Key words: distributed storage system    locally repairable code    orthogonal Latin square    minimum distance    node failure rate
收稿日期: 2023-03-22 出版日期: 2024-03-05
CLC:  TN 911.2  
基金资助: 国家自然科学基金资助项目(62001059,62072054);陕西省自然科学基金资助项目(2021GY-019).
通讯作者: 王静     E-mail: ssliu@chd.edu.cn;jingwang@chd.edu.cn
作者简介: 刘帅帅(1998—),男,硕士生,从事分布式存储编码研究. orcid.org/0009-0001-3932-8455. E-mail:ssliu@chd.edu.cn
服务  
把本文推荐给朋友
加入引用管理器
E-mail Alert
作者相关文章  
刘帅帅
王静
刘哲
徐忠环

引用本文:

刘帅帅,王静,刘哲,徐忠环. 基于正交拉丁方的局部修复码构造[J]. 浙江大学学报(工学版), 2024, 58(3): 501-509.

Shuaishuai LIU,Jing WANG,Zhe LIU,Zhonghuan XU. Construction of locally repairable codes based on orthogonal Latin square. Journal of ZheJiang University (Engineering Science), 2024, 58(3): 501-509.

链接本文:

https://www.zjujournals.com/eng/CN/10.3785/j.issn.1008-973X.2024.03.007        https://www.zjujournals.com/eng/CN/Y2024/V58/I3/501

构造方法$ n $$ k $$ r $$ d $
基于完全图构造的
AS-LRCs[15]
$ C^2_{r+2} $$ C^2_{r+1} $$ \forall r $3
基于区组设计构造
的AS-LRCs[18]
$ C^2_{r+2} $$ C^2_{r+1} $$ \forall r $3
基于奇偶校验矩阵构造的
AS-LRCs[19]
$ \left( {r+2} \right)w $$ rw $$ \forall r $3
基于定理4构造的
AS-LRCs
$ {m^2} $$ {\left( {m - 1} \right)^2} $$ m - 1 $4
表 1  几种典型AS-LRCs构造参数对比
图 1  可用性$ t = 2{\text{ }} $时的码率比较
构造方法$ n $$ k $$ R $
基于定理9构造的IS-LRCs$ tr+{r^2} $$ {r^2} $$ r/\left( {r+t} \right) $
基于阵列LDPC码构造的
IS-LRCs[21]
$ {r^2}+rt+1 $$ {r^2} $$ {r^2}/\left( {{r^2}+rt+1} \right) $
基于正则矩阵构造的
IS-LRCs(其中$ \delta = 3 $)[10]
$ v+2vt/r $$ v $$ r/\left( {r+2t} \right) $
表 2  几种典型IS-LRCs构造参数对比
图 2  局部性$ r = 11{\text{ }} $时的码率比较
1 SIDDIQA A, KARIM A, GANI A Big data storage technologies: a survey[J]. Frontiers of Information Technology and Electronic Engineering, 2017, 18 (8): 1040- 1070
doi: 10.1631/FITEE.1500441
2 LI J, LI B C Demand-aware erasure coding for distributed storage systems[J]. IEEE Transactions on Cloud Computing, 2021, 9 (2): 532- 545
doi: 10.1109/TCC.2018.2885306
3 李鑫, 孙蓉, 刘景伟 分布式存储系统中容错技术综述[J]. 无线电通信技术, 2019, 45 (5): 463- 475
LI Xin, SUN Rong, LIU Jingwei Overview of fault-tolerant techniques in distributed storage system[J]. Radio Communication Technology, 2019, 45 (5): 463- 475
doi: 10.3969/j.issn.1003-3114.2019.05.002
4 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
doi: 10.1109/TIT.2012.2208937
5 TAMO I, PAPAILIOPOULOS D S, DIMAKIS A G Optimal locally repairable codes and connections to matroid theory[J]. IEEE Transactions on Information Theory, 2016, 62 (12): 6661- 6671
doi: 10.1109/TIT.2016.2555813
6 JIN L F, MA L M, XING C P Construction of optimal locally repairable codes via automorphism groups of rational function fields[J]. IEEE Transactions on Information Theory, 2020, 66 (1): 210- 221
doi: 10.1109/TIT.2019.2946637
7 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
doi: 10.1109/TIT.2018.2854717
8 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
doi: 10.1109/TIT.2016.2524510
9 JIN L F, KAN H B, ZHANG Y Constructions of locally repairable codes with multiple recovering sets via rational function fields[J]. IEEE Transactions on Information Theory, 2020, 66 (1): 202- 209
doi: 10.1109/TIT.2019.2946627
10 HAO J, SHUM K W, XIA S T, et al Optimal locally repairable codes for parallel reading[J]. IEEE Access, 2020, 8: 80447- 80453
doi: 10.1109/ACCESS.2020.2992188
11 MA J X, GE G N Optimal binary linear locally repairable codes with disjoint repair groups[J]. SIAM Journal on Discrete Mathematics, 2019, 33 (4): 2509- 2529
doi: 10.1137/19M1248443
12 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 (11): 1741- 1757
13 HAO J, XIA S T Constructions of optimal binary locally repairable codes with multiple repair groups[J]. IEEE Communications Letters, 2016, 20 (6): 1060- 1063
doi: 10.1109/LCOMM.2016.2539160
14 TAMO I, BARG A, FROLOV A Bounds on the parameters of locally recoverable codes[J]. IEEE Transactions on Information Theory, 2016, 62 (6): 3070- 3083
doi: 10.1109/TIT.2016.2518663
15 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
doi: 10.1109/TIT.2019.2934124
16 COLBOURN C J, DINITZ J H. Handbook of combinatorial designs [M]. 2nd ed. Boca Raton: CRC Press, 2006.
17 HAO J, SHUM K W, XIA S T, et al. On optimal quaternary locally repairable Codes [C]// 2021 IEEE International Symposium on Information Theory . Melbourne: ISIT, 2021: 3267−3272.
18 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: ISIT, 2015: 1866−1870.
19 JING Z, SONG H Y. A construction of 2-sequential-recovery locally repairable codes [C]// 2021 IEEE International Conference on Information and Communication Technology Convergence . Jeju Island: ICTC, 2021: 1431−1433.
20 HU Y P, LIU Y H, LI W J, et al Unequal failure protection coding technique for cloud storage systems[J]. IEEE Transactions on Cloud Computing, 2021, 9 (1): 386- 400
doi: 10.1109/TCC.2017.2785396
[1] 余利华, 陈刚, 王伟, 陈柯, 董金祥. 一种基于容器的自组织存储模型[J]. J4, 2010, 44(5): 915-922.