基于sunflower的局部修复码构造

（空军工程大学基础部，西安 710051）

0 引言

在分布式存储系统（Distributed Storage System，DSS）中，数据备份是解决节点错误所采用的最简单的方法，例如三重备份［1］。信息时代数据量的急剧增加，使备份的存储负荷越来越大，因此，人们寻找更好的方法来确保数据的可靠性，纠删码应运而生。纠删码可以在确保数据可靠性的同时，相较于备份大大减少存储负荷，因而得到了广泛应用［2-3］。

为了减小纠删码的修复代价，2012 年，Gopalan 等［4］提出了局部修复码（Locally Repairable Code，LRC）：对于一个码长为n，维数为k，距离为d的线性码C，记为C=[n，k，d]，若码C的每一位都可被其余不超过r位修复，则称这个码为局部度r的LRC。同时，Gopalan 等［4］提出了一个界，要求LRC 的最小距离满足：

这个界被称为Singleton 形界。然而Singleton 形界是不紧的，尤其在小域上，LRC的参数很难达到界。Cadambe等［5-6］提出了一个更适用的界，即C-M（Cadambe-Mazumdar）界。它将域的大小考虑在内，要求LRC的参数满足：

其中：k'=是码长为n、距离为d、q元码的最大维数。对于一个参数为[n，k，d，r]q的LRC，若k=k'，称其参数达到了C-M 界，且该LRC是最优的；若k=k'-1，称该LRC为拟最优的。

近些年关于最优LRC 的构造问题得到了大量研究。2017 年，文献［7］给出了LRC 的校验矩阵刻画和不相交局部修复组的概念，并应用（partial）t-spread 构造了二元域一类距离为6 以上的LRC。Silberstein 等［8］利用反链码构造了局部度为2 和3 的二元LRC，其中部分是最优的。文献［9］在2019 年应用不相交局部修复组构造了距离为6 的二元最优LRC。Fu等［10］给出了三类局部度为1，2，3 的二元LRC，其中大部分是最优的。文献［11］给出了一种二元域上利用奇距离LRC 构造偶距离LRC的方法，并构造了d=6，7，8的最优LRC。文献［12-14］分别研究了利用广义级联码、子域子码和代数曲线和曲面构造LRC。文献［15］证明了对于特定的r，l，w在任意域可构造参数为[(r+1)l，rl-w，w+2；r]q的LRC。文献［16］在2019 年应用sunflower 结构，构造了一类局部度为2 的最优LRC；同时，文献［16］给出了具有不相交局部修复组的最小距离不小于5 的LRC 的界：对于具有r+1 个不相交局部修复组的LRC，如果码的最小距离不小于5，则其维数k满足：

此外，Papailiopoulos 等［17］给出了LRC 的信息率的界，即：

可以看到，关于二元域上最优LRC 的研究已经比较充分，但在一般域上的研究相对较少。本文在文献［16］的启发下，拓展了其结果，利用sunflower 结构、射影几何和不相交局部修复组构造了两类一般域上的LRC。构造的两类LRC中许多LRC为最优的或拟最优的。

1 预备知识

记[n]={1，2，…，n}。若w=(w1，w2，…，wn)∈，w的Hamming 重量为wt(w)=|{i|wi≠0，i=1，2，…，n}|。记矩阵A和向量a的转置分别为AT和aT。

下面给出一些LRC、射影几何和sunflower的基础知识。

记q元域上的LRC 参数为C=[n，k，d；r]q。把C的校验矩阵分为两个部分：H=其中HL决定LRC的局部度r，给定HL的每一行是Hamming重量至多为r+1的向量，向量的非零位均为1。如果HL的某一列存在非零元，则称H的这一列被HL覆盖。如果HL的每一列均存在非零元，则称H的所有n个位被HL覆盖。被HL某一行覆盖的所有列称为这个行的支撑集。HL覆盖码的所有n个位来确保每个码字的局部度均为r，即整个码的局部度为r。HG为子矩阵，用来决定LRC的最小距离。

