低維四元局部修復(fù)碼的構(gòu)造

展秀珍， 李瑞虎， 付 強(qiáng)， 李滬生， 呂京杰

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

在分布式存儲(chǔ)系統(tǒng)中，為了實(shí)現(xiàn)數(shù)據(jù)的可靠存儲(chǔ)與恢復(fù)，三重備份是簡(jiǎn)單易行的方案[1]。由于三重備份的存儲(chǔ)效率低且存儲(chǔ)代價(jià)過大，因此人們提出了存儲(chǔ)負(fù)荷更低的糾刪碼方案[2-3]。局部修復(fù)碼是一種新型糾刪碼，其碼字的任一符號(hào)位發(fā)生故障時(shí)，都可通過訪問其他固定數(shù)目的符號(hào)位恢復(fù)信息。2012年，Gopalan等人提出局部修復(fù)碼(Locally Repairable Code， LRC)的概念[4]：若C=[n,k,d]q是碼長(zhǎng)為n，維數(shù)為k，最小距離為d的q元線性碼，碼字c=(c1,…,cn)∈C的第i(1≤i≤n)位ci都能通過其他至多r位恢復(fù)，則稱C是局部度為r的局部修復(fù)碼，并記為C=[n,k,d;r]q。文獻(xiàn)[4]還給出Singleton-Like(S-L)界：

(1)

當(dāng)?shù)仁匠闪r(shí)，稱碼達(dá)到了S-L界。特別地，當(dāng)k=r時(shí)，S-L界退化為經(jīng)典的Singleton界。為了更加精確地描述LRC 4個(gè)參數(shù)之間的限制關(guān)系，2013年Cadambe和Mazumdar提出一個(gè)考慮域的大小q的界，即Cadambe-Mazumdar(C-M)界[5]:

(2)

若C=[n,k,d;r]q達(dá)到S-L界或C-M界，或者不存在參數(shù)為[n,k,d;r-1]q的局部修復(fù)碼，則稱C是局部度最優(yōu)的(r-最優(yōu)的)。

在工程應(yīng)用中，小域上LRC編碼和解碼復(fù)雜度低，從而更具有實(shí)用性[6]。Gopalan等人提出LRC的概念之后，人們構(gòu)造了在小域上達(dá)到S-L界[7-10]或C-M界[11-12]的LRC。在四元域上，人們得到一些局部度最優(yōu)LRC的結(jié)果：文獻(xiàn)[13]構(gòu)造了四元LRC[4i+3,3i+1,3;3]4和[4i+4,3i+2,3;3]4(i≥1)。與文獻(xiàn)[13]相比，Ernvall等人還構(gòu)造了參數(shù)為[4i+4,3i+1,3;4]4(i≥1)的四元LRC，這三類LRC是局部度最優(yōu)或擬最優(yōu)的[14]。Barg等人利用代數(shù)曲線和代數(shù)曲面構(gòu)造了參數(shù)為[n,k,d;r]q=[18,11,3;2]4的LRC[15]。Fu等利用縮短q元漢明碼與(q2+1)-cap構(gòu)造了d=3,4的四元LRC[10]，其參數(shù)為[17-s,13-s,4;11-s]4(0≤s≤5)，[12-j,8-j,4;6-3i-t]4(j=4i+t,0≤t≤3,0≤i≤1)，[21-s,18-s,3;15-s]4(1≤s≤9)和[12-j,9-j,3;6-2i-t]4(1≤j=3i+t≤4,0≤t,i≤2)。文獻(xiàn)[16]利用有限域上的自同構(gòu)群構(gòu)造一般域上的LRC，可得到參數(shù)為[2,1,2;1]4，[4,1,4;1]4，[4,2,2;1]4，[4,3,2;3]4，[3,2,2;2]4和[5,4,2;4]4的四元LRC。

