參數(shù)較小的最優(yōu)局部修復(fù)碼的構(gòu)造

蔣靜 李勇剛

摘? ?要：局部修復(fù)碼（locally Repairable codes）可用于提高分布式存儲(chǔ)系統(tǒng)的修復(fù)效率。在假設(shè)局部修復(fù)碼有多個(gè)互不相交修復(fù)集合，且每一個(gè)修復(fù)集合只包含一個(gè)校驗(yàn)元的前提下，Cai等人給出了局部修復(fù)碼和組合結(jié)構(gòu)填充（Packing）的關(guān)系?；谶@樣的關(guān)系，文中利用組合結(jié)構(gòu)填充，平衡不完全區(qū)組設(shè)計(jì)（Balanced Incomplete Block Design），可分組設(shè)計(jì)（Group Divisible Design）等，構(gòu)造了參數(shù)較小的局部修復(fù)碼。同時(shí)，利用已知結(jié)果可以證明，這些局部修復(fù)碼都達(dá)到了最優(yōu)極小距離，即是最優(yōu)的。

關(guān)鍵詞：局部修復(fù)碼? 分布式存儲(chǔ)系統(tǒng)? 最優(yōu)極小距離? 填充? 平衡不完全區(qū)組設(shè)計(jì)? 可分組設(shè)計(jì)

中圖分類號(hào)：TN911? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?文獻(xiàn)標(biāo)識(shí)碼：A? ? ? ? ? ? ? ? ? ? ? ?文章編號(hào)：1674-098X（2019）05（b）-0135-06

在存儲(chǔ)數(shù)據(jù)時(shí)，由于出現(xiàn)存儲(chǔ)設(shè)備故障或者軟件故障等原因造成數(shù)據(jù)丟失會(huì)時(shí)常發(fā)生。為了應(yīng)對(duì)此類情況的發(fā)生，最簡(jiǎn)單的方法是直接復(fù)制所有數(shù)據(jù)。顯然，這種方法并不適用于海量數(shù)據(jù)的存儲(chǔ)。為了解決這樣的問(wèn)題，人們提出了分布式存儲(chǔ)系統(tǒng)的概念。

在分布式存儲(chǔ)系統(tǒng)中，原始數(shù)據(jù)被分成k個(gè)等大小的片段，然后被編碼成n個(gè)片段存儲(chǔ)在n個(gè)不同的節(jié)點(diǎn)中，使得只用連接其中部分節(jié)點(diǎn)就可以獲取所需要的數(shù)據(jù)。在實(shí)際的系統(tǒng)中，人們一般使用[n，k]極大距離可分碼（Maximum Distance Separable Code，簡(jiǎn)記為[n，k]-MDS code）來(lái)對(duì)數(shù)據(jù)進(jìn)行編碼，因?yàn)橄鄬?duì)于簡(jiǎn)單的復(fù)制來(lái)說(shuō)[1]，它具有更強(qiáng)的容錯(cuò)性能和較高的數(shù)據(jù)可靠性。對(duì)于一個(gè)[n，k]-MDS碼，當(dāng)要修復(fù)1個(gè)節(jié)點(diǎn)時(shí)，我們需要連接k個(gè)節(jié)點(diǎn)。在大規(guī)模分布式存儲(chǔ)系統(tǒng)中，k的值很大，從而導(dǎo)致了系統(tǒng)在修復(fù)數(shù)據(jù)時(shí)的低效性。

為了改善這個(gè)問(wèn)題，Huang等[2]提出了局部修復(fù)碼（Locally Repairable Codes，LRC）的概念，即1個(gè)失效的存儲(chǔ)節(jié)點(diǎn)可以通過(guò)連接其他至多r<

當(dāng)一個(gè)節(jié)點(diǎn)和它的修復(fù)節(jié)點(diǎn)都有故障出現(xiàn)時(shí)，節(jié)點(diǎn)修復(fù)不能在局部執(zhí)行，這時(shí)，每個(gè)節(jié)點(diǎn)有多個(gè)修復(fù)集合的局部修復(fù)碼更可取。Wang等[3]提出了[（r，δ）]c-局部度的概念，即對(duì)于一個(gè)局部修復(fù)碼來(lái)說(shuō)，如果一個(gè)節(jié)點(diǎn)可以被其他節(jié)點(diǎn)的δ-1個(gè)不相交集合分別修復(fù)，那么我們稱這種碼具有[（r，δ）]c-局部度。

