基于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 是一個值得繼續研究的問題。