四元域是二元域的二次擴(kuò)域，四元碼能夠轉(zhuǎn)化為二元碼。當(dāng)給定碼的碼長(zhǎng)和維數(shù)時(shí)，四元碼的最小距離往往比二元碼的最小距離大，即四元碼的檢錯(cuò)和糾錯(cuò)能力更好，四元距離最優(yōu)LRC有較好的應(yīng)用價(jià)值。由Grassl的碼表[17]和文獻(xiàn)[18～20]可得到距離最優(yōu)四元碼，但給定碼長(zhǎng)和維數(shù)時(shí)，四元距離最優(yōu)碼往往有很多，它們的局部度也有差別[19]，基于此我們構(gòu)造局部度較小的四元LRC。設(shè)碼的維數(shù)2≤k≤4，由給定維數(shù)的四元Simplex碼、MacDonald碼以及少量距離最優(yōu)碼的生成矩陣，利用擴(kuò)展、刪除與并置等組合方法，我們?cè)O(shè)法構(gòu)造出任意碼長(zhǎng)n≥k+1且局部度盡可能小的LRC，并利用S-L界及C-M界判斷其局部度的最優(yōu)性。

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

線性碼的局部度可以由生成陣確定，具體如下：

引理1[4]設(shè)線性碼C=[n,k,d]q的生成陣為Gk,n=(g1,g2,…,gn)，gi(1≤i≤n)是k維列向量。對(duì)任意i∈[n]，若存在集合Ai?[n]{i}使得gi被至多r個(gè)gj(j∈Ai)線性表出，則C的局部度為r。

線性碼的參數(shù)n,k,d相互制約，下面介紹一種重要的碼界——Griesmer界。

在四元域上，記Sk為k維Simplex碼的生成矩陣，Mk為k維MacDonald碼的生成矩陣。設(shè)k∈Z+，k≥2，則k維首一列向量的個(gè)數(shù)(即Sk的列數(shù))為nk=(4k-1)/3，顯然nk=4nk-1+1。下面介紹Sk與Mk的遞歸構(gòu)造。

顯然，Sk生成參數(shù)為[(4k-1)/3,k,4k-1;2]4的距離最優(yōu)LRC，Mk生成距離最優(yōu)LRC[4k-1,k,3·4k-2;2]4。

2 低維四元LRC的構(gòu)造

由文獻(xiàn)[20]可知，對(duì)于四元線性碼[n,k,d]4，當(dāng)k=2且給定最小距離d時(shí)，存在達(dá)到Griesmer界的[n,2,d]4碼。當(dāng)k=3且d=7,8時(shí)，有n=g+1；對(duì)于其他的d存在達(dá)到Griesmer界的[n,3,d]4碼。k=4時(shí)，若d∈{3,4,7,8}∪[13,16]∪[23,32]∪[37,44]∪[77,80]，則n=g+1；對(duì)于其他的d存在達(dá)到Griesmer界的[n,4,d]4碼。因此本節(jié)分3小節(jié)討論四元距離最優(yōu)LRC[n,k,d;r]4(2≤k≤4)的構(gòu)造。

約定：四元距離最優(yōu)碼[n,k,d]4簡(jiǎn)記為[n,k,d]，四元距離最優(yōu)LRC[n,k,d;r]4簡(jiǎn)記為[n,k,d;r]。

2.1 [n,2,d;r]距離最優(yōu)LRC的構(gòu)造

根據(jù)引理1，構(gòu)造二維四元距離最優(yōu)碼的生成矩陣，并分析其列向量間的線性關(guān)系確定其局部度，其中生成矩陣中的列向量均為首一向量。

引理3存在如下參數(shù)[n,2,d;r]的距離最優(yōu)LRC：

1)當(dāng)3≤n≤9時(shí)，存在[n,2,d;2]距離最優(yōu)LRC；特別地，若n=6,8，還存在[n,2,d;1]距離最優(yōu)LRC；

2)當(dāng)n=5l+i，l≥2，0≤i≤4時(shí)，存在[n,2,d;1]距離最優(yōu)LRC。

證明：

2)當(dāng)n=5l，l≥2時(shí)，令G2,5l=(lG2,5)，G2,5l生成[5l,2,4l;1]碼。當(dāng)n=5l+i≥11，1≤i≤4且l≥2時(shí)，由G2,5l+i=(G2,5(l-1)|G2,5+i)可得[5l+i,2,4l+i-1;1]碼。

綜上可知引理3成立。