到目前為止，有一些文獻(xiàn)討論了極小距離的界并構(gòu)造了一些局部修復(fù)碼，如參考文獻(xiàn)[1-14]。但是，關(guān)于有多個(gè)（δ-1≥2）互不相交的修復(fù)集合的局部修復(fù)碼的結(jié)果很少。Wang等[3]證明了這樣的局部修復(fù)碼有兩個(gè)限定條件：（1）碼長(zhǎng)要非常長(zhǎng)，即n≥k（r（δ-1）+1），其中所有修復(fù)組的大小都不大于r;（2）有限域的大小q要足夠大，即。顯然這是不切實(shí)際的。

2014年，Rawat等[5]在假設(shè)每一個(gè)修復(fù)集合只包含一個(gè)校驗(yàn)元的前提下，構(gòu)造了三類最優(yōu)局部修復(fù)碼。最近，Cai等[15]基于這樣的假設(shè)，討論了局部修復(fù)碼與組合結(jié)構(gòu)填充（packing）的關(guān)系，并利用填充構(gòu)造了一些最優(yōu)局部修復(fù)碼。

本文基于文獻(xiàn)[15]的結(jié)果，利用一些組合設(shè)計(jì)結(jié)構(gòu)，如平衡不完全區(qū)組設(shè)計(jì)和可分組設(shè)計(jì)構(gòu)造了若干滿足要求的填充，并得到了相應(yīng)的最優(yōu)局部修復(fù)碼。

1? 相關(guān)概念

1.1 局部修復(fù)碼

首先我們給出下列記號(hào)。

對(duì)正整數(shù)n，記[n]={1，2，…，n}。

對(duì)質(zhì)數(shù)冪q，IFq表示含有q個(gè)元素的有限域。

對(duì)向量x=（x1，x2，…，x]n）∈IFqn，記[（x1，x2，…，xn）]T為列向量。

一個(gè)IFq上的[n，k]q線性碼指指IFqn的一個(gè)k維子空間，并令其生成矩陣為G=（g1，g2，…，gn），其中g(shù)i為k維列向量，1≤i≤n。若碼的最小距離為d，我們也稱是一個(gè)[n，k，d]q線性碼。我們把[n，k，d]2線性碼簡(jiǎn)記為[n，k，d]。

對(duì)任意子集S[n]，|S|表示集合的大小，span（S）表示由{gi|i∈S}生成的IFq上的線性空間，rank（S）表示span（S）的維數(shù)。

定義1[2]：對(duì)G中任意列向量gi，1≤i≤n，定義Loc（gi）為滿足以下條件的最小的整數(shù)r：存在S={i1，i2，…，ir}[n]＼{i}，使得gi∈span（S），即存在λt∈IFq，1≤t≤r，使得。對(duì)任意S[n]，定義Loc（S）=。對(duì)一個(gè)[n，k，d]q線性碼 ，若存在一個(gè)集合S[n]，使得rank（S）=k，且Loc（S）=r，則稱具有信息局部度r。

定義2[3][11][15]：設(shè)是一個(gè)[n，k，d]q線性碼，且其生成矩陣為G=（g1，g2，…，gn）。

若對(duì)gi，

1≤i≤n，存在δ-1個(gè)兩兩不交的集合R1（i），

使得≤r，且（稱為gi的一個(gè)修復(fù)集），1≤j≤δ，則稱gi具有（r，δ）c局部度。若存在一個(gè)子集S[n]，使得rank（S）=k，且對(duì)任意i∈S，我們都有g(shù)i具有（r，δ）c局部度，則稱擁有信息（r，δ）c局部度。若每個(gè)修復(fù)集合恰好包含一個(gè)校驗(yàn)碼元，則稱擁有信息（r，δ）c局部度。

在文獻(xiàn)[11]中，給出了擁有信息（r，δ，1）c局部度的[n，k，d]q線性碼最小距離的界。

引理1[11]：對(duì)于一個(gè)擁有信息（r，δ，1）c局部度的[n，k，d]q線性碼來(lái)說(shuō)，

若一個(gè)擁有信息（r，δ，1）c局部度的[n，k，d]q線性碼滿足d=n-k-，則稱它是最優(yōu)的。

