（空軍工程大學(xué)基礎(chǔ)部，西安 710051）

0 引言

在分布式存儲(chǔ)系統(tǒng)（Distributed Storage System，DSS）中，數(shù)據(jù)備份是解決節(jié)點(diǎn)錯(cuò)誤所采用的最簡(jiǎn)單的方法，例如三重備份［1］。信息時(shí)代數(shù)據(jù)量的急劇增加，使備份的存儲(chǔ)負(fù)荷越來越大，因此，人們尋找更好的方法來確保數(shù)據(jù)的可靠性，糾刪碼應(yīng)運(yùn)而生。糾刪碼可以在確保數(shù)據(jù)可靠性的同時(shí)，相較于備份大大減少存儲(chǔ)負(fù)荷，因而得到了廣泛應(yīng)用［2-3］。

為了減小糾刪碼的修復(fù)代價(jià)，2012 年，Gopalan 等［4］提出了局部修復(fù)碼（Locally Repairable Code，LRC）：對(duì)于一個(gè)碼長(zhǎng)為n，維數(shù)為k，距離為d的線性碼C，記為C=[n，k，d]，若碼C的每一位都可被其余不超過r位修復(fù)，則稱這個(gè)碼為局部度r的LRC。同時(shí)，Gopalan 等［4］提出了一個(gè)界，要求LRC 的最小距離滿足：

這個(gè)界被稱為Singleton 形界。然而Singleton 形界是不緊的，尤其在小域上，LRC的參數(shù)很難達(dá)到界。Cadambe等［5-6］提出了一個(gè)更適用的界，即C-M（Cadambe-Mazumdar）界。它將域的大小考慮在內(nèi)，要求LRC的參數(shù)滿足：

其中：k'=是碼長(zhǎng)為n、距離為d、q元碼的最大維數(shù)。對(duì)于一個(gè)參數(shù)為[n，k，d，r]q的LRC，若k=k'，稱其參數(shù)達(dá)到了C-M 界，且該LRC是最優(yōu)的；若k=k'-1，稱該LRC為擬最優(yōu)的。

近些年關(guān)于最優(yōu)LRC 的構(gòu)造問題得到了大量研究。2017 年，文獻(xiàn)［7］給出了LRC 的校驗(yàn)矩陣刻畫和不相交局部修復(fù)組的概念，并應(yīng)用（partial）t-spread 構(gòu)造了二元域一類距離為6 以上的LRC。Silberstein 等［8］利用反鏈碼構(gòu)造了局部度為2 和3 的二元LRC，其中部分是最優(yōu)的。文獻(xiàn)［9］在2019 年應(yīng)用不相交局部修復(fù)組構(gòu)造了距離為6 的二元最優(yōu)LRC。Fu等［10］給出了三類局部度為1，2，3 的二元LRC，其中大部分是最優(yōu)的。文獻(xiàn)［11］給出了一種二元域上利用奇距離LRC 構(gòu)造偶距離LRC的方法，并構(gòu)造了d=6，7，8的最優(yōu)LRC。文獻(xiàn)［12-14］分別研究了利用廣義級(jí)聯(lián)碼、子域子碼和代數(shù)曲線和曲面構(gòu)造LRC。文獻(xiàn)［15］證明了對(duì)于特定的r，l，w在任意域可構(gòu)造參數(shù)為[(r+1)l，rl-w，w+2；r]q的LRC。文獻(xiàn)［16］在2019 年應(yīng)用sunflower 結(jié)構(gòu)，構(gòu)造了一類局部度為2 的最優(yōu)LRC；同時(shí)，文獻(xiàn)［16］給出了具有不相交局部修復(fù)組的最小距離不小于5 的LRC 的界：對(duì)于具有r+1 個(gè)不相交局部修復(fù)組的LRC，如果碼的最小距離不小于5，則其維數(shù)k滿足：

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

可以看到，關(guān)于二元域上最優(yōu)LRC 的研究已經(jīng)比較充分，但在一般域上的研究相對(duì)較少。本文在文獻(xiàn)［16］的啟發(fā)下，拓展了其結(jié)果，利用sunflower 結(jié)構(gòu)、射影幾何和不相交局部修復(fù)組構(gòu)造了兩類一般域上的LRC。構(gòu)造的兩類LRC中許多LRC為最優(yōu)的或擬最優(yōu)的。