定义1假定(r+1)|n，如果C的对偶码中存在l=n/(r+1)个对偶码字，这l个对偶码字的重量均为r+1，且它们的支撑集是两两不相交的，则称C的校验矩阵H是由不相交的局部修复组构成的，称H中这l个对偶码字为局部度行。记由同一局部度行覆盖的r+1 列的集合为一个局部修复组。

定理1［18］定义χ(s，r；n，q)为射影空间PG(n，q)过s维空间的r维空间的个数。

其中，当s＜r时，[r，s]-=1；当s≥r时，[r，s]-=

注：这里可以得到射影空间PG(s+2，q)上过s维空间的s+1 维空间的个数χ(s，s+1；s+2，q)=[2，2]-/[1，1]-=q+1。

定义2定义Gq(m，s)为上所有s维子空间的集合，对于其子集S⊂Gq(m，s)，如果S中任意两个不同元素的交为同一个t维子空间Z，则称S为sunflower。其中t维子空间Z称为S的中心，记为Cen(S)。

目前，构造小距离的LRC（d=2，3，4）的结果很多，而构造距离不小于5的LRC 结果相对较少。其难点在于生成矩阵的最小码字重量或校验矩阵的列相关关系难以确定。sunflower 中子空间的基向量具有独立的线性关系，因此在构造LRC 时，校验矩阵的线性关系可通过子空间的关系统一分析，从而确定校验矩阵的线性相关关系及码的最小距离。将sunflower 中低维空间的基向量作为不相交局部修复组HG的列向量，可较容易地确定LRC 的最小距离，从而构造参数良好的LRC。

2 q为大于3的奇素数幂时LRC的构造

当m=s+1，t=s-1(s≥3) 时，Gq(s+1，s) 上的sunflowerS即为有限射影空间PG(s，q)中过s-2维空间的s-1维空间的集合。因此，S中元素个数即为q+1。基于以上结论，给出如下定理。

定理2当q是大于3 的奇素数幂时，可构造参数为[(r+1)(q+1)，rq-1，6；r](3 ≤r≤q-1)的LRC。

证明 证明部分将分两种情况：q是大于3 的素数和q=(2t+1)a，2t+1(t∈Z+)为素数，a≥2。

1）当q是大于3 的素数时，记S的中心，即Gq(s+1，s)上的s-1 维子空间为Cen(S)=注意到有q+1个s维子空间的交集为Cen(S)，就有q+1个非零向量i∈[q+1]使得{vi，∪gj，1 ≤j≤s-1}构成Vi的一组基，因此{vi，∪(gj-jvi)，1 ≤j≤s-1}也构成Vi的一组基。

每个s维子空间V的一组基对应一个修复组，可以构造如下矩阵H：

记C为具有上述校验矩阵H的q元线性码。由其校验阵结构可知C是参数为[(s+1)(q+1)，sq-1，d；s]的LRC。接下来证明当s≤q-1 时，该LRC 的距离为6，即H中任意5列线性无关且存在6列线性相关。

首先证明H中任意5 列线性无关。当给定的5 列分布在一个或者3个修复组时，易知这些列是线性无关的。当这5列分布在2 个修复组时，选取其中3 种复杂的情况进行讨论，其他简单情况省略。为便于叙述，假定其中3 列l1、l2、l3在第x个修复组，另外两列l4、l5在第y个修复组。

Case1 当l1、l2、l3和l4、l5中均不包括修复组的前2 列时，假定λ1，λ2，…，λ5∈Fq、1 ≤j1，j2，j3，j4，j5≤s-1，使得：

当λ4，λ5均不为0时，λ4j4+λ5j5≠0，即Cen(S)，等式（4）不成立。当λ4=λ5=0 时，等式（4）为=0，又由于均为子空间中的基向量，因此λ1=λ2=λ3=0，仅当λ1=λ2=λ3=λ4=λ5=0时，等式（4）成立，即l1、l2、l3、l4、l5线性无关。

