基于MOLS 的最优二元局部修复码构造*

王 娥 李静辉 杨佳蓉

（长安大学 西安 710064）

1 引言

随着信息时代的飞速发展，海量数据随之产生［1］。大型分布式存储系统往往采取冗余策略来保证数据可靠性［2］。最常见的冗余策略是复制，但是由于其高存储开销逐渐被纠删码取代［3］。纠删码在确保数据可靠性的同时减小了存储开销，但是其修复带宽开销过大。再生码平衡了存储开销和修复带宽开销之间的关系，但是再生码具有较高修复局部性和计算复杂度［4］。为了解决这一问题，Gopalan 等提出了局部修复码（Locally Repairable Codes，LRCs）的概念［5］。局部修复码减小了故障节点修复时的磁盘I/O 开销。对于一个[n，k，d]线性码来说，具有局部性r 的码字符号表示其最多可以从r个其他码字符号中恢复。码字符号具有局部性r 的[n，k，d] 线性码又被称为(n，k，r) 局部修复码［6］。除了局部性r，可用性t也是局部修复码的一个重要属性［7］。这一属性与热数据密切相关。具有(r，t)-局部性的局部修复码确保了热数据在多个修复组中的局部修复和并行读取［8］。

目前有许多学者对(n，k，r)局部修复码展开研究。Tamo 等［9］基于Reed-Solomon 编码块构造了一种最小距离最优的局部修复码，但是该码不能在较小的有限域上实现，其编码和修复复杂度较高。Wang 等［10］基于球面填充方法推导出(n，k，r)二元局部修复码的维度k的上界，并将边界和码的构造扩展到了q元域上，但是构造的码既没有实现最小距离最优也没有实现码率最优。Chen 等［11］利用常环MDS 码构造了七类具有新参数的最优(r，δ)-局部修复码，但是该码的参数选择不够灵活。Cai等［12］提出了一种新的最小距离界，并且给出了满足该界的局部修复码的显示结构，但是构造的码的码率较低。Balaji 等［13］推导出(n，k，r)局部修复码的码率上界，并且基于校验矩阵构造了达到该上界的局部修复码，但是构造的码不是最优的局部修复码。

为了解决上述问题，本文基于相互正交的拉丁方（Mutually Orthogonal Latin Squares，MOLS）提出一种信息符号具有(r，t)-局部性的二元局部修复码（Binary Locally Repairable Codes，BLRCs）。其编码和修复过程均在二元域上进行，有效降低了运算复杂度。除此之外，本文构造的BLRCs是最小距离最优的二元局部修复码。当可用性t=2 时，该BLRCs实现了码率最优。

2 基础知识

2.1 局部修复码

定义1［14］若φ1(i)局部修复码的一个码字符号可以被大小至多为r 的t 个不相交的修复集修复，则称该码字符号具有(r，t)-局部性。具有(r，t)-局部性的局部修复码需要满足：

1）φ1(i)，φ2(i)，…，φt(i)⊂[n]{i}；

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

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

其中φj(i)(j∈[t])为ci的修复集。

定义2［15］当(n，k，r，t)i局部修复码的所有信息符号都具有(n，k，r，t)i-局部性时，该局部修复码被称为(n，k，r，t)i-LRCs。若(n，k，r，t)i-LRCs 的每个信息符号的修复集都只包含一个校验符号，则该局部修复码被称为单校验(n，k，r，t)i-LRCs。

定理1［14］单校验(n，k，r，t)i-LRCs的最小距离满足：

定理2［16］Prakash 等人推导出可用性为2 的局部修复码的码率满足：

2.2 区组设计

定义3［17］设X={x1，x2，…，xv} 为一v元集，B1，B2，…，Bb是X的b个不同的k元子集。若满足条件：

1）对∀x∈X，x恰好出现在B1，B2，…，Bb的r个中；

2）X的每个2 元子集都恰好包含在子集组B1，B2，…，Bb的λ个中；

3）0 ＜λ，k＜v-1。

则称B1，B2，…，Bb为一(b，v，r，k，λ)-设计。

定义4［17］设X，Bi(i=1，2，…，b)如定义3，则X关于Bi的关联矩阵A=(aij)b×v(i=1，2，…b;j=1，2，…v)。其中：

2.3 MOLS