1 預(yù)備知識(shí)

記[n]={1，2，…，n}。若w=(w1，w2，…，wn)∈，w的Hamming 重量為wt(w)=|{i|wi≠0，i=1，2，…，n}|。記矩陣A和向量a的轉(zhuǎn)置分別為AT和aT。

下面給出一些LRC、射影幾何和sunflower的基礎(chǔ)知識(shí)。

記q元域上的LRC 參數(shù)為C=[n，k，d；r]q。把C的校驗(yàn)矩陣分為兩個(gè)部分：H=其中HL決定LRC的局部度r，給定HL的每一行是Hamming重量至多為r+1的向量，向量的非零位均為1。如果HL的某一列存在非零元，則稱H的這一列被HL覆蓋。如果HL的每一列均存在非零元，則稱H的所有n個(gè)位被HL覆蓋。被HL某一行覆蓋的所有列稱為這個(gè)行的支撐集。HL覆蓋碼的所有n個(gè)位來確保每個(gè)碼字的局部度均為r，即整個(gè)碼的局部度為r。HG為子矩陣，用來決定LRC的最小距離。

定義1假定(r+1)|n，如果C的對(duì)偶碼中存在l=n/(r+1)個(gè)對(duì)偶碼字，這l個(gè)對(duì)偶碼字的重量均為r+1，且它們的支撐集是兩兩不相交的，則稱C的校驗(yàn)矩陣H是由不相交的局部修復(fù)組構(gòu)成的，稱H中這l個(gè)對(duì)偶碼字為局部度行。記由同一局部度行覆蓋的r+1 列的集合為一個(gè)局部修復(fù)組。

定理1［18］定義χ(s，r；n，q)為射影空間PG(n，q)過s維空間的r維空間的個(gè)數(shù)。

其中，當(dāng)s＜r時(shí)，[r，s]-=1；當(dāng)s≥r時(shí)，[r，s]-=

注：這里可以得到射影空間PG(s+2，q)上過s維空間的s+1 維空間的個(gè)數(shù)χ(s，s+1；s+2，q)=[2，2]-/[1，1]-=q+1。

定義2定義Gq(m，s)為上所有s維子空間的集合，對(duì)于其子集S?Gq(m，s)，如果S中任意兩個(gè)不同元素的交為同一個(gè)t維子空間Z，則稱S為sunflower。其中t維子空間Z稱為S的中心，記為Cen(S)。

目前，構(gòu)造小距離的LRC（d=2，3，4）的結(jié)果很多，而構(gòu)造距離不小于5的LRC 結(jié)果相對(duì)較少。其難點(diǎn)在于生成矩陣的最小碼字重量或校驗(yàn)矩陣的列相關(guān)關(guān)系難以確定。sunflower 中子空間的基向量具有獨(dú)立的線性關(guān)系，因此在構(gòu)造LRC 時(shí)，校驗(yàn)矩陣的線性關(guān)系可通過子空間的關(guān)系統(tǒng)一分析，從而確定校驗(yàn)矩陣的線性相關(guān)關(guān)系及碼的最小距離。將sunflower 中低維空間的基向量作為不相交局部修復(fù)組HG的列向量，可較容易地確定LRC 的最小距離，從而構(gòu)造參數(shù)良好的LRC。

2 q為大于3的奇素?cái)?shù)冪時(shí)LRC的構(gòu)造

當(dāng)m=s+1，t=s-1(s≥3) 時(shí)，Gq(s+1，s) 上的sunflowerS即為有限射影空間PG(s，q)中過s-2維空間的s-1維空間的集合。因此，S中元素個(gè)數(shù)即為q+1?；谝陨辖Y(jié)論，給出如下定理。

定理2當(dāng)q是大于3 的奇素?cái)?shù)冪時(shí)，可構(gòu)造參數(shù)為[(r+1)(q+1)，rq-1，6；r](3 ≤r≤q-1)的LRC。

證明 證明部分將分兩種情況：q是大于3 的素?cái)?shù)和q=(2t+1)a，2t+1(t∈Z+)為素?cái)?shù)，a≥2。