Case2 当l1、l2、l3和l4、l5中均有一列为修复组第2 列时，假定λ1，λ2，…，λ5∈Fq、1 ≤j1，j2，j3，j4，j5≤s-1，使得：

与Case1相同，仅当l1、l2、l3的线性组合和l4、l5的线性组合都属于Cen(S) 时，等式（5）成立。在等式（5）中，若j5=q-1，∈Cen(S)且∈Cen(S)，等式成立，l1、l2、l3、l4、l5线性相关，因此需要s≠q。

特殊的，当j5=1 时，若q=2t(t≥1)，j5+1=0，∈Cen(S)不能保证l1、l2、l3、l4、l5线性无关，因此需要满足q≠2t(t≥1)。

Case3 当l4，l5中一列为修复组第一列，另一列为修复组最后一列时，假定λ1，λ2，…，λ5∈Fq、1 ≤j1，j2，j3，j4，j5≤s-1使得：

其他情况与上述三种情况类似，不再赘述。综上所述，当s≤q-1时，该LRC的距离不小于6。

接下来证明H中存在6 列线性相关。取l1、l2、l3和l4、l5、l6中均不包括修复组的前两列，假定λ1，λ2，…，λ6均不为0且1 ≤j1，j2，j3，j4，j5，j6≤s-1时，使得：

化简等式（7），可得：

当λ1j1+λ2j2+λ3j3=0 且λ4j4+λ5j5+λ6j6=0 时，均属于中心，即等式成立。由于：λ1j1+λ2j2+λ3j3=0，λ4j4+λ5j5+λ6j6=0，λ1+λ2+λ3=0，λ4+λ5+λ6=0，λ1，λ2，…，λ6有非零解，H中存在6列线性相关。

综上所述，当s≤q-1 时，dC=6。为便于叙述，将s替换为局部度r，即当q是大于3的素数时，校验矩阵为H的线性码对应参数是[(r+1)(q+1)，rq-1，6；r](3 ≤r≤q-1) 的LRC。

2）当q=(2t+1)a，2t+1(t∈Z+)为素数，a≥2 时，与q是大于3 的素数时相似，{vi，∪gj，1 ≤j≤s-1}构成Vi的一组基。记ξ为Fq的一个本原元，{vi，∪(gj-σvi)，σ=ξj-1，1 ≤j≤s-1}也构成Vi的一组基。构造结构类似于H的校验矩阵H'，区别在于当j＜(q+1)/2时，=gj-σvi，σ=ξj-1，1 ≤j≤s-1，i∈[q+1]；当j≥(q+1)/2 时，=gj-σvi，σ=ξj，1 ≤j≤s-1，i∈[q+1]。总结起来，σ≠ξ(q-1)/2=-1。校验矩阵H'中包含q+1 个修复组，每个修复组列数为s+1。接下来证明当s≤q-1 时，该码的距离为6。

Case4 当l1、l2、l3和l4、l5中均不包括修复组的前两列时，假定λ1，λ2，…，λ5∈Fq、1 ≤j1，j2，j3，j4，j5≤s-1使得：

Case5 当s=q时=gq-1-vi以及当σ=ξ(q-1)/2时，均会导致矩阵的距离小于6，因此需要s≤q-1和σ≠ξ(q-1)/2。

证明H'的距离与证明H的距离方法类似，不再赘述。下面给出一个例子。

例 当q=5 时，令G5(4，3) 上3 维子空间的中心为Cen(S)={λ1(0，1，0，0)T+λ2(1，0，1，0)T|λ1，λ2∈F5} ；取v1=(0，0，1，0)T，v2=(0，0，0，1)T，v3=(0，0，1，4)T，v4=(0，0，1，1)T，v5=(0，0，1，3)T，v6=(0，0，1，2)T。构造如下矩阵H：

易知该校验矩阵对应参数为[24，14，6；3]的LRC，且该LRC达到了C-M界，是最优的。