定义5［18］设A=(aij)是一个m×s矩阵，若A的任一行是集[1，n]的一个s-排列，任一列是集[1，n]的一个m-排列，则称A是一个m×s的拉丁矩(m≤n，s≤n)。若m=s=n，则称A为一个n阶拉丁方（Latin Square）。

定义6［18］设A=(aij)，B=(bij)是两个不同的n阶拉丁方，如果n2个有序对都是不同的，则称拉丁方A与B正交。设A1，A2，…As是一组n阶拉丁方，n≥s，s≥2，若只要i≠j，Ai与Aj就正交，则称A1，A2，…As是相互正交的拉丁方（Mutually Orthogonal Latin Squares，MOLS）。

定理3［18］设n=pα，其中p是素数，α是正整数，则一定存在由n-1 个n阶拉丁方组成的完备正交组。

定理4［18］令n≥2 为一整数。如果存在n-1 个n阶MOLS，则存在(b=n2+n，v=n2，k=n，r=n+1，λ=1)-设计。

3 基于MOLS的局部修复码构造

本节基于MOLS 提出一种信息符号具有(r，t) -局部性的(n，k，r，t)i-BLRCs 的构造算法。具体步骤如下：

1）令q=pα(p∈P，α∈N*)，给定A1，A2，…Aq-1表示q-1个q阶MOLS。

2）令矩阵：

3）由以上定义的q+1 个矩阵Ao(o=-1，0，…q-1) 构造(b=q2+q，v=q2，r'=q+1，k'=q，λ=1) -设计。具体的，给定q2元集X=xj(j=1，2，…，q2)，由Ao确定q2+q个区组Ao(z)(z=1，2，…q) 。令Ao中第m行第s列的元素为Ao(m，s) ，若Ao(m，s)=z，则x(m-1)q+s∈Ao(z)。

4）将区组Ao(z) 标记为区组Bi(i=1，2，…，q2+q)。

5）将区组Bi(i=1，2，…，q2+q)与矩阵的行关联，集合xj(j=1，2，…，q2)与矩阵的列关联，得到X关于Bi的关联矩阵A=(aij)(q2+q)×q2(i=1，2，…q2+q，j=1，2，…，q2)，其中，

6）在矩阵A前面级联一个q2+q阶单位矩阵I得到统一的生成矩阵G=(I|A)(q2+q)×(2q2+q)。则由生成矩阵G定义的二进制线性码C是信息符号具有(q+1，q) -局部性的(n=2q2+q，k=q2+q，r=q+1，t=q)i-BLRCs。

例：以下给出(n=10，k=6，r=3，t=2)i-BLRCs的构造过程。

令q=21=2，

令：

给定X={x1，x2，x3，x4}，则区组：

A-1(1)={x1，x2}，A(-1)(2)={x3，x4}，A0(1)={x1，x3}，A0(2)={x2，x4}，A1(1)={x1，x4}，A1(2)={x2，x3}。

则区组：

B1={x1，x2}，B2={x3，x4}，B3={x1，x3}，

B4={x2，x4}，B5={x1，x4}，B6={x2，x3}。

则X关于Bi的关联矩阵：

则由生成矩阵G=(I|A)12×21构造的码是单校验(n=10，k=6，r=3，t=2)i-BLRCs，最小距离d=t+1=3，码率R=k/n=0.6 。若信息节点c1故障，有c1=c3+c5+c7=c4+c6+c8。因此，c1的修复集为φ1(1)={3，5，7}，φ2(1)={4，6，8}。同理，可以得到其他码字符号的修复集。

4 性能分析

4.1 最小距离

本节讨论基于MOLS 构造的BLRCs 的最小距离，将它与最优最小距离边界进行比较。

将基于MOLS 构造的信息符号具有(r=q+1，t=q) -局部性的单校验(n=2q2+q，k=q2+q，r=q+1，t=q)i-BLRCs 的参数n=2q2+q，k=q2+q，r=q+1，t=q代入式（1）可得：

满足式（1）上界，即基于MOLS 构造的单校验(n=2q2+q，k=q2+q，r=q+1，t=q)i-BLRCs 是最小距离最优的二元局部修复码，且最小距离d=t+1。

4.2 码率