1.2 組合設(shè)計(jì)結(jié)構(gòu)

填充是一種經(jīng)典的組合結(jié)構(gòu)，被廣泛地應(yīng)用于構(gòu)造光正交碼[17-20]。

定義3[22]：設(shè)R是正整數(shù)集的一個(gè)子集，k≥2是一個(gè)整數(shù)。設(shè)X是一個(gè)包含k個(gè)元素的集合，是X的一些子集（稱為區(qū)組）組成的集合。若X，滿足以下條件：

（1）對(duì)任意B∈，有|B|∈R;

（2）任意點(diǎn)對(duì){x，y}X至多包含于一個(gè)區(qū)組中;

則稱（X，）為一個(gè)（k，R，1）-填充。

若R=R'∪{s}，且（k，R，1）-填充中恰有一個(gè)區(qū)組的長(zhǎng)度為s，則我們將（k，R，1）填充記為（k，R'∪{s*}，1）-填充。若R={r}，則我們把（k，R，1）-填充簡(jiǎn)記為（k，r，1）-填充。若在一個(gè)（k，r，1）-填充中，任意點(diǎn)對(duì){x，y}X恰好出現(xiàn)在一個(gè)區(qū)組中，則我們稱其為（k，r，1）平衡不完全區(qū)組設(shè)計(jì)（Balanced Incomplete Block Design），記為（k，r，1）-BIBD。若在一個(gè)（k，R，1）-填充中，X中的每個(gè)元素恰包含于g個(gè)區(qū)組中，則我們稱此填充是正則的，記為g-正則（k，R，1）-填充。

定義4[22]：設(shè)（X，）為一個(gè)（k，R，1）-填充。若（X，）滿足以下條件：

（1），且對(duì)任意i≠j∈[g]，有;

（2）對(duì)任意i∈[g]，i是X的一個(gè)劃分（稱為平行類），即，且對(duì)任意B≠B′∈i，有B∩B'=;

則稱（X，）是可分解的，記為可分解（k，R，1;g）-填充。

顯然一個(gè)可分解（k，R，1;g）-填充是一個(gè)g-正則（k，R，1）-填充。若在一個(gè)可分解（k，r，1;g）-填充中，任意點(diǎn)對(duì){x，y}X恰好出現(xiàn)在一個(gè)區(qū)組中，則我們稱其為可分解（k，r，1）-平衡不完全區(qū)組設(shè)計(jì)，記為（k，r，1）-RBIBD。

1.3 局部修復(fù)碼和填充的關(guān)系

Cai等[15]證明了局部修復(fù)碼與填充有以下關(guān)系。

引理1[15]：設(shè)k，δ，r是正整數(shù)，且滿足下列條件中的一個(gè)條件：

C1：δ≥4;

C2：δ=3，k≥2r或k=r+κ，其中≤κ<或≤κ

C3： δ=2， k≥2r或k=r+κ，其中≤κ

若r| k（δ-1），則擁有局部信息（r，δ，1）c的對(duì)稱碼是最優(yōu)的，當(dāng)且僅當(dāng)存在一個(gè)（δ-1）-正則（k，r，1）-填充。

引理2[15]：設(shè)k，δ，r是正整數(shù)，且滿足引理1中C1-C3中的一個(gè)條件。若k（δ-1）≡r-1（modr），則擁有局部信息 （r，δ，1）c的對(duì)稱碼是最優(yōu)的，當(dāng)且僅當(dāng)

（1） 存在一個(gè)區(qū)組個(gè)數(shù)為的（k，r，1）-填充。

（2） 存在一個(gè)（δ-1）-正則（k，{r，（r-1）*}，1）-填充。

本文將考慮r=3的情況。由以上兩個(gè)引理我們可以得到以下引理。

引理3：設(shè)k，δ是正整數(shù)且滿足引理1中C1-C3中的一個(gè)條件。若k（δ-1）≡0，2（mod3），則擁有局部信息（3，δ，1）c的對(duì)稱碼是最優(yōu)的，當(dāng)且僅當(dāng)

（1） 存在一個(gè)（δ-1）-正則（k，3，1）-填充，或

（2） 存在一個(gè)（δ-1）-正則（k，{3，2*}，1）-填充。

本文將通過(guò)構(gòu)造滿足要求的填充，并利用上述引理得到以下結(jié)果。

