基于迭代矩阵的局部修复码构造

Construction of locally repairable codes based on iterative matrix

关键词:  分布式存储系统  局部修复码  迭代矩阵  最小距离  码率

Key words:  distributed storage systems  locally repairable codes  iterative matrix  minimum distance  code rate

摘要:

为解决目前分布式存储系统中局部修复码(locally repairable codes,LRCs)参数选择灵活性不足以及码率较低的问题,设计了两类新型的局部修复码。首先,基于全0矩阵和全1向量组合构造一类迭代矩阵,再由构造的此类迭代矩阵作为校验矩阵提出一种全符号具有(r,t)-局部性的局部修复码(all symbol-locally repairable codes,AS-LRCs)的构造算法;随后,通过改进基于迭代矩阵构造的AS-LRCs校验矩阵的结构,进一步提出一种信息符号具有(r,t)-局部性的局部修复码(information symbol-locally repairable codes,IS-LRCs)的构造算法。实验和理论分析表明:AS-LRCs满足严格可用性要求,且在可用性参数t=2时,其码长达到理论最小界,成为码长最优的局部修复码；IS-LRCs的最小距离达到Singleton-like最优界,是最小距离最优的局部修复码；AS-LRCs和IS-LRCs构造算法均支持任意局部性和任意可用性的灵活配置,两种构造算法的码率显著高于现有方法,并在t=2时达到理论码率最优界。两类LRCs的构造算法在保证高效数据修复的同时,支持更灵活的参数配置,并实现更高的码率,为分布式存储系统提供了更高效的编码策略,进而提升分布式存储系统的整体性能。

Abstract:

To address the issues of insufficient parameter flexibility and low code rate in locally repairable codes (LRCs) within current distributed storage systems, this paper introduces two new types of locally repairable codes. First, this paper constructs a class of iterative matrices based on the combination of all-zero matrices and all-one vectors, and then proposes a construction algorithm for all symbol-locally repairable codes (AS-LRCs) with (r,t)-locality using the constructed iterative matrices as parity-check matrices. Subsequently, by improving the structure of the parity-check matrix of AS-LRCs based on iterative matrices, a construction algorithm for information symbol-locally repairable codes (IS-LRCs) with (r,t)-locality is further proposed. Experimental and theoretical analyses show that AS-LRCs meet strict availability requirements, and when the availability parameter t=2, their code length reaches the theoretical minimum bound, making them the optimal LRCs in terms of code length. The minimum distance of IS-LRCs reaches the Singleton-like optimal bound, making them the optimal LRCs in terms of minimum distance. Both AS-LRCs and IS-LRCs construction algorithms support flexible configuration of arbitrary locality and availability. The code rates of the two construction algorithms are significantly higher than existing methods, reaching the theoretical optimal bound of code rate when t=2. The construction algorithms of the two types of LRCs not only ensure efficient data repair but also support more flexible parameter configurations and achieve higher code rates. This provides more efficient coding strategies for distributed storage systems and thereby enhancing the overall performance of distributed storage systems.