1）當(dāng)q是大于3 的素?cái)?shù)時(shí)，記S的中心，即Gq(s+1，s)上的s-1 維子空間為Cen(S)=注意到有q+1個(gè)s維子空間的交集為Cen(S)，就有q+1個(gè)非零向量i∈[q+1]使得{vi，∪gj，1 ≤j≤s-1}構(gòu)成Vi的一組基，因此{(lán)vi，∪(gj-jvi)，1 ≤j≤s-1}也構(gòu)成Vi的一組基。

每個(gè)s維子空間V的一組基對(duì)應(yīng)一個(gè)修復(fù)組，可以構(gòu)造如下矩陣H：

記C為具有上述校驗(yàn)矩陣H的q元線性碼。由其校驗(yàn)陣結(jié)構(gòu)可知C是參數(shù)為[(s+1)(q+1)，sq-1，d；s]的LRC。接下來證明當(dāng)s≤q-1 時(shí)，該LRC 的距離為6，即H中任意5列線性無關(guān)且存在6列線性相關(guān)。

首先證明H中任意5 列線性無關(guān)。當(dāng)給定的5 列分布在一個(gè)或者3個(gè)修復(fù)組時(shí)，易知這些列是線性無關(guān)的。當(dāng)這5列分布在2 個(gè)修復(fù)組時(shí)，選取其中3 種復(fù)雜的情況進(jìn)行討論，其他簡(jiǎn)單情況省略。為便于敘述，假定其中3 列l(wèi)1、l2、l3在第x個(gè)修復(fù)組，另外兩列l(wèi)4、l5在第y個(gè)修復(fù)組。

Case1 當(dāng)l1、l2、l3和l4、l5中均不包括修復(fù)組的前2 列時(shí)，假定λ1，λ2，…，λ5∈Fq、1 ≤j1，j2，j3，j4，j5≤s-1，使得：

當(dāng)λ4，λ5均不為0時(shí)，λ4j4+λ5j5≠0，即Cen(S)，等式（4）不成立。當(dāng)λ4=λ5=0 時(shí)，等式（4）為=0，又由于均為子空間中的基向量，因此λ1=λ2=λ3=0，僅當(dāng)λ1=λ2=λ3=λ4=λ5=0時(shí)，等式（4）成立，即l1、l2、l3、l4、l5線性無關(guān)。

Case2 當(dāng)l1、l2、l3和l4、l5中均有一列為修復(fù)組第2 列時(shí)，假定λ1，λ2，…，λ5∈Fq、1 ≤j1，j2，j3，j4，j5≤s-1，使得：

與Case1相同，僅當(dāng)l1、l2、l3的線性組合和l4、l5的線性組合都屬于Cen(S) 時(shí)，等式（5）成立。在等式（5）中，若j5=q-1，∈Cen(S)且∈Cen(S)，等式成立，l1、l2、l3、l4、l5線性相關(guān)，因此需要s≠q。

特殊的，當(dāng)j5=1 時(shí)，若q=2t(t≥1)，j5+1=0，∈Cen(S)不能保證l1、l2、l3、l4、l5線性無關(guān)，因此需要滿足q≠2t(t≥1)。

Case3 當(dāng)l4，l5中一列為修復(fù)組第一列，另一列為修復(fù)組最后一列時(shí)，假定λ1，λ2，…，λ5∈Fq、1 ≤j1，j2，j3，j4，j5≤s-1使得：

其他情況與上述三種情況類似，不再贅述。綜上所述，當(dāng)s≤q-1時(shí)，該LRC的距離不小于6。

接下來證明H中存在6 列線性相關(guān)。取l1、l2、l3和l4、l5、l6中均不包括修復(fù)組的前兩列，假定λ1，λ2，…，λ6均不為0且1 ≤j1，j2，j3，j4，j5，j6≤s-1時(shí)，使得：

化簡(jiǎn)等式（7），可得：

當(dāng)λ1j1+λ2j2+λ3j3=0 且λ4j4+λ5j5+λ6j6=0 時(shí)，均屬于中心，即等式成立。由于：λ1j1+λ2j2+λ3j3=0，λ4j4+λ5j5+λ6j6=0，λ1+λ2+λ3=0，λ4+λ5+λ6=0，λ1，λ2，…，λ6有非零解，H中存在6列線性相關(guān)。