定理1：設(shè)k≤21，δ是正整數(shù)，且k（δ-1）≡0，2（mod3）。若 k，δ滿足下面條件中的一個(gè)條件：

C1：? δ≥4;

C2： δ=3，k≥6;

C3： δ=2，k≥5;

則存在一個(gè)擁有局部信息（r，δ，1）c的最優(yōu)對(duì)稱碼。

由引理3，為了得到定理1，我們需要構(gòu)造相應(yīng)的填充。顯然，當(dāng)R∈{{3}，{3，2*}}時(shí)，由填充的定義可知，在（k，R，1）-填充中，每個(gè)點(diǎn)出現(xiàn)的次數(shù)不大于，所以δ-1≤。因此，我們只需構(gòu)造表1中列出的填充。

2? 最優(yōu)局部修復(fù)碼的構(gòu)造

本節(jié)將構(gòu)造表1中列出的所有填充。首先我們考慮 δ-1=1的情況。

引理4：設(shè)k≥4是一個(gè)整數(shù)。

（1） 若k≡0 （mod 3），則存在一個(gè) 1-正則（k，3，1）-填充。

（2） 若k≡2 （mod 3），則存在一個(gè) 1-正則（k，{3，2*}，1）-填充。

證明：（1）當(dāng)k≡0（mod 3）時(shí)，設(shè)X={0，1，…，k-1}。對(duì)任意1≤i≤，取

Bi={（i-1）3，（i-1）3+1，（i-1）3+2}

且{Bi|1≤i≤k/3}。則（X，）是一個(gè)1-正則（k，3，1）-填充。

（2）當(dāng)k≡2 （mod 3）時(shí)，設(shè) X={0，1，…，k-1}。對(duì)任意1≤i≤，取

Bi={（i-1）3，（i-1）3+1，（i-1）3+2}，

且。

則（X，）是一個(gè)1-正則（k，{3，2*}，1-填充。

推論1：（1）存在一個(gè)1-正則（k，3，1）-填充，其中 k∈{6，9，12，15，18，21}。

（2）存在一個(gè)1-正則（k，{3，2*}，1）-填充，其中 k∈{5，8，11，14，17，20}。

引理5：若存在一個(gè)（k，3，1）-RBIBD，則存在一個(gè)g-正則 （k，3，1）-填充，其中1≤g≤。

證明：設(shè)（X，）是一個(gè)（k，3，1）-RBIBD。則（X，）有個(gè)平行類，記為i，1≤i≤。對(duì)任意1≤g≤（k-1）/2，取。則（X，（g））即為一個(gè)g-正則 （k，3，1）-填充。

引理6[22]：存在一個(gè)（k，3，1）-RBIBD，其中k∈{9，15，21}。

推論2：存在一個(gè)g-正則（k，3，1）-填充，其中k∈{9，15，21}，1≤g≤。

下面我們將利用可分組設(shè)計(jì)構(gòu)造填充。

定義5[22]：設(shè)R和H都是正整數(shù)集的子集，k≥2是一個(gè)整數(shù)。設(shè)X是一個(gè)包含k個(gè)元素的集合，是X的一個(gè)劃分（中的元素被稱為組），是X的一些子集（稱為區(qū)組）組成的集合。若滿足以下條件：

（1） 對(duì)任意B∈B，有 |B|∈R;

（2） 不同組的任意兩個(gè)元素恰包含于一個(gè)區(qū)組中;

（3） 同一組的任意兩個(gè)元素不包含于同一個(gè)區(qū)組中;

（4） | |>1;

則稱為一個(gè)可分組設(shè)計(jì)（Group divisible design），記為R-GDD。

若R={r}，則將R-GDD簡(jiǎn)記為r-GDD。若在一個(gè)r-GDD 中，若||=u且對(duì)任意G∈，都有|G|=h，則稱是一個(gè)型為hu的r-GDD。更進(jìn)一步，若一個(gè)型為hu的r-GDD 滿足定義4中的條件（1）和（2），則稱其為可分的，記為型為hu的r-RGDD。

引理7：若存在一個(gè)型為hu的3-RGDD，則存在一個(gè)g-正則（hu，3，1）-填充，其中1≤g≤

