Construction of locally repairable codes based on iterative matrix

doi:10.11918/202302054

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

doi: 10.11918/202302054

王娥，王静，李静辉，杨佳蓉

长安大学信息工程学院，西安 710064

基金项目: 国家自然科学基金(62001059) ；陕西省重点研发计划(2021GY-019) ；长安大学大学生创新创业训练计划(S202310710121)

详细信息

作者简介

王娥(1998—)，女，硕士研究生；

王静(1982—)，女，教授，硕士生导师

通讯作者

王静，jingwang@chd.edu.cn

中图分类号: TN911.2

文献标识码: A

文章编号: 0367-6234(2025)09-0087-08

Construction of locally repairable codes based on iterative matrix

WANG E ， WANG Jing ， LI Jinghui ， YANG Jiarong

School of Information Engineering, Chang′an University, Xi′an 710064 , China

摘要

为解决目前分布式存储系统中局部修复码(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.

Keywords

distributed storage systems / locally repairable codes / iterative matrix / minimum distance / code rate

1 局部修复码 2 基于迭代矩阵构造BLRCs 2.1 基于迭代矩阵构造AS-LRCs 2.2 基于迭代矩阵构造IS-LRCs 3 性能分析 3.1 局部性和可用性 3.2 码率 3.2.1 几种（n，k，r，t）_all-BLRCs码率的对比分析 3.2.2 几种（n，k，r，t）_in-BLRCs码率的对比分析 4 结论

随着互联网的快速发展，互联网数据呈指数增长趋势，海量数据的存储和处理成为当前研究的热点^[1]。大规模分布式存储系统（distributed storage systems，DSSs）因低成本和高可扩展性，非常适用于海量数据存储。DSSs通常采用冗余策略来确保数据存储的可靠性和可用性^[2]，常用的解决方案是复制策略。复制策略可简单、快速地修复故障节点，但存储开销过大^[3]。为此，纠删码被大规模应用于DSSs，以降低存储开销并提高存储可靠性。然而，纠删码策略会导致较高的修复带宽开销和磁盘I/O开销 ^[4-5]。为了解决这一问题，Gopalan等^[6]提出了局部修复码（locally repairable codes，LRCs），其可以有效降低修复过程中连接的节点数，减少故障节点修复的磁盘I/O开销。为了进一步实现并行修复，Wang等^[7]引入了（r，t）-局部性的概念，在具有（r，t）-局部性的LRCs中，节点中存储的数据可以通过t+1种不同的方式获得，有效保证了数据的可用性和可靠性。

最小距离和码率是LRCs的两个重要特性。最小距离越大，码的纠错能力越强；码率越大，码的信息传输速率越高。Hao等^[8]推导了LRCs码长的上界，并且提出了修复组大小为2时，具有最大码长的q元LRCs的构造算法。这类码的最小距离很大，但码率较低。Jin等^[9]通过自同构群构造了具有多个修复集的LRCs，但其最小距离始终比最小距离上界小1，且码率较低。Fu等^[10]基于三维单纯形码提出了具有（2，q）-局部性的LRCs，其最小距离达到了Singleton-like界，是最小距离最优的LRCs。但码率不高，参数选择也不够灵活。Hao等^[11]提出了一种用于并行读取的LRCs，每个信息符号的多个修复子集保证了数据的并行读取，实现了信息符号（r，t，δ）-局部性，该码在δ=2时实现了最优最小距离，但码率恒为0.5。

局部性参数r和可用性参数t是LRCs的两个重要构造参数，两者的灵活选择对于大数据背景下需求多元化的DSSs至关重要。到目前为止，唯一已知的能够实现任意局部性和可用性的LRCs是直积码^[12]和Wang等^[13]构造的LRCs，但直积码码率较低，Wang等^[13]的构造算法复杂。其他均是基于r和t的特殊值构造LRCs。Cai等^[14]基于组合设计理论，建立了LRCs与打包设计之间的密切关系，提出了一类最小距离最优的LRCs的显式结构，但其t的取值范围很受限。Song等^[15]提出了可分解局部修复码（sequential locally repairable codes，SLRCs），该修复码在t∈{2，3}时实现了最优码率，但是其t限制较大。Kim等^[16]基于图设计提出了几种具有联合局部性的二元局部修复码（binary locally repairable codes，BLRCs）。虽然在特殊情况下能够实现最优最小距离和最优码率，但其构造的码在修复单故障节点时r恒为2，t取值也十分局限。Tan等^[17]基于部分几何构造了信息符号具有（r，t）-局部性的BLRCs，实现了最优最小距离，但其局部性和可用性的参数限制也较大。

为解决上述问题，本文设计了两类新型的LRCs。首先基于迭代矩阵构造一种全符号具有（r，t）-局部性的二元局部修复码（all symbol-binary locally repairable codes，AS-BLRCs）；然后对迭代矩阵进行推广，构造一种信息符号具有（r，t）-局部性的二元局部修复码（information symbol-binary locally repairable codes，IS-BLRCs）；最后，将构造的基于迭代矩阵的AS-BLRCs和IS-BLRCs分别与现有的AS-BLRCs和IS-BLRCs在局部性、可用性以及码率方面进行对比分析。

1 局部修复码

现代DSSs采用各种编码技术提高系统性能。其中，LRCs的目的是最小化修复局部性，即单个故障节点修复所需的磁盘访问数。对于一个（n，k）线性码C来说，如果C的一个码字符号可以通过访问最多r个其他码字符号来修复，则将码C称为具有局部性r的（n，k，r）-LRCs。有时，存储系统中会遇到多个存储节点同时发生故障的情况。此时，修复性能在很大程度上依赖于正在使用的修复策略。当一个节点及其任意一个帮助节点失效时，（n，k，r）-LRCs将无法继续执行局部修复功能，因此具有多个修复组的（n，k，r，t）-LRCs受到广泛关注。在（n，k，r，t）-LRCs中，可以并行修复故障节点，进一步提升了存储系统的容错能力和存储节点的修复效率。

定义1（（n，k，r，t）-LRCs）^[18] 如果（n，k，r）-LRCs的码字符号c_i∈C可以被大小至多为r的t个不相交的修复集修复，则称该局部修复码为具有（r，t）-局部性的（n，k，r，t）局部修复码，记作（n，k，r，t）-LRCs。（n，k，r，t）-LRCs需要满足下列条件：

1）有t个子集，满足φ₁（i），φ₂（i），···，φ_t（i）

\subset

[n]\{i}；

2) |φ_j (i) |≤r，j∈[t]；