本节讨论基于MOLS 构造的BLRCs 的码率，将它与最优码率边界进行比较。

基于MOLS 构造的单校验(n=2q2+q，k=q2+q，r=q+1，t=q)i-BLRCs的码率

当t=2 时，基于MOLS 构造的BLRCs 的码率R=r/(r+2)满足式（2）上界。即当可用性t=2 时，基于MOLS 构造的BLRCs 是码率最优的二元局部修复码。

4.3 与其他码的比较

下面比较基于MOLS 构造的BLRCs 与基于阵列LDPC 码构造的BLRCs［19］，直积码［20］和基于迭代矩阵构造的BLRCs［21］的码长n和码率R。表1 列出了这四种BLRCs的相关参数。为方便比较，将这些码的码长n，信息位k，码率R，均用局部性r和可用性t表示。

表1 四种BLRCs相关参数对照

码长n的比较：

由表1 可知，当r≥t≥2 时，基于阵列LDPC 码构造的BLRCs的码长：

当r≥2，t≥2 时，直积码的码长：

当r＞3，t=2 时，基于迭代矩阵构造的BLRCs的码长：

即相同r，t下，当r≥t≥2 时，基于阵列LDPC码构造的BLRCs 的码长始终大于基于MOLS 构造的BLRCs 的码长。当r≥2，t≥2 时，直积码的码长始终大于基于MOLS 构造的BLRCs 的码长。当r＞3，t=2 时，基于迭代矩阵构造的BLRCs 的码长始终大于基于MOLS构造的BLRCs的码长。

为了更直观地表示表1中四种BLRCs的码长n随局部性r的变化趋势，图1 给出了可用性t=2时，码长n随局部性r的变化关系曲线，限于图幅大小，局部性r取值为3 ≤r≤11。

图1 t=2 时，码长n 的对比分析图

由图1 可知，可用性t=2 时，四种BLRCs 的码长均随局部性r的增大而增大，且基于MOLS 构造的BLRCs 的码长始终小于基于阵列LDPC 码构造的BLRCs，直积码和基于迭代矩阵构造的BLRCs的码长。证明基于MOLS构造的BLRCs的码长更优。

码率R的比较：

由表1 可知，当r≥2，t≥2 时，基于阵列LDPC码构造的BLRCs的码率：

当r≥2，t≥2 时，直积码的码率：

当r≥2，t=2 时，基于迭代矩阵构造的BLRCs的码率：

即相同r，t下，当r≥2，t≥2 时，基于阵列LDPC 码构造的BLRCs和直积码的码率始终小于基于MOLS 构造的BLRCs 的码率。当r≥2，t=2 时，基于迭代矩阵构造的BLRCs 的码率小于基于MOLS构造的BLRCs的码率。

为了更直观地表示表1 中四种BLRCs 的码率R随局部性r的变化趋势，图2 给出了可用性t=2时，码率R随局部性r的变化关系曲线，限于图幅大小，局部性r取值为2 ≤r≤10。

图2 t=2 时，码率R 的对比分析图

由图2 可知，可用性t=2 时，四种BLRCs 的码率均随局部性r的增大而增大，且r越大，码率R的变化趋势越缓慢。另外，基于MOLS 构造的BLRCs 的码率始终大于基于阵列LDPC 码构造的BLRCs，直积码和基于迭代矩阵构造的BLRCs 的码率，且达到了Prakash 等提出的最优码率界。证明t=2 时，基于MOLS 构造的BLRCs 是码率最优的二元局部修复码。

5 结语

本文基于MOLS 提出一种信息符号具有(r，t)-局部性的二元局部修复码的构造算法。当存储节点故障时，构造的BLRCs能通过t个大小至多为r的修复集进行修复。理论分析表明，该BLRCs 的最小距离满足最优最小距离界，是最优的二元局部修复码。仿真发现，基于MOLS 构造的BLRCs 的码率高于基于阵列LDPC 码构造的BLRCs，基于迭代矩阵构造的BLRCs和直积码的码率，且可用性t=2 时，基于MOLS构造的BLRCs的码率达到了prakash 等提出的最优码率界，是码率最优的二元局部修复码。除此之外，本文提出的BLRCs能通过简单地异或运算实现数据的编码，修复和并行读取，因此对于大型分布式存储系统是非常理想的。