綜上所述，當(dāng)s≤q-1 時(shí)，dC=6。為便于敘述，將s替換為局部度r，即當(dāng)q是大于3的素?cái)?shù)時(shí)，校驗(yàn)矩陣為H的線性碼對(duì)應(yīng)參數(shù)是[(r+1)(q+1)，rq-1，6；r](3 ≤r≤q-1) 的LRC。

2）當(dāng)q=(2t+1)a，2t+1(t∈Z+)為素?cái)?shù)，a≥2 時(shí)，與q是大于3 的素?cái)?shù)時(shí)相似，{vi，∪gj，1 ≤j≤s-1}構(gòu)成Vi的一組基。記ξ為Fq的一個(gè)本原元，{vi，∪(gj-σvi)，σ=ξj-1，1 ≤j≤s-1}也構(gòu)成Vi的一組基。構(gòu)造結(jié)構(gòu)類似于H的校驗(yàn)矩陣H'，區(qū)別在于當(dāng)j＜(q+1)/2時(shí)，=gj-σvi，σ=ξj-1，1 ≤j≤s-1，i∈[q+1]；當(dāng)j≥(q+1)/2 時(shí)，=gj-σvi，σ=ξj，1 ≤j≤s-1，i∈[q+1]。總結(jié)起來，σ≠ξ(q-1)/2=-1。校驗(yàn)矩陣H'中包含q+1 個(gè)修復(fù)組，每個(gè)修復(fù)組列數(shù)為s+1。接下來證明當(dāng)s≤q-1 時(shí)，該碼的距離為6。

Case4 當(dāng)l1、l2、l3和l4、l5中均不包括修復(fù)組的前兩列時(shí)，假定λ1，λ2，…，λ5∈Fq、1 ≤j1，j2，j3，j4，j5≤s-1使得：

Case5 當(dāng)s=q時(shí)=gq-1-vi以及當(dāng)σ=ξ(q-1)/2時(shí)，均會(huì)導(dǎo)致矩陣的距離小于6，因此需要s≤q-1和σ≠ξ(q-1)/2。

證明H'的距離與證明H的距離方法類似，不再贅述。下面給出一個(gè)例子。

例 當(dāng)q=5 時(shí)，令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。構(gòu)造如下矩陣H：

易知該校驗(yàn)矩陣對(duì)應(yīng)參數(shù)為[24，14，6；3]的LRC，且該LRC達(dá)到了C-M界，是最優(yōu)的。

這里以參數(shù)為[24，14，6；3]的LRC與三重備份作對(duì)比。假設(shè)總數(shù)據(jù)量為M。應(yīng)用參數(shù)為[24，14，6；3]的LRC 在編碼時(shí)，將總數(shù)據(jù)量分為14 份，每個(gè)節(jié)點(diǎn)數(shù)據(jù)量為M。編碼冗余需要10份，冗余數(shù)據(jù)量為M，編碼的總數(shù)據(jù)量為M，一個(gè)節(jié)點(diǎn)丟失的修復(fù)I/O 開銷為M。三重備份的編碼冗余為2M，編碼的總數(shù)據(jù)量為3M，一個(gè)節(jié)點(diǎn)丟失的修復(fù)I/O 開銷為M。由此可見，LRC 相較于三重備份大大減少了存儲(chǔ)冗余，同時(shí)又確保了數(shù)據(jù)的可靠性。

3 q=2t(t ≥2)時(shí)LRC的構(gòu)造

在第2 章中，給出了一類參數(shù)為[(r+1)(q+1)，rq-1，6；r](3 ≤r≤q-1)的LRC。在證明其距離d=6 的Case2中，需要q≠2t(t≥1)。接下來，以第2章的矩陣構(gòu)造方法為基礎(chǔ)，給出q=2t(t≥2)時(shí)d=6的LRC。

定理 3當(dāng)q=2t(t≥2) 時(shí)，可構(gòu)造參數(shù)為[r(q+1)，rq-q-2，6；r-1]，2 ≤r≤q的LRC。