3) φ_j (i) ∩φ_l (i) =φ，j≠l∈[t]。

式中φ_j（i）（j∈[t]）为c_i的修复集。

定义2（IS-LRCs和AS-LRCs）^[19] 若（n，k，r，t）-LRCs的全部信息符号具有（r，t）-局部性，则称该局部修复码为具有信息符号局部性的（n，k，r，t）-IS-LRCs或（n，k，r，t）_in-LRCs。若（n，k，r，t）-LRCs的所有符号均具有（r，t）-局部性，则称该局部修复码为具有全符号局部性的（n，k，r，t）-AS-LRCs或（n，k，r，t）_all-LRCs。

定义3（SA-LRCs）^[20] 若局部修复码的校验矩阵H_x_×_y的每行具有相同的行重r+1，每列具有相同的列重t，则称该局部修复码为具有严格可用性的（n，k，r，t）-SA-LRCs或（n，k，r，t）_sa-LRCs，且yt=x（r+1）。

定义4（最小距离）^[21] 假设u和v表示码C的两个任意不同的码字，则C的最小距离可以定义为

d = m i n {d (u, v)}

(1)

式中d（u，v）为u和v之间的汉明距离。

定理1^[17] 对于具有（r，t）-局部性的（n，k，r，t）-LRCs，其最小距离满足：

d ⩾ t + 1

(2)

定理2^[18] 若（n，k，r，t）-IS-LRCs每个信息符号的修复集只包含单个校验符号，那么该局部修复码被称为单校验（n，k，r，t）-IS-LRCs，该单校验（n，k，r，t）-IS-LRCs的最小距离界满足：

d ⩽ n - k - ⌈\frac{k t}{r}⌉ + t + 1

(3)

当且仅当式（3）等号成立时，称单校验（n，k，r，t）-IS-LRCs达到了最优最小距离界。此时（n，k，r，t）-IS-LRCs的最小距离达到了最大值，抗干扰能力最强。在同样译码方法下，译码错误率最小。

定理3^[22] （n，k，r，t）-SA-LRCs的码长界满足:

n ⩾ (r + 1)^{2} - \frac{r (r + 1)}{t}

(4)

当且仅当式（4）等号成立时，称（n，k，r，t）-SA-LRCs达到了最小码长界。此时（n，k，r，t）-SA-LRCs的码长达到了最小值，编解码复杂度最低，耗时最小。

2 基于迭代矩阵构造BLRCs

提出两种基于迭代矩阵H^a^，^b的BLRCs的构造算法。矩阵H^a^，^b具体结构如下：

当b=1时，

H^{a, b} = H^{a, 1} = 1_{a} = (\begin{matrix} 1 \dots 1 \end{matrix}) \in F_{2}^{1 \times a}

(5)

当a=b时，

H^{a, b} = H^{a, a} = {(1_{a})}^{T} = (\begin{matrix} 1 \\ ⋮ \\ 1 \end{matrix}) \in F_{2}^{a \times 1}

(6)

(7)

式中：

I_{（ \binom{a - 1}{b - 1} ）}

为

C_{a - 1}^{b - 1}

阶单位矩阵，

0_{（ \binom{a - 1}{b} ）}

为列数为

C_{a - 1}^{b}

、行数与矩阵H^a^-1，^b^-1行数一致的全0矩阵。

2.1 基于迭代矩阵构造AS-LRCs

基于矩阵H^a^，^b构造（

n = C_{r + t}^{t} ， k = C_{r + t - 1}^{t} ， r = r ，

t=t）_all-BLRCs，具体步骤如下：

步骤1 令m＞t≥1为任意正整数，给定m和t。令r=m-t，则r≥1。

步骤2 将a=m，b=t代入矩阵H^a^，^b，得到校验矩阵H^m^，^t。

步骤3 若矩阵H^m^，^t中的所有二进制元素可知，则由校验矩阵H^m^，^t定义的二进制线性码C是全符号具有（r，t）-局部性的（

n = C_{r + t}^{t} ， k = C_{r + t - 1}^{t} ， r = r ，

t=t）_all-BLRCs；否则，将矩阵H^m^，^t中所有元素未知的子矩阵代入式（7），不断迭代，直到所有子矩阵迭代至b=1或a=b，H^m^，^t中所有二进制元素可知。