證明：設(shè)是一個(gè)型為?u的3-RGDD。我們首先證明（X，）是一個(gè)-正則可分解（hu，3，1）-填充。因?yàn)槭且粋€(gè)型為?u的3-RGDD，所以對(duì)任意B∈，有|B|=3，且對(duì)于不同組的任意兩個(gè)元素x，y來(lái)說(shuō)，{x，y}恰包含于一個(gè)區(qū)組中。顯然 X 中的任意一個(gè)點(diǎn)在中出現(xiàn)的次數(shù)為

即證。因?yàn)槭且粋€(gè)型為RGDD，所以（X，）是一個(gè)可分解（?u，3，1）-填充。

下面我們將構(gòu)造一個(gè)g-正則 （hu，3，1）-填充，其中1≤g≤因?yàn)椋╔，）是一個(gè)-正則可分解 （hu，3，1）-填充，所以（X，）有個(gè)平行類，記為i， 1≤i≤。對(duì)任意1≤g≤，取

1≤i≤g}。則即為一個(gè)g-正則（k，3，1）-填充。即證。

引理8[22]：存在一個(gè)型為hu的3-RGDD，其中（h，u）∈{（4，3），（2，9）}。

推論3：存在一個(gè)g-正則（hu，3，1）-填充，其中（h，u）∈{（4，3），（2，9）}，1≤g≤。

引理9：若存在一個(gè)（k，3，1）-BIBD，則存在一個(gè)-正則 （k，3，1）-填充、一個(gè)-正則 （k-1，3，1）-填充和一個(gè)-正則 （k-2，{3，2*}，1）-填充。

證明：設(shè)（X，）是一個(gè)（k，3，1）-BIBD。顯然（X，）是一個(gè)正則（k，3，1）-填充。

設(shè)x∈X，且。則為一個(gè)-正則（k，1，3，1）-填充，所以。 因此存在一個(gè)點(diǎn)z∈X＼x，使得。在中取一個(gè)包含z的區(qū)組Bz。則即為一個(gè)-正則 （k-2，{3，2*}，1）-填充。

引理10[22]：存在一個(gè)（k，3，1）-BIBD，其中 k∈{7，9，13，15，19，21}。

推論4：（1） 存在一個(gè) g-正則（k，3，1）-填充，其中（k，g）∈{（7，3），（6，2），（9，4），（8，3），（13，6），（12，5），（15，7），（14，6），（19，9），（18，8），（21，10），（20，9）}。（2） 存在一個(gè) g-正則 （k，{3，2*}，1）-填充，其中（k，g）∈{（7，2），（11，4），（13，5），（17，7），（19，8）} 。

引理11：存在一個(gè)g-正則（k，3，1）-填充，其中（k，g）∈{（11，3）， （13，3），（14，3），（16，3），（16，6），（17，3），（17，6），（19，3），（19，6），（20，3），（20，6）}。

證明：設(shè)X={0，1，…，k-1}。我們構(gòu)造g-正則（k，3，1）-填充的區(qū)組集（（k，g））如下：

（11，3）={{0，1，3}，{1，2，4}，{2，3，5}，{3，4，6}，{4，5，7}，

{5，6，8}，{6，7，9}，{7，8，0}，{8，9，1}，{9，0，2}};

（13，3）={{0，1，4}，{1，2，5}，{2，3，6}，{3，4，7}，{4，5，8}，

{5，6，9}，{6，7，10}，{7，8，11}，{8，9，12}，{9，10，0}，

{10，11，1}，{11，12，2}，{12，0，3}};

（14，3）={{0，1，4}，{1，2，5}，{2，3，6}，{3，4，7}，{4，5，8}，

{5，6，9}，{6，7，10}，{7，8，11}，{8，9，12}，{9，10，13}，

{10，11，0}，{11，12，1}，{12，13，2}，{13，0，3}};

（16，3）={{0，1，4}，{1，2，5}，{2，3，6}，{3，4，7}，{4，5，8}，

{5，6，9}，{6，7，10}，{7，8，11}，{8，9，12}，{9，10，13}，

{10，11，14}，{11，12，15}，{12，13，0}，{13，14，1}，

{14，15，2}，{15，0，3}};

