摘要
分布式存储系统采用冗余策略来确保数据的可靠性和可用性,局部修复码(locally repairable codes,LRC)引起了广泛的关注,极大地减少了数据修复过程中所连接的节点数,在数据存储中作用极大。每个信息码元可以从其他t个不相交的集合中修复,且每个集合大小为r,称此类码具有(r,t)局部度。从校验矩阵入手,提出两种构造具有(r,t)局部度的LRC的方法。方法一利用λ=1的非循环相对差集(relative difference sets,RDS)构造关联矩阵,方法二提出了利用酉设计构造关联矩阵,均在关联矩阵的右侧添加单位矩阵,构造LRC的校验矩阵。两种方法构造的LRC均是一个修复集中包含一个校验节点,并且可以达到任意(r,t)局部度。理论分析表明,构造的两种码的最小距离均满足最小距离界,证明了两种码均是最优的LRC。非循环相对差集构造的码的信息率为1/2,酉设计构造的码的码率在一定条件下高于1/2,码率为r/r+t。
The distributed storage system adopts redundancy strategy to ensure the reliability and availability of data.Locally repairable codes(LRC)has attracted much attention,which greatly reduce the number of nodes connected in the process of data repair and play a great role in data storage.Each information symbol can be repaired from t other disjoint sets and each set size is r,we call codes have(r,t)local degree.Starting with the calibration matrix,two methods of constructing LRC with(r,t)local degree are proposed.The first one uses acyclic relative difference sets(RDS)with parametersλ=1 to construct the correlation matrix,and the other one proposes to construct the correlation matrix by using unital design,then adding the unit matrix to the right of the correlation matrix,and constructing the LRC check matrix.The LRC constructed by both methods are that a repair group contains a check node and can achieve arbitrary(r,t)local degree.Theoretical analysis shows that the minimum distance of the constructed two codes satisfies the minimum distance boundary,which proves that both codes are optimal LRC.The information rate of code constructed by acyclic relative difference sets is 1/2,and that of code constructed by unitary design is higher than 1/2 under certain conditions,and the code rate is r/ r+t.
作者
何亚锦
孙伟
沈克勤
张鑫楠
刘向阳
HE Ya-jin;SUN Wei;SHEN Ke-qin;ZHANG Xin-nan;LIU Xiang-yang(School of Information Engineering,Chang’an University,Xi’an 710064,China;School of Information and Communication,National University of Defense Technology,Xi’an 710106,China)
出处
《计算机技术与发展》
2021年第4期112-117,共6页
Computer Technology and Development
基金
陕西省自然科学基金资助项目(2019JM-386)
中央高校基本科研业务费专项资金资助项目(300102248104,300102248201,300102248401)
大学生创新创业训练计划资助项目(201910710071)。
关键词
分布式存储系统
局部修复码
相对差集
酉设计
最小距离
distributed storage system
locally repairable codes
relative difference sets
unital design
minimum distance