以上構(gòu)造得到所有[n,2,d]距離最優(yōu)碼，其中[3,2,2;2]，[4,2,3;2]，[5,2,4;2]，[6,2,4;1]，[8,2,6;1]，[10,2,8;1]碼達(dá)到S-L界；[7,2,5;2]和[9,2,7;2]碼達(dá)不到S-L界或C-M界，但不難驗(yàn)證[7,2,5;1]和[9,2,7;1]不存在，故這兩個(gè)LRC仍是r-最優(yōu)的；其余LRC的局部度為r=1，已達(dá)到局部度最優(yōu)。

2.2 [n,3,d;r]距離最優(yōu)LRC的構(gòu)造

與2.1節(jié)類似，構(gòu)造三維四元距離最優(yōu)碼的生成矩陣，并分析其列向量間的線性關(guān)系確定局部度。

引理4存在如下參數(shù)[n,3,d;r]的距離最優(yōu)LRC。

1)當(dāng)4≤n≤6時(shí)，存在[n,3,d;3]距離最優(yōu)LRC；當(dāng)7≤n≤41(n≠32,33)及n=52,53時(shí)，存在[n,3,d;2]距離最優(yōu)LRC；特別地，當(dāng)n=10,12,28,30,32,33,38,40時(shí)，還存在[n,3,d;1]距離最優(yōu)LRC；

2)當(dāng)n≥42(n≠52,53)時(shí)，存在[n,3,d;1]距離最優(yōu)LRC。

證明：

1)構(gòu)造如下4個(gè)生成矩陣。

(α1,α2,…,α21)。

以上4個(gè)矩陣生成[4,3,2;3]，[9,3,6;2]，[16,3,12;2]和[21,3,16;2]碼。令α=(1,2,3)T，β=(1,3,2)T，作G3,5=(G3,4|α)，G3,6=(G3,5|β)，由G3,5和G3,6得[5,3,3;3]，[6,3,4;3]碼。由G3,9的子矩陣G3,i=(g1,g2,…,gi)(7≤i≤8)可得[7,3,4;2]和[8,3,5;2]碼。由G3,10=(G3,9|γ)，γ∈G3,9可得[10,3,6;2]碼。當(dāng)1≤j≤5時(shí)，刪除G3,16的后j列得到G3,16-j，G3,16-j生成[16-j,3,12-j;2]碼。當(dāng)1≤j≤4時(shí)，刪除G3,21的后j列得到G3,21-j，由G3,21-j可得[21-j,3,16-j;2]LRC。

當(dāng)22≤n≤24時(shí)，構(gòu)造G3,n=(S3|e1,…,en-21)得到[n,3,d;2]距離最優(yōu)LRC；當(dāng)25≤n≤30，33≤n≤41時(shí)，構(gòu)造G3,n=(S3|G3,n-21)，G3,n生成[n,3,d;2]距離最優(yōu)LRC；n=31時(shí)，構(gòu)造G3,31=(M3|G3,15)，G3,31生成[31,3,23;2]碼。

特別地，當(dāng)i∈[5,6]∪[14,16]∪[19,21]時(shí)，令A(yù)3,2i=(G3,i|G3,i)，A3,2i生成[2i,3,2d;1]距離最優(yōu)LRC。由G3,33=(A3,32|γ)，γ∈A3,32可得[33,2,24;1]LRC。

2)當(dāng)43≤n≤63且n≠52,53時(shí)，構(gòu)造G3,n=(S3|G3,n-21)，G3,n生成[n,3,d;1]距離最優(yōu)LRC。構(gòu)造G3,52=(S3|G3,31)，G3,53=(S3|A3,32)分別生成[52,3,39;2]和[53,3,40;2]LRC。

當(dāng)n=21l，l≥3時(shí)，令G3,21l=(lG3,21)，G3,21l生成[21l,3,16l;1]碼。當(dāng)n=21l+i，1≤i≤20且l≥3時(shí)，令G3,21l+i=(G3,21(l-1)|G3,21+i)，G3,21l+i生成r=1的[21l+i,3,d]距離最優(yōu)碼。

綜上可知引理4成立。