（16，6）={{0，1，4}，{1，2，5}，{2，3，6}，{3，4，7}，{4，5，8}，

{5，6，9}，{6，7，10}，{7，8，11}，{8，9，12}，{9，10，13}，

{10，11，14}，{11，12，15}，{12，13，0}，{13，14，1}，

{14，15，2}，{15，0，3}，{0，2，7}，{1，3，8}，{2，4，9}，

{3，5，10}，{4，6，11}，{5，7，12}，{6，8，13}，{7，9，14}，

{8，10，15}，{9，11，0}，{10，12，1}，{11，13，2}，

{12，14，3}，{13，15，4}，{14，0，5}，{15，1，6}};

（17，3）={{0，1，4}，{1，2，5}，{2，3，6}，{3，4，7}，{4，5，8}，

{5，6，9}，{6，7，10}，{7，8，11}，{8，9，12}，{9，10，13}，

{10，11，14}，{11，12，15}，{12，13，16}，{13，14，0}，

{14，15，1}，{15，16，2}，{16，0，3}};

（17，6）={{0，1，4}，{1，2，5}，{2，3，6}，{3，4，7}，{4，5，8}，

{5，6，9}，{6，7，10}，{7，8，11}，{8，9，12}，{9，10，13}，

{10，11，14}，{11，12，15}，{12，13，16}，{13，14，0}，

{14，15，1}，{15，16，2}，{16，0，3}}，{0，2，7}，{1，3，8}，

{2，4，9}，{3，5，10}，{4，6，11}，{5，7，12}，{6，8，13}，

{7，9，14}，{8，10，15}，{9，11，16}，{10，12，0}，

{11，13，1}，{12，14，2}，{13，15，3}，{14，16，4}，

{15，0，5}，{16，1，6}};

（19，3）={{0，1，4}，{1，2，5}，{2，3，6}，{3，4，7}，{4，5，8}，

{5，6，9}，{6，7，10}，{7，8，11}，{8，9，12}，{9，10，13}，

{10，11，14}，{11，12，15}，{12，13，16}，{13，14，17}，

{14，15，18}，{15，16，0}，{16，17，1}，{17，18，2}，

{18，0，3}};

（19，6）={{0，1，4}，{1，2，5}，{2，3，6}，{3，4，7}，{4，5，8}，

{5，6，9}，{6，7，10}，{7，8，11}，{8，9，12}，{9，10，13}，

{10，11，14}，{11，12，15}，{12，13，16}，{13，14，17}，

{14，15，18}，{15，16，0}，{16，17，1}，{17，18，2}，

{18，0，3}，{0，2，7}，{1，3，8}，{2，4，9}，{3，5，10}，

{4，6，11}，{5，7，12}，{6，8，13}，{7，9，14}，{8，10，15}，

{9，11，16}，{10，12，17}，{11，13，18}，{12，14，0}，

{13，15，1}，{14，16，2}，{15，17，3}，{16，18，4}，

{17，0，5}，{18，1，6}};

（20，3）={{0，1，4}，{1，2，5}，{2，3，6}，{3，4，7}，{4，5，8}，

{5，6，9}，{6，7，10}，{7，8，11}，{8，9，12}，{9，10，13}，

{10，11，14}，{11，12，15}，{12，13，16}，{13，14，17}，

{14，15，18}，{15，16，19}，{16，17，0}，{17，18，1}，

{18，19，2}，{19，0，3}};

（20，6）={{0，1，4}，{1，2，5}，{2，3，6}，{3，4，7}，{4，5，8}，

{5，6，9}，{6，7，10}，{7，8，11}，{8，9，12}，{9，10，13}，

{10，11，14}，{11，12，15}，{12，13，16}，{13，14，17}，

{14，15，18}，{15，16，19}，{16，17，0}，{17，18，1}，

{18，19，2}，{19，0，3}，{0，2，7}，{1，3，8}，{2，4，9}，

{3，5，10}，{4，6，11}，{5，7，12}，{6，8，13}，{7，9，14}，

{8，10，15}，{9，11，16}，{10，12，17}，{11，13，18}

{12，14，19}，{13，15，0}，{14，16，1}，{15，17，2}，

{16，18，3}，{17，19，4}，{18，0，5}，{19，1，6}}。

引理12：存在一個(gè)g-正則（k，{3，2^* }，1）-填充，其中（k，g）∈{（10，2），（13，2），（14，4），（16，2），（16，5），（17，4），（19，5），（20，4），（20，7）}。