定理4 由校验矩阵H^m^，^t构造的（

n = C_{r + t}^{t} ， k = C_{r + t - 1}^{t} ， r = r ，

t=t）_all-BLRCs是具有严格可用性的SA-LRCs，且最小距离d=t+1。

证明对于任意i∈[n]，由校验矩阵H^m^，^t的结构可知，若

\{h_{i_{1}} ， h_{i_{2}} ， \dots ， h_{i_{t}}\}

是校验矩阵H^m^，^t第i列元素为1的行组成的集合，则有

s u p p (h_{i_{j}}) ∣ = r + 1 （ j \in [t] ）

，且

s u p p (h_{i_{j}}) \cap s u p p (h_{i_{j^{'}}}) = {i}

（j≠j′）。即对于校验矩阵H^m^，^t，因为H^m^，^t每一列列重为t，每一行行重为r+1，且任意两行至多有一列元素同时为1，所以由校验矩阵H^m^，^t构造的BLRCs的每个码字符号都有t个修复集。t个修复集互不相交，且每个修复集的大小均为r，即该BLRCs的所有符号都具有（r，t）-局部性。

将校验矩阵H^m^，^t的行数

x = C_{r + t}^{t - 1}

和列数

y = C_{r + t}^{t}

代入yt，可得

\begin{matrix} y t = C_{r + t}^{t} \times t = \frac{(r + t) (r + t - 1) \dots (r + 1)}{t!} \times t = \\ \frac{(r + t) (r + t - 1) \dots (r + 2)}{(t - 1)!} \times (r + 1) = \\ C_{r + t}^{t - 1} \times (r + 1) = x (r + 1) \end{matrix}

(8)

即由校验矩阵H^m^，^t构造的（

n = C_{r + t}^{t} ， k = C_{r + t - 1}^{t} ， r = r ，

t=t）_all-BLRCs是具有严格可用性的SA-LRCs。由定理1可知，该SA-LRCs的最小距离d≥t+1；另一方面，H^m^，^t中存在t+1列线性相关，即该SA-LRCs的最小距离d≤t+1，因此，基于迭代矩阵构造的（n，k，r，t）_all-BLRCs的最小距离d=t+1，证毕。

定理5 由校验矩阵H^m^，2构造的

{(n = C_{r + 2}^{2} ， k = C_{r + 2 - 1}^{2} ， r = r ， t = 2)}_{s a}

-BLRCs是码长最小的（n，k，r，t）-SA-LRCs。

证明将

{(n = C_{r + 2}^{2} ， k = C_{r + 2 - 1}^{2} ， r = r ， t = 2)}_{s a}

-BLRCs的构造参数t=2代入式（4），可得

\begin{matrix} n ⩾ (r + 1)^{2} - \frac{r (r + 1)}{t} = (r + 1)^{2} - \frac{r (r + 1)}{2} = \\ \frac{(r + 2) (r + 1)}{2} = C_{r + 2}^{2} \end{matrix}

(9)

码长

n = C_{r + 2}^{2}

达到了t=2时式（4）给出的最小码长下界，即基于迭代矩阵构造的

{(n = C_{r + 2}^{2} ， k = C_{r + 2 - 1}^{2} ， r = r ， t = 2)}_{s a}

-BLRCs是码长最小的（n，k，r，t）-SA-LRCs，证毕。

例1 考虑在DSSs中，期望所有符号均具有较高可靠性和可用性的情况。当任意一个节点失效时，为降低修复局部性、实现修复方案多样化和并行通信，通过设计（n，k，r，t）_all-LRCs保证每个故障节点具有t个修复集，且每次修复需要访问任意r个幸存节点。以下给出m=4、t=2时（n=6，k=3，r=2，t=2）_all-BLRCs的构造过程。

当m=4、t=2时，r=m-t=2。将a=m=4、b=t=2代入式（7），可得矩阵

。由式（5）可知，矩阵H^3，1=（1 1 1），将a=3、b=2再次代入式（7），可得矩阵

。由式（5）和（6）可知，H^2，1=（1 1），

H^{2，2} = （ \binom{1}{1} ）

。因此，校验矩阵

。由校验矩阵H^4，2构造的（n=6，k=3，r=2，t=2）_all-BLRCs的最小距离d=t+1=3，所有码字符号均具有r=2，可用性t=2。

2.2 基于迭代矩阵构造IS-LRCs

基于矩阵H^a^，^b构造单校验

(n = C_{r + t}^{t} ， k = C_{r + t - 1}^{t} ， r = r ， t = t ）_{i n}

-BLRCs，具体步骤如下：

步骤1 令m＞t≥1为任意正整数，给定m和t。令r=m-t，则r≥1。

步骤2 令a=m-1，b=t并代入矩阵H^a^，^b，得到校验矩阵H^m^-1，^t。

步骤3 若矩阵H^m^-1，^t中的所有二进制元素可知，在矩阵H^m^-1，^t后级联一个

C_{r + t - 1}^{t - 1}

阶单位矩阵

I_{（ \binom{r + t - 1}{t - 1} ）}

，得到校验矩阵

H = (H^{m - 1 ， t} |I_{（ \binom{r + t - 1}{t - 1} ）})

，则由该校验矩阵H定义的二进制线性码C是信息符号具有（r，t）-局部性的单校验

(n = C_{r + t}^{t} ， k = C_{r + t - 1}^{t} ， r = r ， t = t ）_{i n}

-BLRCs；否则，将H^m^-1，^t中所有元素未知的子矩阵代入式（7），不断迭代，直到所有子矩阵迭代至b=1或a=b，H^m^-1，^t中所有二进制元素可知。

定理6 由校验矩阵

H = (H^{m - 1 ， t} |I_{（ \binom{r + t - 1}{t - 1} ）})

构造的单校验

(n = C_{r + t}^{t} ， k = C_{r + t - 1}^{t} ， r = r ， t = t ）_{i n}

-BLRCs是最小距离最优的单校验（n，k，r，t）-IS-LRCs，且最小距离d=t+1。

证明由定理4已知，由校验矩阵H^m^，^t构造的BLRCs是具有严格可用性的SA-LRCs，所以矩阵H^m^，^t每一行行重为r+1，每一列列重为t。因此矩阵H^m^-1，^t每一行行重为r，每一列列重为t，且任意两行至多有一列元素同时为1。又因为单位矩阵

I_{（ \binom{r + t - 1}{t - 1} ）}

每一行行重为1，所以由校验矩阵

H = (H^{m - 1 ， t} |I_{（ \binom{r + t - 1}{t - 1} ）})

构造的BLRCs的每个信息符号都有t个修复集。t个修复集互不相交，每个修复集的大小均为r，且每个修复集仅包含一个校验符号，即该单校验BLRCs的所有信息符号都具有（r，t）-局部性。

将基于校验矩阵

H = (H^{m - 1 ， t} |I_{（ \binom{r + t - 1}{t - 1} ）})

构造的单校验

(n = C_{r + t}^{t} ， k = C_{r + t - 1}^{t} ， r = r ， t = t ）_{i n}

-BLRCs的构造参数

n = C_{r + t}^{t} ， k = C_{r + t - 1}^{t} ， r = r ， t = t

代入定理2，可得

\begin{matrix} d ⩽ n - k - ⌈\frac{k t}{r}⌉ + t + 1 = \\ C_{r + t}^{t} - C_{r + t - 1}^{t} - ⌈\frac{C_{r + t - 1}^{t} \times t}{r}⌉ + t + 1 = \\ \frac{(r + t - 1) (r + t - 2) \dots (r + 1)}{(t - 1)!} - \\ ⌈\frac{(r + t - 1) (r + t - 2) \dots (r + 1) \times t}{t!}⌉ + t + 1 = t + 1 \end{matrix}

(10)

另一方面，由定理1可知d≥t+1。因此基于校验矩阵

H = (H^{m - 1 ， t} |I_{（ \binom{r + t - 1}{t - 1} ）})

构造的单校验

(n = C_{r + t}^{t} ， k = C_{r + t - 1}^{t} ， r = r ， t = t ）_{i n}

-BLRCs的最小距离d=t+1，达到了定理2给出的最小距离上界，是最小距离最优的单校验（n，k，r，t）-IS-LRCs，证毕。

例2 考虑到DSSs中冷热数据访问频率的不同，只关注信息符号具有较高可靠性和可用性，同时保证校验符号具有较低故障频率的情况。当任意一个信息节点失效时，为降低修复局部性及实现对热数据（信息符号）的并行读取和多路修复，通过设计单校验（n，k，r，t）_in-LRCs保证每个信息符号具有t个修复集，且每次修复需要访问1个校验节点和r-1个幸存的信息节点。以下给出m=4、t=2时，单校验（n=6，k=3，r=2，t=2）_in-BLRCs的构造过程。

当m=4、t=2时，r=m-t=2。将a=m-1=3、b=t=2代入式（7），可得矩阵

H^{3，2} =

，由式（5）和（6）可知，矩阵H^2，1=（1 1），

H^{2，2} = （ \binom{1}{1} ）

，因此，矩阵

H^{m - 1 ， t} = H^{3，2} =

，则校验矩阵

H = (H^{3，2} ∣ I) =

。

由校验矩阵H构造的单校验（n=6，k=3，r=2，t=2）_in-BLRCs的最小距离d=t+1=3。若信息符号c₁故障，有c₁=c₄-c₂=c₅-c₃，因此信息符号c₁的修复集为φ₁（1）={2，4}，φ₂（1）={3，5}。若校验符号c₄故障，有c₄=c₁+c₂，因此校验符号c₄的修复集为φ（4）={1，2}。同样地，可以得到其他码字符号的修复集。

3 性能分析

3.1 局部性和可用性

将本文提出的基于迭代矩阵构造的二元局部修复码与其他二元局部修复码进行构造参数方面的对比，见表1。其中，构造参数包括局部性和可用性，为了方便比较，将码的局部性均用r表示，可用性均均用t表示。

表1几种（n，k，r，t）-BLRCs的r和t对比

Tab.1Comparison of r and t of several (n, k, r, t) -BLRCs

由表1可知，除基于直积码构造的AS-BLRCs，本文提出的基于迭代矩阵构造的（

n = C_{r + t}^{t} ， k = C_{r + t - 1}^{t} ， r = r ， t = t

）all-BLRCs和（

n = C_{r + t}^{t} ， k = C_{r + t - 1}^{t} ， r = r ， t = t

）in-BLRCs的构造参数r和t选择更加灵活，均实现了（

\forall r ， \forall t

）-局部性。

另外，文献^[28]证明了当（n，k，d）-LRCs同时满足d-最优和r-最优时，该LRCs是最优局部修复码。定理6已经证明了基于迭代矩阵构造的（

n = C_{r + t}^{t} ， k = C_{r + t - 1}^{t} ， r = r ， t = t

）_in-BLRCs是最小距离最优的单校验（n，k，r，t）-IS-LRCs。

证明基于迭代矩阵构造的（

n = C_{r + t}^{t} ， k = C_{r + t - 1}^{t} ， r = r ， t = t

）_in-BLRCs是局部性最优的单校验（n，k，r，t）-IS-LRCs。

文献^[29]给出了（n，k，r）局部修复码的局部性限，同理可推导出单校验（n，k，r，t）-IS-LRCs的局部性满足：

r ⩾ \frac{k t}{n - k - d + t + 1}

(11)

将基于迭代矩阵构造的单校验（

n = C_{r + t}^{t} ， k = C_{r + t - 1}^{t} ， r = r ， t = t

）_in-BLRCs的构造参数

n = C_{r + t}^{t} ， k = C_{r + t - 1}^{t} ， r = r

，d=t+1代入式（11），可得

\begin{matrix} r ⩾ ⌈\frac{C_{r + t - 1}^{t} \times t}{C_{r + t}^{t} - C_{r + t - 1}^{t} - (t + 1) + t + 1}⌉ = \\ ⌈\frac{\frac{(r + t - 1) (r + t - 2) \dots r \times t}{t!}}{\frac{(r + t) (r + t - 1) \dots (r + 1) - (r + t - 1) (r + t - 2) \dots r}{t!}}⌉ = \\ ⌈\frac{(r + t - 1) (r + t - 2) \dots r \times t}{(r + t - 1) \dots (r + 1) (r + t - r)}⌉ = r \end{matrix}

(12)

即基于迭代矩阵构造的（

n = C_{r + t}^{t} ， k = C_{r + t - 1}^{t} ， r = r ， t = t

）_in-BLRCs的r满足局部性限，是局部性最优的（n，k，r，t）-IS-LRCs，所以基于迭代矩阵构造的（

n = C_{r + t}^{t} ， k = C_{r + t - 1}^{t} ， r = r ， t = t

）_in-BLRCs既满足d-最优又满足r-最优，是最优的（n，k，r，t）-IS-LRCs。

3.2 码率

在（n，k）线性码C中，令R=k/n表示码C的码率。R是衡量线性码有效性的一个基本参数，R越大，信息位在码字中所占的比重越大，每个码元携带的有用信息越多，编码效率越高。下面将本文提出的两类基于迭代矩阵构造的BLRCs的码率与最优码率界进行比较。

文献^[30]提出了具有（r，t）-局部性的（n，k，r，t）-LRCs的最优码率界为

(13)

特别地，当t=2时，文献^[23]提出了（n，k，r，2）-LRCs的最优码率界为

R ⩽ \frac{r}{r + 2}

(14)

本文提出的基于迭代矩阵构造的（

n = C_{r + t}^{t} ， k = C_{r + t - 1}^{t} ， r = r ， t = t

）_all-BLRCs和（

n = C_{r + t}^{t} ， k = C_{r + t - 1}^{t} ， r = r ， t = t

）_in-BLRCs的码率均为

R = \frac{k}{n} = \frac{C_{r + t - 1}^{t}}{C_{r + t}^{t}} = \frac{\frac{(r + t - 1) (r + t - 2) \dots r}{t!}}{\frac{(r + t) (r + t - 1) \dots (r + 1)}{t!}} = \frac{r}{r + t}

(15)

当t=1时，两种BLRCs的码率均达到了式（13）中的最优码率界；当t=2时，两种BLRCs的码率均达到了式（14）中的最优码率界，即t∈{1，2}时，本文构造的两种BLRCs均是码率最优的（n，k，r，t）-LRCs。

将本文提出的基于迭代矩阵构造的BLRCs的码率与其他BLRCs的码率进行对比。为了方便比较，本文将码的码率均用R表示。对比结果见表2。

表2几种（n，k，r，t）-BLRCs的码率对比

Tab.2Comparison of code rates of several (n, k, r, t) -BLRCs

3.2.1 几种（n，k，r，t）_all-BLRCs码率的对比分析

由表2可知：本文提出的基于迭代矩阵构造的AS-BLRCs与基于完全图构造的AS-BLRCs相比，当t≤2时，

\frac{r}{r + t} ⩾ \frac{r}{r + 2}

。即t≤2时，本文构造的基于迭代矩阵的AS-BLRCs的码率大于等于基于完全图构造的AS-BLRCs的码率。事实上，基于迭代矩阵构造的AS-BLRCs利用校验矩阵H^m^，t=H^r^+2，2定义的AS-BLRCs与基于完全图构造的AS-BLRCs完全相同，即基于完全图构造的AS-BLRCs是基于迭代矩阵构造的AS-BLRCs在t=2时的一种特殊情况，而基于迭代矩阵构造的AS-BLRCs给出了t为任意值时的一般构造。与基于张量积矩阵构造的AS-BLRCs相比，当

\frac{t}{r} ⩽ \frac{4}{3}

时，

\frac{r}{r + t} = \frac{1}{1 + t / r} ⩾ \frac{3}{7}

。即

\frac{t}{r} ⩽ \frac{4}{3}

时，本文构造的基于迭代矩阵的AS-BLRCs的码率始终大于等于基于张量积矩阵构造的AS-BLRCs的码率。与基于直积码构造的AS-BLRCs相比，因为

{(1 + \frac{1}{r})}^{t} ⩾ 1 + \frac{t}{r}

，所以

1 / {(1 + \frac{1}{r})}^{t} ⩽ 1 / (1 + \frac{t}{r}) = \frac{r}{r + t}

。即本文构造的基于迭代矩阵的AS-BLRCs的码率始终大于等于基于直积码构造的AS-BLRCs的码率。

为了更直观地表示相同r和相同t时，上述几种AS-BLRCs的R随r和t的变化趋势，以及其码率与最优码率界之间的关系，图1给出了r=2时，上述两类AS-BLRCs的R随t的变化曲线。r=2时，基于完全图构造的AS-BLRCs和基于张量积矩阵构造的AS-BLRCs仅在单个点处取值，故这两类码不在图1中示意。可以看出，随着t的增大，两类码的R同时呈减小的趋势，且t越大，R减小的趋势越缓慢。当t取相同值时，基于迭代矩阵构造的AS-BLRCs的码率始终高于基于直积码构造的AS-BLRCs的码率。当t=1时，两类码的码率同时达到了最优码率界^[30]；当t＞1时，两类码的码率始终低于最优码率界^[30]。

图1r=2时，两类AS-BLRCs码率对比

Fig.1Comparison of code rates of two AS-BLRCs when r=2

图2给出了t=2时，上述3类AS-BLRCs的R随r的变化曲线。t=2时，基于张量积矩阵构造的AS-BLRCs无取值，故不在图2中示意。可以看出，随着r的增大，3类AS-BLRCs的码率同时呈增大的趋势，且r越大，码率增大的趋势越缓慢。当r取相同值时，本文提出的基于迭代矩阵构造的AS-BLRCs的码率始终高于基于直积码构造的AS-BLRCs的码率。另外，本文提出的基于迭代矩阵构造的AS-BLRCs的码率与基于完全图构造的AS-BLRCs的码率完全重合，且均达到了最优码率界^[23]，证明t=2时，本文提出的基于迭代矩阵构造的AS-BLRCs是码率最优的（n，k，r，2）-LRCs。

图2t=2时，3类AS-BLRCs码率对比

Fig.2Comparison of code rates of three AS-BLRCs when t=2

3.2.2 几种（n，k，r，t）_in-BLRCs码率的对比分析

由表2可知：本文提出的基于迭代矩阵构造的IS-BLRCs与基于阵列LDPC码构造的IS-BLRCs相比，因为

\frac{r^{2}}{r^{2} + t r + 1} = \frac{1}{1 + t / r + 1 / r^{2}} < \frac{1}{1 + t / r} = \frac{r}{r + t}

，所以本文构造的基于迭代矩阵的IS-BLRCs的码率始终大于基于阵列LDPC码构造的IS-BLRCs的码率。与基于仿射平面构造的IS-BLRCs相比，当t≤r时，

\frac{r}{r + t} = \frac{1}{1 + t / r} ⩾ \frac{1}{2}

。即t≤r时，本文构造的基于迭代矩阵的IS-BLRCs的码率始终大于等于基于仿射平面构造的IS-BLRCs的码率。与基于完全多部图构造的IS-BLRCs相比，当r≥2时，

\frac{r}{r + t} = \frac{1}{1 + t / r} ⩾ \frac{1}{1 + t / 2} = \frac{2}{2 + t}

。即r≥2时，本文构造的基于迭代矩阵的IS-BLRCs的码率始终大于等于基于完全多部图构造的IS-BLRCs的码率。

为了更直观地表示相同r和相同t时，上述几种IS-BLRCs的R随r和t的变化趋势，以及其码率与最优码率界之间的关系，图3给出了r=2时，上述3类IS-BLRCs的码率随t的变化曲线。r=2时，基于仿射平面构造的IS-BLRCs仅在单个点处取值，故不在图3中示意。可以看出，随着t的增大，3类码的码率均呈减小的趋势，且t越大，码率减小的趋势越缓慢。当t取相同值时，基于迭代矩阵构造的IS-BLRCs的码率与基于完全多部图构造的IS-BLRCs的码率相等，且始终高于基于阵列LDPC码构造的IS-BLRCs的码率。当t=1时，3类码的码率同时达到了最优码率界^[30]；当t＞1时，3类码的码率始终低于最优码率界^[30]。

图3r=2时，3类IS-LRCs码率对比

Fig.3Comparison of code rates of three IS-BLRCs when r=2

图4给出了t=2时，上述3类IS-BLRCs的R随r的变化曲线。t=2时，基于仿射平面构造的IS-BLRCs仅在单个点处取值，故不在图4中示意。可以看出，随着r的增大，除基于完全多部图构造的IS-BLRCs外，其他两类码的码率均呈增大的趋势，且r越大，码率增大的趋势越缓慢。当r取相同值时，本文提出的基于迭代矩阵构造的IS-BLRCs的码率始终高于基于阵列LDPC码构造的IS-BLRCs的码率。当r＞2时，本文提出的基于迭代矩阵构造的IS-BLRCs的码率始终高于基于完全多部图构造的IS-BLRCs的码率。另外，本文提出的基于迭代矩阵构造的IS-BLRCs的码率与最优码率界^[23]完全重合，证明t=2时，本文提出的基于迭代矩阵构造的IS-BLRCs是码率最优的（n，k，r，2）-LRCs。

图4t=2时，3类IS-BLRCs码率对比

Fig.4Comparison of code rates of three IS-BLRCs when t=2

4 结论

1）基于迭代矩阵构造的两种局部修复码的局部性和可用性的参数取值更加灵活，均实现了（

\forall r

，

\forall t

）。

2）本文构造的（n，k，r，t）-AS-LRCs满足严格可用性要求，且当t=2时，本文构造的（n，k，r，t）_all-BLRCs的码长达到了最小码长界，实现码长最优。本文构造的（n，k，r，t）-IS-LRCs的局部性满足局部性限，同时最小距离达到Singleton-like最优界，局部性和最小距离均达到最优。

3）当可用性或局部性一定时，本文构造的AS-BLRCs和IS-BLRCs的码率均高于基于阵列LDPC码构造的IS-BLRCs的码率。

4）当t=1时，本文构造的AS-BLRCs和IS-BLRCs的码率均达到了文献^[30]提出的最优码率界；当t=2时，两种BLRCs的码率均达到了文献^[23]提出的最优码率界，即t∈{1，2}时，AS-BLRCs和IS-BLRCs均实现码率最优。

图1r=2时，两类AS-BLRCs码率对比

Fig.1Comparison of code rates of two AS-BLRCs when r=2

下载: 全尺寸图片

图2t=2时，3类AS-BLRCs码率对比

Fig.2Comparison of code rates of three AS-BLRCs when t=2

下载: 全尺寸图片

图3r=2时，3类IS-LRCs码率对比

Fig.3Comparison of code rates of three IS-BLRCs when r=2

下载: 全尺寸图片

图4t=2时，3类IS-BLRCs码率对比

Fig.4Comparison of code rates of three IS-BLRCs when t=2

下载: 全尺寸图片

表1几种（n，k，r，t）-BLRCs的r和t对比

Tab.1Comparison of r and t of several (n, k, r, t) -BLRCs

下载: 全尺寸图片

表2几种（n，k，r，t）-BLRCs的码率对比

Tab.2Comparison of code rates of several (n, k, r, t) -BLRCs

下载: 全尺寸图片

图1r=2时，两类AS-BLRCs码率对比

Fig.1Comparison of code rates of two AS-BLRCs when r=2

图2t=2时，3类AS-BLRCs码率对比

Fig.2Comparison of code rates of three AS-BLRCs when t=2

图3r=2时，3类IS-LRCs码率对比

Fig.3Comparison of code rates of three IS-BLRCs when r=2

图4t=2时，3类IS-BLRCs码率对比

Fig.4Comparison of code rates of three IS-BLRCs when t=2

表1几种（n，k，r，t）-BLRCs的r和t对比

Tab.1Comparison of r and t of several (n, k, r, t) -BLRCs

表2几种（n，k，r，t）-BLRCs的码率对比

Tab.2Comparison of code rates of several (n, k, r, t) -BLRCs

图1r=2时，两类AS-BLRCs码率对比

Fig.1Comparison of code rates of two AS-BLRCs when r=2

图2t=2时，3类AS-BLRCs码率对比

Fig.2Comparison of code rates of three AS-BLRCs when t=2

图3r=2时，3类IS-LRCs码率对比

Fig.3Comparison of code rates of three IS-BLRCs when r=2

图4t=2时，3类IS-BLRCs码率对比

Fig.4Comparison of code rates of three IS-BLRCs when t=2

表1几种（n，k，r，t）-BLRCs的r和t对比

Tab.1Comparison of r and t of several (n, k, r, t) -BLRCs

表2几种（n，k，r，t）-BLRCs的码率对比

Tab.2Comparison of code rates of several (n, k, r, t) -BLRCs

BHUVANESHWARI P V, THARINI C. Review on LDPC codes for big data storage[J]. Wireless Personal Communications,2021,117(2):1601. DOI:10.1007/s11277-020-07937-4

QI Yichuan, FENG Dan, HOU Binbing. Towards building reliable and cost-efficient distributed storage systems[J]. IEEE Access,2020,8:157862. DOI:10.1109/ACCESS.2020.3019108

ZHU Bing, WANG Weiping, WANG Jianxin. On some capacity-achieving fractional repetition codes[J]. IEEE Transactions on Vehicular Technology,2022,71(3):3332. DOI:10.1109/TVT.2022.3142931

LI Jun, LI Baochun. Demand-aware erasure coding for distributed storage systems[J]. IEEE Transactions on Cloud Computing,2021,9(2):532. DOI:10.1109/TCC.2018.2885306

QIAO Yi, ZHANG Menghao, ZHOU Yu,et al. NetEC:accelerating erasure coding reconstruction with in-network aggregation[J]. IEEE Transactions on Parallel and Distributed Systems,2022,33(10):2571. DOI:10.1109/TPDS.2022.3145836

GOPALAN P, HUANG C, SIMITCI H,et al. On the locality of codeword symbols[J]. IEEE Transactions on Information Theory,2012,58(11):6925. DOI:10.1109/TIT.2012.2208937

WANG Anyu, ZHANG Zhifang. Repair locality with multiple erasure tolerance[J]. IEEE Transactions on Information Theory,2014,60(11):6979. DOI:10.1109/TIT.2014.2351404

HAO Jie, SHUM K W, XIA Shutao,et al. On the maximal code length of optimal linear locally repairable codes[C]//IEEE International Symposium on Information Theory. Vail: IEEE,2018:1326. DOI:10.1109/ISIT.2018.8437466

JIN Lingfei, KAN Haibin, ZHANG Yu. Constructions of locally repairable codes with multiple recovering sets via rational function fields[J]. IEEE Transactions on Information Theory,2020,66(1):202. DOI:10.1109/TIT.2019.2946627

FU Qiang, LI Ruihu, YANG Sen. Optimal(r,δ)-locally repairable codes from simplex code and cap code[J]. IEEE Access,2020,8:215414. DOI:10.1109/ACCESS.2020.3040320

HAO Jie, SHUM K W, XIA Shutao,et al. Optimal locally repairable codes for parallel reading[J]. IEEE Access,2020,8:80447. DOI:10.1109/ACCESS.2020.2992188

CHAICHANAVONG P, SIEGEL P H. Relaxation bounds on the minimum pseudo-weight of linear block codes[C]//IEEE International Symposium on Information Theory. Adelaide: IEEE,2005:805. DOI:10.1109/ISIT.2005.1523448

WANG Anyu, ZHANG Zhifang, LIU Mulan. Achieving arbitrary locality and availability in binary codes[C]//IEEE International Symposium on Information Theory. Hong Kong: IEEE,2015:1866. DOI:10.1109/ISIT.2015.7282779

CAI Han, CHENG Minquan, FAN Cuiling,et al. Optimal locally repairable systematic codes based on packings[J]. IEEE Transactions on Communications,2019,67(1):39. DOI:10.1109/TCOMM.2018.2869800

SONG Wentu, CAI Kai, YUEN C,et al. On sequential locally repairable codes[J]. IEEE Transactions on Information Theory,2018,64(5):3513. DOI:10.1109/TIT.2017.2711611

KIM J H, SONG H Y. Alphabet-dependent bounds for locally repairable codes with joint information availability[J]. IEEE Communications Letters,2017,21(8):1687. DOI:10.1109/LCOMM.2017.2699968

TAN Pan, ZHOU Zhengchun, SIDORENKO V,et al. Two classes of optimal LRCs with information(r,t)-locality[J]. Designs, Codes and Cryptography,2020,88(9):1741. DOI:10.1007/s10623-020-00728-9

RAWAT A S, PAPAILIOPOULOS D S, DIMAKIS A G,et al. Locality andavailability in distributed storage[J]. IEEE Transactions on Information Theory,2016,62(8):681. DOI:10.1109/TIT.2016.2524510

ZHANG Yu, KAN Haibin. Locally repairable codes from combinatorial designs[J]. Science China Information Sciences,2020,63(2):174. DOI:10.1007/s11432-019-2649-5

BALAJI S B, KUMAR P V. Bounds on the rate and minimum distance of codes with availability[C]//IEEE International Symposium on Information Theory. Aachen: IEEE,2017:3155. DOI:10.1109/ISIT.2017.8007111

王新梅, 肖国镇. 纠错码—原理与方法[M]. 西安: 西安电子科技大学出版社,2001:52.WANG Xinmei, XIAO Guozhen. Error correcting codes—principle and method[M]. Xi′an: Xidian University Press,2001:52

BALAJI S B, PRASANTH K P, KUMAR P V. Binary codes with locality for multiple erasures having short block length[C]. IEEE International Symposium on Information Theory. Barcelona: IEEE,2016:655. DOI:10.1109/ISIT.2016.7541380

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. DOI:10.1109/TIT.2019.2934124

GOPARAJU S, CALDERBANK R. Binary cyclic codes that are locally repairable[C]//IEEE International Symposium on Information Theory. Honolulu: IEEE,2014:676. DOI:10.1109/ISIT.2014.6874918

HAO Jie, XIA Shutao, CHEN Bin. On the single-parity locally repairable codes with availability[C]//IEEE/CIC International Conference on Communications in China. Chengdu: IEEE,2016:7636892. DOI:10.1109/ICCChina.2016.7636892

HAO Jie, XIA Shutao. Constructions of optimal binary locally repairable codes with multiple repair groups[J]. IEEE Communications Letters,2016,20(6):1060. DOI:10.1109/LCOMM.2016.2539160

KIM J H, NAM M Y, SONG H Y. Binary locally repairable codes from complete multipartite graphs[C]//6th International Conference on Information and Communication Technology Convergence. Jeju Island: IEEE,2015:1093. DOI:10.1109/ICTC.2015.7354746

SHAHABINEJAD M, KHABBAZIAN M, ARDAKANI M. A class of binary locally repairable codes[J]. IEEE Transactions on Communications,2016,64(8):3182. DOI:10.1109/TCOMM.2016.2581163

SHAHABINEJAD M, KHABBAZIAN M, ARDAKANI M. On the average locality of locally repairable codes[J]. IEEE Transactions on Communications,2018,66(7):2773. DOI:10.1109/TCOMM.2017.2712186

TAMO I, BARG A. Bounds on locally recoverable codes with multiple recovering sets[C]//IEEE International Symposium on Information Theory. Honolulu: IEEE,2014:691. DOI:10.1109/ISIT.2014.6874921

Publication Statement

Journal Subscription

1 局部修复码

2 基于迭代矩阵构造BLRCs

3 性能分析

4 结论