以上構(gòu)造給出所有[n,3,d]距離最優(yōu)碼，當(dāng)r=1時(shí)，局部度已達(dá)到最優(yōu)。當(dāng)r≥2時(shí)，[4,3,2;3]，[5,3,3;3]，[6,3,4;3]，[7,3,4;2]，[8,3,5;2]以及[9,3,6;2]LRC達(dá)到S-L界；[23,3,16;2]，[52,3,39;2]，[53,3,40;2]LRC達(dá)不到S-L界或C-M界，其余的LRC能達(dá)到C-M界。

2.3 [n,4,d;r]距離最優(yōu)LRC的構(gòu)造

下面分5≤n≤85，86≤n1≤170，171≤n2≤255和n3≥255四種情形討論四維LRC的構(gòu)造。

2.3.1 5≤n≤85時(shí)距離最優(yōu)LRC的構(gòu)造

由文獻(xiàn)[20]知，當(dāng)k=4時(shí)，若d∈{3,4,7,8}∪[13,16]∪[23,32]∪[37,44]∪[77,80]，則n=g+1，對(duì)于其他的d存在達(dá)到Griesmer界的[n,4,d]碼。便于描述，當(dāng)5≤n≤85時(shí)，記達(dá)到Griesmer界的[n,4,d]距離最優(yōu)碼的碼長(zhǎng)構(gòu)成集合N1,0，且N1,0=[9,10]∪[14,17]∪[25,32]∪[46,50]∪[61,85]。當(dāng)n∈[5,85]時(shí)，若[n,4,d]距離最優(yōu)碼達(dá)不到Griesmer界，但[g+85,4,d]距離最優(yōu)碼達(dá)到Griesmer界，則記碼長(zhǎng)n構(gòu)成集合N1,1=[7,8]∪[12,13]∪[33,44]∪[52,60]；若[g+85,4,d]距離最優(yōu)碼仍達(dá)不到Griesmer界，則記碼長(zhǎng)n構(gòu)成集合N1,2=[19,24]。

此外，當(dāng)n=6,11,18,29,32,50,65,71,76,81時(shí)，雖然[n,4,d]距離最優(yōu)碼達(dá)不到Griesmer界，但存在[n-1,4,d]距離最優(yōu)碼達(dá)到Griesmer界；當(dāng)n=51,66時(shí)，存在[n-2,4,d]距離最優(yōu)碼達(dá)到Griesmer界；當(dāng)n=45時(shí)，不存在[n-1,4,d]或[n-2,4,d]距離最優(yōu)碼達(dá)到Griesmer界。

定理5當(dāng)5≤n≤85時(shí)，存在如下參數(shù)[n,4,d;r]的距離最優(yōu)LRC：

1)存在[5,4,2;4]距離最優(yōu)LRC；當(dāng)7≤n≤18及n=33時(shí)，存在[n,4,d;3]距離最優(yōu)LRC。

2)當(dāng)n=6及19≤n≤85(n≠33,34)時(shí)，存在[n,4,d;2]距離最優(yōu)LRC；特別地，當(dāng)n=32,34,35,51,56時(shí)，還存在[n,4,d;1]距離最優(yōu)LRC。

證明：

構(gòu)造以下12個(gè)矩陣G4,n，其中G4,17由文獻(xiàn)[10]給出，G4,85的6個(gè)子塊Bi為4×5矩陣。

G4,85=(B1，B2,…，B6|G4,55)=

1)G4,5和G4,10生成[5,4,2;4]，[10,4,6;3]碼。當(dāng)1≤i≤3時(shí)，刪除G4,10的后i列得到[10-i,4,6-i;3]距離最優(yōu)LRC。記G4,n=(β1,…,βn)，n=17-j，當(dāng)11≤n≤17時(shí)，G4,n生成[n,4,12-j;3]。由γ∈G4,17，G4,18=(G4,17|γ)可得[18,4,12;3]。當(dāng)n=33,34時(shí)，由G4,n=(G4,17|G4,n-17)可得[33,4,23;3]與[34,4,24;1]碼。