这里以参数为[24，14，6；3]的LRC与三重备份作对比。假设总数据量为M。应用参数为[24，14，6；3]的LRC 在编码时，将总数据量分为14 份，每个节点数据量为M。编码冗余需要10份，冗余数据量为M，编码的总数据量为M，一个节点丢失的修复I/O 开销为M。三重备份的编码冗余为2M，编码的总数据量为3M，一个节点丢失的修复I/O 开销为M。由此可见，LRC 相较于三重备份大大减少了存储冗余，同时又确保了数据的可靠性。

3 q=2t(t ≥2)时LRC的构造

在第2 章中，给出了一类参数为[(r+1)(q+1)，rq-1，6；r](3 ≤r≤q-1)的LRC。在证明其距离d=6 的Case2中，需要q≠2t(t≥1)。接下来，以第2章的矩阵构造方法为基础，给出q=2t(t≥2)时d=6的LRC。

定理 3当q=2t(t≥2) 时，可构造参数为[r(q+1)，rq-q-2，6；r-1]，2 ≤r≤q的LRC。

证明 构造结构类似于H的校验矩阵H″，其中0==gj-σvi，i∈[q+1]，σ∈ξj-1，1 ≤j≤s-1。显然H″中任意三列线性无关。

分别从两个修复组中取第 2、3 列，假定λ1，λ2，λ3，λ4∈Fq、1 ≤j1，j2≤s-1，使得：

由于λ1+λ2=0，λ1=-λ2，化简等式（9），可得λ1vx+λ2(g1-vx)=(λ1-λ2)vx+λ2g1=2λ1vx+λ2g1=λ2g1，即当λ1，λ2≠0 时，Cen(S)，同理可取λ3，λ4≠0，∈Cen(S)。因此，H″中存在4 列线性相关。此时构造的矩阵H″对应的局部修复码距离为4。删去H″中每个修复组的第2 列，将得到的矩阵记为H‴。当s≤q时，易证H″对应的LRC的距离为6，证明其距离为6的方法与第二章中证明类似。为便于叙述，将s替换为局部度r，这样就得到了参数为[r(q+1)，rq-q-2，6；r-1]，2 ≤r≤q的LRC。

4 构造的LRC的对比与分析

本文所构造的LRC均为新结果，对于Singleton形界式（1）和C-M 界式（2）而言，大部分均为最优或拟最优的。此外，通过固定码的最小距离和局部度，查阅文献中构造的与本文参数具有比较性的LRC 并与本文构造的两类码参数进行比较。结果见表1。

表1 本文结果与文献中应用不同方法构造的LRC比较Tab.1 Comparisons between results in this paper and LRC constructed by different methods in the literatures

由表1 可以发现，对于特定参数的LRC，本文构造LRC 的信息率均高于文献［12-15］利用不同方法构造LRC的信息率。此外，当q为奇数时，在文献［15］的表1 中构造了参数为[q2-2q，q2-3q-4，6；q-3]的一类LRC，而本文的LRC 参数为[q2-3q+2，q2-3q-1，6；q-3]，信息率高于文献［15］的结果。

通过对文献中已有参数的对比，在固定码的最小距离和局部度时，本文构造的LRC 的信息率均高于文献［12-15］的LRC 的信息率，改进了文献［12-15］中的结果。另外，对于定理3 中的结果，当r-1=3 时，可得到参数为[3(q+1)，2q-2，6；2]的LRC，这类LRC相较于式（3）是拟最优的。

5 结语

本文在现有研究的基础上，利用不相交局部修复组、sunflower 和射影几何等理论，构造了一般域上的两类LRC，参数 为 [(r+1)(q+1)，rq-1，6；r]和 [r(q+1)，rq-q-2，6；r-1]。其中大部分LRC 是最优或拟最优的。当域的大小增大时，这两类LRC 的信息率将越来越接近信息率的界。与文献［12-15］利用不同方法构造的LRC比较，本文构造的LRC 在具有相同最小距离和局部度时，提高了信息率。这两类码的构造对其他LRC 的构造具有借鉴意义。此外，如何利用sunflower 和射影几何构造其他参数良好的LRC 是一个值得继续研究的问题。