證明 構(gòu)造結(jié)構(gòu)類似于H的校驗(yàn)矩陣H″，其中0==gj-σvi，i∈[q+1]，σ∈ξj-1，1 ≤j≤s-1。顯然H″中任意三列線性無關(guān)。

分別從兩個(gè)修復(fù)組中取第 2、3 列，假定λ1，λ2，λ3，λ4∈Fq、1 ≤j1，j2≤s-1，使得：

由于λ1+λ2=0，λ1=-λ2，化簡(jiǎn)等式（9），可得λ1vx+λ2(g1-vx)=(λ1-λ2)vx+λ2g1=2λ1vx+λ2g1=λ2g1，即當(dāng)λ1，λ2≠0 時(shí)，Cen(S)，同理可取λ3，λ4≠0，∈Cen(S)。因此，H″中存在4 列線性相關(guān)。此時(shí)構(gòu)造的矩陣H″對(duì)應(yīng)的局部修復(fù)碼距離為4。刪去H″中每個(gè)修復(fù)組的第2 列，將得到的矩陣記為H?。當(dāng)s≤q時(shí)，易證H″對(duì)應(yīng)的LRC的距離為6，證明其距離為6的方法與第二章中證明類似。為便于敘述，將s替換為局部度r，這樣就得到了參數(shù)為[r(q+1)，rq-q-2，6；r-1]，2 ≤r≤q的LRC。

4 構(gòu)造的LRC的對(duì)比與分析

本文所構(gòu)造的LRC均為新結(jié)果，對(duì)于Singleton形界式（1）和C-M 界式（2）而言，大部分均為最優(yōu)或擬最優(yōu)的。此外，通過固定碼的最小距離和局部度，查閱文獻(xiàn)中構(gòu)造的與本文參數(shù)具有比較性的LRC 并與本文構(gòu)造的兩類碼參數(shù)進(jìn)行比較。結(jié)果見表1。

表1 本文結(jié)果與文獻(xiàn)中應(yīng)用不同方法構(gòu)造的LRC比較Tab.1 Comparisons between results in this paper and LRC constructed by different methods in the literatures

由表1 可以發(fā)現(xiàn)，對(duì)于特定參數(shù)的LRC，本文構(gòu)造LRC 的信息率均高于文獻(xiàn)［12-15］利用不同方法構(gòu)造LRC的信息率。此外，當(dāng)q為奇數(shù)時(shí)，在文獻(xiàn)［15］的表1 中構(gòu)造了參數(shù)為[q2-2q，q2-3q-4，6；q-3]的一類LRC，而本文的LRC 參數(shù)為[q2-3q+2，q2-3q-1，6；q-3]，信息率高于文獻(xiàn)［15］的結(jié)果。

通過對(duì)文獻(xiàn)中已有參數(shù)的對(duì)比，在固定碼的最小距離和局部度時(shí)，本文構(gòu)造的LRC 的信息率均高于文獻(xiàn)［12-15］的LRC 的信息率，改進(jìn)了文獻(xiàn)［12-15］中的結(jié)果。另外，對(duì)于定理3 中的結(jié)果，當(dāng)r-1=3 時(shí)，可得到參數(shù)為[3(q+1)，2q-2，6；2]的LRC，這類LRC相較于式（3）是擬最優(yōu)的。

5 結(jié)語

本文在現(xiàn)有研究的基礎(chǔ)上，利用不相交局部修復(fù)組、sunflower 和射影幾何等理論，構(gòu)造了一般域上的兩類LRC，參數(shù) 為 [(r+1)(q+1)，rq-1，6；r]和 [r(q+1)，rq-q-2，6；r-1]。其中大部分LRC 是最優(yōu)或擬最優(yōu)的。當(dāng)域的大小增大時(shí)，這兩類LRC 的信息率將越來越接近信息率的界。與文獻(xiàn)［12-15］利用不同方法構(gòu)造的LRC比較，本文構(gòu)造的LRC 在具有相同最小距離和局部度時(shí)，提高了信息率。這兩類碼的構(gòu)造對(duì)其他LRC 的構(gòu)造具有借鑒意義。此外，如何利用sunflower 和射影幾何構(gòu)造其他參數(shù)良好的LRC 是一個(gè)值得繼續(xù)研究的問題。