2)G4,6生成[6,4,2;2]碼。當(dāng)n=23,28,39,44,49時(shí)，G4,n生成[23,4,16;2]，[28,4,20;2]，[39,4,28;2]，[44,4,32;2]，[49,4,36;2]，刪除G4,n的后i(1≤i≤4)列得到[n-i,4,d;2]距離最優(yōu)LRC。G4,31生成[31,4,22;2]碼，刪除G4,31的后2列得到[n-i,4,d;2]距離最優(yōu)LRC。當(dāng)n=31,49時(shí)，由G4,n+1=(G4,n|γ)，γ∈G4,n可得[n+1,4,d;2]距離最優(yōu)LRC。

G4,85生成[85,4,64;2]碼，刪除G4,85的子矩陣(B1,B2,…,Bi)，1≤i≤6可得[85-5i,4,64-4i;2]距離最優(yōu)LRC。當(dāng)n=55,70,75,80,85，1≤i≤4時(shí)，刪除G4,n的后i列得到的矩陣生成[n-i,4,d;2]距離最優(yōu)LRC。

考察M4及其子矩陣，M4生成[64,4,48;2]碼, 當(dāng)1≤i≤8時(shí)，刪除M4的后i列得到[64-i,4,48-i;2]距離最優(yōu)LRC。

綜上可知定理5成立。

2.3.2 86≤n1≤170時(shí)距離最優(yōu)LRC的構(gòu)造

當(dāng)86≤n1≤170時(shí)，由距離最優(yōu)LRCC1=[n1,4,d1;r1]和C2=[n2,4,d2;r2]的生成矩陣構(gòu)造距離最優(yōu)LRCC=[n1+n2,4,d1+d2;r]的生成矩陣，其中r≤max {r1,r2}，通過刪除C的生成矩陣的子矩陣(或列向量)得到新的距離最優(yōu)LRC的生成矩陣。

定理6記n1=n+85(n∈[1,85])，當(dāng)86≤n1<170時(shí)，存在[n1,4,d;2]距離最優(yōu)LRC；特別地，當(dāng)n1=88,98,124,126,128,129,130,140,150,151,156,158,160,161,166,168,170時(shí)，還存在[n1,4,d;1]距離最優(yōu)LRC。

證明：

1)當(dāng)n∈N1,0,n∈N1,2或n∈[1,5]時(shí)，取n∈[1,5]∪[9,10]∪[14,17]∪[25,31]∪[46,50]∪[61,85]∪[19,24]，構(gòu)造G4,n1=(S4|G4,n)，其中G4,5=(α1,…,α5)及其子矩陣G4,i=(α1,…,αi)(1≤i≤4)，由此可得[n1,4,d;2]距離最優(yōu)LRC。

2)當(dāng)n∈N1,1時(shí)，結(jié)合N1,1的定義，便于描述，記ng=g+85，下面分情況討論。

①當(dāng)ng∈[91,93]時(shí)，構(gòu)造G4,ng=(G4,75|G4,n1-75)；當(dāng)ng∈[96,98]時(shí)，構(gòu)造G4,ng=(G4,80|G4,ng-80)，以上得到的均為[ng,4,d;2]距離最優(yōu)LRC。

③136≤ng≤144時(shí)，構(gòu)造G4,ng=(M4|G4,ng-64)；當(dāng)145≤ng≤170時(shí)，構(gòu)造G4,ng=(S4|G4,ng-85)，以上得到的均為[ng,4,d;2]距離最優(yōu)LRC。

3)特別地，當(dāng)i=44,49,62,63,64,65,70,75,78,79,80,83,84,85時(shí)，令A(yù)4,2i=(G4,i|G4,i)，得到[2i,4,2d;1]距離最優(yōu)LRC。

綜上可知定理6成立。

2.3.3 171≤n2≤255時(shí)距離最優(yōu)LRC的構(gòu)造

類似于2.3.2節(jié)，給出碼長(zhǎng)171≤n2≤255的四元距離最優(yōu)LRC的構(gòu)造。

定理7記n2=n+170,n∈[1,85]，當(dāng)n2∈[176,178]∪[181,183]∪[202,214]∪[222,230]時(shí)，存在[n2,4,d;2]距離最優(yōu)LRC；對(duì)于其他碼長(zhǎng)n2存在[n2,4,d;1]距離最優(yōu)LRC。特別地，當(dāng)n=204時(shí)，還存在距離最優(yōu)LRC[204,4,152;1]。