證明：設(shè)X={0，1，…，k-1}。我們構(gòu)造 g-正則（k，{3，2^* }，1）-填充的區(qū)組集B^（（k，g））如下：

（10，2）={{8，9}，{0，1，2}，{0，3，4}，{1，3，5}，{2，4，6}，

{5，7，8}，{6，7，9}};

（13，2）={{11，12}，{0，1，2}，{0，3，4}，{1，3，5}，{2，4，5}，

{6，7，8}，{6，9，10}，{7，9，11}，{8，10，12}};

（14，4）={{12，13}，{0，1，2}，{0，3，4}，{0，5，6}，{0，7，8}，

{1，3，5}，{1，4，6}，{1，7，9}，{2，3，6}，{2，4，5}，{2，7，10}，

{3，8，11}，{4，9，12}，{5，10，13}，{6，11，12}，{7，11，13}

{8，9，13}，{8，10，12}，{9，10，11}};

（16，2）={{14，15}，{0，1，2}，{0，3，4}，{1，3，5}，{2，4，5}，

{6，7，8}，{6，9，10}，{7，9，11}，{8，10，12}，{11，13，14}，

{12，13，15}};

（16，5）={{12，13}，{0，1，2}，{0，3，14}，{0，5，6}，

{0，7，13}，{0，9，10}，{1，3，5}，{1，4，6}，{1，7，9}，{1，8，10}，

{2，3，6}，{2，4，5}，{2，8，9}，{2，11，14}，{3，7，11}，

{3，8，12}，{4，7，12}，{4，8，11}，{4，10，15}，{5，9，13}，

{5，11，15}，{6，7，15}，{6，9，14}，{8，13，15}，{10，11，12}，

{10，13，14}，{12，14，15}};

（17，4）={{14，15}，{0，1，2}，{0，3，4}，{0，5，16}，

{0，7，8}，{1，3，5}，{1，4，6}，{1，7，9}，{2，3，6}，

{2，4，5}，{2，7，10}，{3，7，11}，{4，8，9}，{5，8，10}，

{6，8，12}，{6，13，16}，{9，12，15}，{9，13，14}，{10，11，14}，

{10，13，15}，{11，12，13}，{11，15，16}，{12，14，16}};

（19，5）={{16，18}，{0，1，2}，{0，3，13}，{0，9，10}，

{0，14，15}，{0，17，18}，{1，3，5}，{1，4，6}，{1，7，9}，

{1，8，10}，{2，3，6}，{2，4，5}，{2，7，10}，{2，13，17}，

{3，7，11}，{3，8，12}，{4，7，12}，{4，8，11}，{4，13，14}，

{5，6，15}，{5，9，11}，{5，10，12}，{6，9，12}，{6，13，16}，

{7，14，16}，{8，14，18}，{8，15，17}，{9，15，18}，{10，14，17}，

{11，13，18}，{11，15，16}，{12，16，17}};

（20，4）={{17，19}，{0，1，2}，{0，3，4}，{0，5，6}，{0，7，8}，

{1，3，5}，{1，4，6}，{1，7，9}，{2，3，6}，{2，4，5}，{2，7，10}，

{3，7，11}，{4，8，16}，{5，8，10}，{6，8，11}，{9，10，11}，

{9，12，13}，{9，15，16}，{10，12，14}，{11，14，18}，{12，15，17}，

{12，18，19}，{13，14，17}，{13，15，18}，{13，16，19}，

{14，15，19}，{16，17，18}};

（20，7）={{15，16}，{0，1，2}，{0，3，18}，{0，7，8}，

{0，9，10}，{0，11，12}，{0，13，14}，{0，16，19}，{1，3，5}，

{1，4，6}，{1，7，16}，{1，11，13}，{1，12，17}，{1，18，19}，

{2，3，6}，{2，4，5}，{2，7，10}，{2，11，14}，{2，13，15}，

{2，16，18}，{3，7，12}，{3，8，16}，{3，9，13}，{3，10，14}，

{4，8，19}，{4，9，14}，{4，10，18}，{4，12，15}，{4，16，17}，

{5，6，19}，{5，7，13}，{5，8，14}，{5，9，15}，{5，10，12}，

{6，7，14}，{6，8，13}，{6，10，11}，{6，15，17}，{7，17，19}，

{8，9，17}，{8，15，18}，{9，12，18}，{9，11，16}，{10，13，17}，

{11，15，19}，{11，17，18}，{12，14，19}}。