證明：當(dāng)n∈N1,0或n∈[1,5]時(shí)，令G4,n2=(S4|S4|G4,n)，得到[n2,4,d;1]距離最優(yōu)LRC；當(dāng)n∈N1,1時(shí)，令G4,n2=(S4|G4,n+85)，得到參數(shù)為[n2,4,d;2]的距離最優(yōu)LRC；當(dāng)n2∈[189,192]時(shí)，令G4,n2=(M4|M4|G4,n2-128)，其中G4,61，G4,62與G4,63是M4的子矩陣，得到[n2,4,d;1]距離最優(yōu)LRC。

特別地，當(dāng)i=102時(shí)，由A4,2i=(G4,i|G4,i)可得[204,4,152;1]距離最優(yōu)LRC。

綜上可知定理7成立。

2.3.4n3≥255時(shí)距離最優(yōu)LRC的構(gòu)造

由已構(gòu)造的四元距離最優(yōu)碼構(gòu)造碼長(zhǎng)n3≥255的四元距離最優(yōu)LRC并判斷[n,4,d;r](n≥5)距離最優(yōu)LRC的局部度最優(yōu)性。

定理8記n3=85i+n，i≥3且n∈[1,85]。若n3∈[274,279]，存在[n3,4,d;2]距離最優(yōu)LRC；對(duì)于其他碼長(zhǎng)n3存在[n3,4,d;1]距離最優(yōu)LRC。

證明：

當(dāng)n3=85i+n(i≥3)且n∈N1,0或n∈N1,1時(shí),令G4,n3=(S4|G4,85(i-1)+n)，得到[n3,4,d;1]距離最優(yōu)LRC；當(dāng)n3=85i+n(i=3)且n∈N1,2時(shí)，令G4,n3=G4,255+n=(S4|G4,170+n)，得到[n3,4,d;2]距離最優(yōu)LRC；當(dāng)n3=85i+n(i≥4)時(shí)，令G4,n3=(S4|G4,n)，得到[n3,4,d;1]距離最優(yōu)LRC。

綜上可知定理8成立。

以上構(gòu)造給出所有[n,4,d]距離最優(yōu)碼，當(dāng)r=1時(shí)，局部度已達(dá)到最優(yōu)。當(dāng)r≥2時(shí)，若n∈[5,10]，[n,4,d;r]為達(dá)到S-L界的距離最優(yōu)LRC;n∈{19,24,33,40,45,66,87,93,114,119,135,145}∪[103,109]∪[176,178]∪[181,183]∪[202,214]∪[222,230]∪[274,279]且n≠204時(shí)，[n,4,d;r]為未達(dá)到S-L界或C-M界的距離最優(yōu)LRC; 其余的為達(dá)到C-M界的距離最優(yōu)LRC。

3 結(jié)語

結(jié)合Grassl碼表[17]及文獻(xiàn)[20]，對(duì)于四元線性碼[n,k,d]，根據(jù)碼的維數(shù)分k=2,3,4三種情形構(gòu)造碼長(zhǎng)n≥k+1的距離最優(yōu)LRC。當(dāng)r=1時(shí)，局部度達(dá)到最優(yōu)。r≥2的[n,k,d;r]距離最優(yōu)LRC的局部度最優(yōu)性如下：n∈[3,5]時(shí)，[n,2,d;2]碼達(dá)到S-L界，[7,2,5;2]和[9,2,7;2]碼達(dá)不到S-L界或C-M界，它們?nèi)允蔷植慷茸顑?yōu)的；[n,3,d;r](n∈[4,9])碼達(dá)到S-L界，[n,3,d;2](n=23,52,53)碼達(dá)不到S-L界或C-M界，其余的LRC達(dá)到C-M界；當(dāng)n∈[5,10]時(shí)，[n,4,d;r]LRC達(dá)到S-L界，52個(gè)LRC達(dá)不到S-L界或C-M界。對(duì)于以上55個(gè)局部度較小仍達(dá)不到S-L界或C-M界的LRC，我們未能判定其局部度的最優(yōu)性，這也是我們接下來要研究的問題。