定理1的證明：由推論1-4和引理11-12可知，存在一個(gè)（δ-1）-正則（k，R，1）-填充，其中（k，δ-1，R）的值為表1中列出的值。由引理3可知，存在一個(gè)擁有局部信息（r，δ，1）c的最優(yōu) 對(duì)稱碼。

3? 結(jié)語(yǔ)

本文構(gòu)造了參數(shù)較小的最優(yōu)局部修復(fù)碼，即基于文獻(xiàn)[15]的結(jié)果，利用一些組合設(shè)計(jì)結(jié)構(gòu)，構(gòu)造了當(dāng)k（δ-1）≡0，2（mod 3）且k≤21時(shí)，擁有局部信息（3，δ，1）c的最優(yōu)對(duì)稱碼。本文方法也可以用于構(gòu)造k>21時(shí)的最優(yōu)局部修復(fù)碼，但這樣的局部修復(fù)碼結(jié)構(gòu)較復(fù)雜、相應(yīng)的構(gòu)造也更加困難，需要對(duì)構(gòu)造方法做進(jìn)一步地改進(jìn)。

參考文獻(xiàn)

[1] Gopalan P， Huang C， Simitci H， Yekhanin S. On the Locality of Codeword Symbols[J]. IEEE Transactions on Information Theory， 2012， 58（11）： 6925-6934.

[2] Huang C， Chen M， Li J. Pyramid Codes： Flexible Schemes to Trade Space for Access Efficiency in Reliable Data Storage Systems[J]. ACM Transactions on Storage， 2013， 9（1）：3.

[3] Wang A， Zhang Z. Repair Locality with Multiple Erasure Tolerance[J]. IEEE Transactions on Information Theory， 2014， 60（11）： 6979-6987.

[4] Cadambe V R， Huang C， Li J. Permutation Code： Optimal Exact-Repair of A Single Failed Node in MDS Code based Distributed Storage Systems[C]// Proceedings of international symposium on information theory， St. Petersburg，? USA， IEEE Press， 2011： 1225-1229.

[5] Forbes M， Yekhanin S. On the Locality of Codeword Symbols in Non-Linear Codes[J]. Discrete Mathematics， 2014， 324（6）： 78-84.

[6] Gopalan P， Huang C， Jenkins B， Yekhanin S. Explicit Maximally Recoverable Codes with Locality[J]. IEEE Transactions on Information Theory， 2014， 60（9）： 5245-5256.

[7] Pamies-Juarez L， Hollmann H， Oggier F. Locally Repairable Codes with Multiple Repair Alternatives[C]// Proceedings of International Symposium on Information Theory，? Istanbul， Turkey， IEEE Press， 2013： 892-896.

[8] Papailiopoulos D S， Dimakis A G. Locally Repairable Codes[C]// Proceedings of International Symposium on Information Theory， Cambridge MA， USA， IEEE Press， 2012： 2771-2775.

[9] Prakash N， Kamath G M， Lalitha V， et al. Optimal Linear Codes with a Local-Error-Correction Property[C]// Proceedings of International Symposium on Information Theory， Cambridge MA，USA，IEEE Press， 2012： 2776-2780.

[10]Rawat A S， Koyluoglu O O， Silberstein N， et al. Optimal Locally Repairable and Secure Codes for Distributed Storage Systems[J]. IEEE Transactions on Information Theory， 2014， 60（1）： 212-236.

[11]Rawat A S， Papailopoulos D S， Dimakis A G， et al.? Locality and Availability in Distributed Storage[J]. IEEE Transactions on Information Theory， 2016， 62（8）： 4481-4493.

[12]Song W， Dau S， Yuen C， et al. Optimal Locally? Repairable Linear Codes[J]. IEEE Journal on Selected Areas in Communications， 2014， 32（5）： 1019-1036.

[13]Tamo I， Barg A. A Family of Optimal Locally Recoverable Codes[J]. IEEE Transactions on Information Theory， 2014， 60（8）： 4661-4676.

[14]Wang A， Zhang Z. An Integer Programming-based Bound for Locally Repairable Codes[J]. IEEE Transactions on Information Theory， 2015， 61（10）： 5280-5294.