基于正交拉丁方的局部修復(fù)碼構(gòu)造

劉帥帥，王靜，劉哲，徐忠環(huán)

(長(zhǎng)安大學(xué) 信息工程學(xué)院，陜西 西安 710064)

分布式存儲(chǔ)系統(tǒng)在云計(jì)算時(shí)代得到了廣泛應(yīng)用[1].為了保證系統(tǒng)的持續(xù)可靠運(yùn)轉(zhuǎn)，須采用冗余策略來(lái)應(yīng)對(duì)系統(tǒng)中的節(jié)點(diǎn)故障[2].“復(fù)制”策略操作簡(jiǎn)單，但存儲(chǔ)效率較低；糾刪碼均衡了存儲(chǔ)開(kāi)銷(xiāo)和糾錯(cuò)性能，但在修復(fù)過(guò)程中須重構(gòu)原始文件，帶來(lái)巨大的修復(fù)帶寬開(kāi)銷(xiāo)[3].

Gopalan等[4]提出局部修復(fù)碼(locally repairable codes,LRCs).當(dāng)一個(gè)數(shù)據(jù)節(jié)點(diǎn)發(fā)生故障時(shí)，系統(tǒng)會(huì)通過(guò)獲取r(r?k) 個(gè)節(jié)點(diǎn)的數(shù)據(jù)在局部組內(nèi)修復(fù)故障節(jié)點(diǎn)，而不再重構(gòu)原始文件，帶來(lái)了修復(fù)過(guò)程中帶寬消耗與磁盤(pán)訪問(wèn)數(shù)量的減少，有效地提高了修復(fù)效率.文獻(xiàn)[4]證明 (n,k,r) 局部修復(fù)碼最小距離滿足Singleton-型界，其中，n為碼長(zhǎng)，k為碼字中信息位個(gè)數(shù)，r為局部性參數(shù).Tamo等[5]利用RS碼和特殊的MDS碼構(gòu)造了一類(lèi)最小距離最優(yōu)局部修復(fù)碼，但須在較大的有限域上編碼，增加了實(shí)現(xiàn)的復(fù)雜性.Jin等[6]利用有理函數(shù)域上的自同構(gòu)群推廣了RS碼的構(gòu)造，得到一類(lèi)字母表大小與碼長(zhǎng)相當(dāng)?shù)淖钚【嚯x最優(yōu)局部修復(fù)碼，但參數(shù)須滿足 (r+1)|n.Luo等[7]基于循環(huán)碼和校驗(yàn)多項(xiàng)式構(gòu)造了一類(lèi)碼長(zhǎng)與字母表大小無(wú)關(guān)的局部修復(fù)碼，但只有在最小距離d∈{3,4} 時(shí)才能實(shí)現(xiàn)最小距離最優(yōu).

為了實(shí)現(xiàn)多故障節(jié)點(diǎn)修復(fù)，文獻(xiàn)[8]提出具有(r,t)局部性的局部修復(fù)碼，不相交的t個(gè)修復(fù)集提高了系統(tǒng)的魯棒性，同時(shí)支持?jǐn)?shù)據(jù)的并行讀取.其中，t表示可用性參數(shù).Jin等[9]利用有理函數(shù)域上的自同構(gòu)群構(gòu)造了具有多個(gè)修復(fù)集的局部修復(fù)碼，但碼的最小距離沒(méi)有達(dá)到上界且沒(méi)有考慮碼率.Hao等[10]通過(guò)替換正則矩陣中特定行和列的方法，得到一類(lèi)參數(shù)為 (r,t,δ) 的最小距離最優(yōu)局部修復(fù)碼，但字母表大小須滿足q≥r+δ-2，且碼率較低.Ma等[11]利用弱獨(dú)立集構(gòu)造出維度最優(yōu)的二元線性局部修復(fù)碼，但其參數(shù)須滿足r∈{2,3}.Tan等[12]利用線性代數(shù)和部分幾何構(gòu)造信息位具有 (r,t) 局部性的局部修復(fù)碼，其最小距離最優(yōu)且碼率較高，但當(dāng)可用性較大時(shí)構(gòu)造復(fù)雜度較高.Hao等[13]研究LDPC碼與局部修復(fù)碼之間的關(guān)系，并構(gòu)造3種信息位具有 (r,t) 局部性的局部修復(fù)碼，實(shí)現(xiàn)了最小距離最優(yōu).其中，第1種基于射影平面的構(gòu)造碼率只有0.5，參數(shù)須滿足r=t；第2種刪除仿射平面中特定點(diǎn)線的構(gòu)造方法與第1種構(gòu)造方法的性能相同；第3種基于陣列LDPC碼的構(gòu)造須對(duì)循環(huán)排列矩陣進(jìn)行多次矩陣乘法運(yùn)算，帶來(lái)較大的計(jì)算開(kāi)銷(xiāo).

針對(duì)上述問(wèn)題，提出基于正交拉丁方的二元局部修復(fù)碼構(gòu)造方法，無(wú)須生成抽象幾何圖形和矩陣乘法運(yùn)算，減小了構(gòu)造復(fù)雜度.根據(jù)正交拉丁方元素與矩陣位置的對(duì)應(yīng)關(guān)系構(gòu)造關(guān)聯(lián)矩陣，得到一類(lèi)具有全符號(hào)局部性的局部修復(fù)碼，該碼的碼率和碼長(zhǎng)漸近邊界條件；將關(guān)聯(lián)矩陣級(jí)聯(lián)一個(gè)單位矩陣，構(gòu)造出一類(lèi)信息位具有 (r,t=2) 局部性的單校驗(yàn)局部修復(fù)碼，該碼的最小距離和碼率均滿足邊界條件，為最優(yōu)局部修復(fù)碼.為了修復(fù)系統(tǒng)中的高故障率節(jié)點(diǎn)，利用正交拉丁方完備組構(gòu)造一類(lèi)具有高可用性的單校驗(yàn)局部修復(fù)碼，可根據(jù)節(jié)點(diǎn)故障概率來(lái)選擇可用性t，提高系統(tǒng)的魯棒性.

1 背景知識(shí)

1.1 局部修復(fù)碼

定義1 具有(r,t) 局部性的局部修 碼[8].在有限域Fq中的[n,k,d]q線性分組碼，給定集合{1,2,···,n}，c=[c1,c2,···,cn] 是一個(gè)碼字，如果其中 一個(gè)碼元符號(hào)ci具有局部性r和可用性t，那 么須滿足以下條件：

1）存在t個(gè)子集，R1(i),···,Rt(i)?{1,2,···,n}{i}，滿足

2）Rj(i)∩Rl(i)=?，j≠l且j,l∈{1,2,···,t} ；

3）ci∈span(cl)，其中l(wèi)∈Rj(i),j∈{1,2,···,t}，即向量ci屬于張成的線性空間.其中，稱Rj(i) 為ci的局部 修復(fù)組.

對(duì)于 (n,k) 局部修復(fù)碼，若其所有符號(hào)都具有 (r,t) 局部性，則稱該碼為具有全符號(hào)局部性的局部修復(fù)碼(all symbol-locally repairable codes,AS-LRCs)；若只有信息位符號(hào)具有 (r,t) 局部性，則稱為具有信息符號(hào)局部性的局部修復(fù)碼(information symbol-locally repairable codes,IS-LRCs)[8].

Rawat等[8]證明了當(dāng)每個(gè)局部修復(fù)組中只包含一個(gè)校驗(yàn)符號(hào)時(shí)，信息位符號(hào)具有 (r,t) 局部性LRCs的最小距離界為

滿足邊界條件(式(1))的LRCs，稱為最小距離最優(yōu)的LRCs.

Tan等[12]證明對(duì)于信息位符號(hào)具有 (r,t) 局部性的 [n,k,d]q局部修復(fù)碼，其最小距離滿足

Tamo等[14]提出具有 (r,t) 局部性的LRCs碼率邊界為

式中：R為碼率.

Prakash等[15]提出，當(dāng)可用性t=2 時(shí)，(n,k,r,t=2)-LRCs的碼率邊界和碼長(zhǎng)邊界為

1.2 拉丁方

定 義2 拉丁方[16].設(shè)S={1,2,···,n} 為n元 集合為集合S上的n階方陣.如果方陣L的每行每列都是集合S中元素的一個(gè)全排列，則稱L為S上的一個(gè)n階拉丁方.

定理1[16]對(duì)于n元集S上的拉丁方，若n≠2,6，則必然存在一對(duì)n階正交拉丁方.

定義4 正交拉丁方組[16].對(duì)于n元集S上的t(t≥2) 個(gè)拉丁方，若它們兩兩正交，則它們組成n階(t個(gè))正交拉丁方組.

定 理2[16]用N(n) 表 示n階正交 拉丁方組中拉丁方的最大個(gè)數(shù)，則N(n)≤n-1.

定義5 正交拉丁方完備組[16].若n階正交拉丁方組中含有N(n)=n-1 個(gè)拉丁方，則稱為n階正交拉丁方完備組.

定理3[16]若q為素?cái)?shù)，v為正整數(shù)，p=qv為素?cái)?shù)冪，且p≥3，則存在p階正交拉丁方完備組.

定義6 支撐集[17].給定向量v=[v1,v2,···,vn]，則它的支撐集為 supp(v)={i|vi≠0},i=1,2,···,n.

2 具有全符號(hào)局部性的局部修復(fù)碼構(gòu)造

設(shè)集合 Ω={1,2,···,m2}，矩陣X為由集合 Ω 中m2個(gè)元素排列成的m階方陣，即

定理4將 關(guān)聯(lián) 矩陣作為校驗(yàn)矩陣H1，可以構(gòu)造參數(shù)為n=m2、k=(m-1)2、t=2、r=m-1的AS-LRCs，其中m≥3 且m≠6.

證明由關(guān)聯(lián)矩陣可知構(gòu)造的局部修復(fù)碼的碼長(zhǎng)n=m2，由于集合 Ω 中的每個(gè)元素在集合B1和B2中分別只出現(xiàn)1次，在集合B中共出現(xiàn)2次，故關(guān)聯(lián)矩陣中所有行向量構(gòu)成了一個(gè)線性相關(guān)組，且其中不存在零向量.用bi(1≤i≤2m) 表示關(guān)聯(lián)矩陣的行向量，bi≠0，將所有行向量按分量相加得到零向量，即隨機(jī)刪除1個(gè)行向量bl(l∈{1,2,···,2m})，根據(jù)正交拉丁方的正交性，剩余的行向量構(gòu)成線性無(wú)關(guān)組.因此關(guān)聯(lián)矩陣的秩為局部修復(fù)碼的維度為k=m2-(2m-1)=(m-1)2.關(guān)聯(lián)矩 陣每列漢明重量為2，且每列“1”元素所在的行向量的支撐集只在該“1”元素坐標(biāo)處相交，所以每個(gè)符號(hào)位具有2個(gè)不相交的局部修復(fù)組，即可用性t=2.關(guān)聯(lián)矩陣每行漢明重量為m，當(dāng)某個(gè)符號(hào)位丟失時(shí)須獲得另外m-1 個(gè)符號(hào)位的信息才能恢復(fù)，故修復(fù)局部性r=m-1.

由集合B和集合 Ω 的映射關(guān)系易得關(guān)聯(lián)矩陣：

將關(guān)聯(lián) 矩陣M6×9作 為校驗(yàn)矩 陣H1，可以構(gòu)造參數(shù)為n=9、k=4、t=2、r=2 的AS-LRCs.若 碼元符號(hào)c1故 障，其修復(fù)集為R1(1)={6,8} 和R2(1)={5,9}，故c1=c6⊕c8=c5⊕c9，其中 ⊕ 表示異或運(yùn)算.其他碼元符號(hào)可以通過(guò)類(lèi)似的方法進(jìn)行修復(fù).

定理5定理4構(gòu)造的AS-LRCs的最小距離為d=4，且d＞t+1.

證明AS-LRCs的最小距離d=4 表明其校驗(yàn)矩陣H1即關(guān)聯(lián)矩陣中任意3列線性無(wú)關(guān)，且存在4列線性相關(guān).

1）若3列選自同一組，則對(duì)應(yīng)于拉丁方同一行上的3個(gè)不同元素，由拉丁方的性質(zhì)可知這3個(gè)元素處于不同的m-子集中，故這3列必然線性無(wú)關(guān)，如例1中 {h1,h2,h3} ；

2）若3列中2列選自同一組，剩余1列選自其他組，同一組的2列必然線性無(wú)關(guān)，同組的2列相加可以得到一個(gè)漢明重量為4的列向量，而選自其他組的列向量漢明重量為2，因此這3列必然線性無(wú)關(guān)，如例1中 {h1,h2,h4} ；

3）若3列分別選自不同組，且對(duì)應(yīng)于拉丁方中3個(gè)不同的元素，則與3列選自同一組的情況1)相同，3個(gè)列向量線性無(wú)關(guān)，如例1中 {h1,h4,h7} ；若選自不同組的3列對(duì)應(yīng)于拉丁方中2個(gè)不同的元素，則對(duì)應(yīng)于同一個(gè)元素的2列相加可以得到一個(gè)漢明重量為2的列向量，且2個(gè)“1”元素所在的2行所對(duì)應(yīng)的m-子集處于同一個(gè)Bh(h=1,2)中，而剩余1個(gè)列向量中“1”元素所在的2行所對(duì)應(yīng)的m-子集分別處于不同的Bh(h=1,2) 中，故這3列必然線性無(wú)關(guān)，如例1中 {h1,h6,h7} ；若選自不同組的3列均對(duì)應(yīng)于拉丁方中同一個(gè)元素，則3列所對(duì)應(yīng)的集合 Ω 中的元素所構(gòu)成的子集只能在Bh(h=1,2)中某個(gè)m-子集出現(xiàn)一次，在另一個(gè)集合Bh(h=1,2) 中，子集中3個(gè)元素必處于3個(gè)不同的m-子集中，故這3列必然線性無(wú)關(guān)，如例1中 {h1,h6,h8}.綜上所述，關(guān)聯(lián)矩陣中任意3列線性無(wú)關(guān)，所以d≥4.

綜上所述，定理4構(gòu)造的AS-LRCs最小距離為d=4，且滿足d＞t+1=2+1=3，得證.

如表1所示為幾種典型的AS-LRCs在可用性t=2 時(shí)的參數(shù).表中，w為任意正整數(shù)，m(m≥3,m≠6) 為拉丁方的階數(shù).可以發(fā)現(xiàn)，當(dāng)可用性t=2時(shí)，定理4構(gòu)造的AS-LRCs最小距離最大，并且滿足d＞t+1.

表1 幾種典型AS-LRCs構(gòu)造參數(shù)對(duì)比Tab.1 Comparison of structural parameters of several typical AS-LRCs

由于不存在一對(duì)6階的正交拉丁方，定理4無(wú)法構(gòu)造局部性r=5 的AS-LRCs.下面通過(guò)改變集合的構(gòu)造方法，可以得到任意局部性r≥2 的AS-LRCs.

定理6在m階方陣X上疊合一個(gè)m階標(biāo)準(zhǔn)型拉丁方，即該拉丁方第1行與第1列的元素均按順序排列.集 合仍然利用前面的方法構(gòu)造，而集合則利用標(biāo)準(zhǔn)型拉丁方每列元素在方陣X中對(duì)應(yīng)的位置索引構(gòu) 造，集 合B=B1∪B2.將集合B和集合Ω 的關(guān)聯(lián)矩陣作為校驗(yàn)矩陣，可以構(gòu)造參數(shù)為n=m2、=(m-1)2、t=2、r=m-1 的AS-LRCs，其中m≥3.

可以證明定理6構(gòu)造出來(lái)的AS-LRCs最小距離仍滿足定理5.

例2當(dāng)m=6時(shí)，Ω={1，2，···，36}，方陣X為

6階標(biāo)準(zhǔn)型拉丁方如下：

由集合B和集合Ω 的映射關(guān)系得到關(guān)聯(lián)矩陣M12×36，將其作為校驗(yàn)矩陣可以構(gòu)造一個(gè)參數(shù)為n=36、k=25、t=2、r=5的AS-LRCs.

所構(gòu)造的AS-LRCs碼率為

如圖1所示為定理6構(gòu)造的AS-LRCs碼率與Prakash等[15]提出的碼率邊界的比較.圖中，R為碼率，R=k/n.可以發(fā)現(xiàn)，隨著局部性參數(shù)r的增大，即拉丁方階數(shù)m的增大，AS-LRCs的碼率將逐漸接近碼率邊界，即式(4)中的邊界條件.

圖1 可用性 t=2 時(shí)的碼 率比較Fig.1 Code rate comparison with availability t=2

不過(guò)，由于

定理6中的AS-LRCs碼率始終小于邊界條件(式(4)).

將碼的參數(shù)代入碼長(zhǎng)邊界（式(5)），可以得到

可以看出，定理6構(gòu)造的AS-LRCs碼長(zhǎng)僅比最優(yōu)碼長(zhǎng)界大1，能夠更好地均衡系統(tǒng)的冗余.

3 具有信息位局部性的局部修復(fù)碼構(gòu)造

3.1 信息位具有 (r,t=2) 局部性的局部修復(fù)碼

證明由校驗(yàn)矩陣H2可知構(gòu)造的局部修復(fù)碼的碼長(zhǎng)n=2m+m2，且右邊級(jí)聯(lián)單位矩陣I2m×2m使得校驗(yàn)矩陣H2滿秩，因此局部修復(fù)碼的維度矩陣H2的前m2列對(duì)應(yīng)信息位符號(hào)，后 2m列對(duì)應(yīng)校驗(yàn)位符號(hào).關(guān)聯(lián)矩陣中每列的漢明重量為2，且每列“1”元素所在行向量的支撐集只在該“1”元素坐標(biāo)處相交，所以每個(gè)信息位具有2個(gè)不相交的局部修復(fù)組，即可用性t=2.同時(shí)，校驗(yàn)矩陣H2每行的漢明重量為m+1，當(dāng)某個(gè)信息位符號(hào)丟失時(shí)須獲得另外m個(gè)符號(hào)位的信息才能恢復(fù)，故修復(fù)局部性r=m，且每個(gè)局部修復(fù)組中只有一個(gè)校驗(yàn)符號(hào).

定理8定理7構(gòu)造的IS-LRCs的最小距離為d=3，且最小距離最優(yōu).

證明校驗(yàn)矩陣H2的前m2列漢明重量均為2，后2m列為單位矩陣I2m×2m.從校驗(yàn)矩陣H2的前m2列中任選一個(gè)列向量，表示為ξ，它是單位陣I2m×2m中特定2列的線性組合，故矩陣H2中存在3列線性相關(guān)，d≤3.另一方面，從校驗(yàn)矩陣H2中任選2個(gè)列向量 {hs1,hs2}，其中 1 ≤s1,s2≤2m+m2，若2列都選自單位陣I2m×2m，顯然它們線性無(wú)關(guān)；若2列都選自關(guān)聯(lián)矩陣類(lèi)似于定理5可以證明它們線性無(wú)關(guān)；若其中一列選自單位陣I2m×2m，另一列選自關(guān)聯(lián)矩陣由于列重不同，它們必然線性無(wú)關(guān).因此，校驗(yàn)矩陣H2中任意2列線性無(wú)關(guān)，從而d≥3.綜上所述，定理7構(gòu)造的IS-LRCs的最小距離為d=3.

將參數(shù)n=2m+m2、k=m2、t=2、r=m代 入最小距離邊界條件(式(1))，可得

滿足邊界條件(式(1))，所以定理7構(gòu)造的ISLRCs最小距離最優(yōu).

定理7構(gòu)造的IS-LRCs碼率為

滿足碼率邊界條件（式(4)），因此定理7構(gòu)造的IS-LRCs碼率最優(yōu).

此外，局部性r與維度k的比值為

即當(dāng)系統(tǒng)發(fā)生單節(jié)點(diǎn)故障時(shí)，新生節(jié)點(diǎn)需要連接的幫助節(jié)點(diǎn)數(shù)僅為同參數(shù)下糾刪碼的 1/m，能夠有效降低修復(fù)過(guò)程中的磁盤(pán)I/O開(kāi)銷(xiāo)，加快修復(fù)效率.

3.2 信息位具有 (r,t) 局部性的局部修復(fù)碼

3.1節(jié)構(gòu)造的IS-LRCs的可用性參數(shù)僅局限于t=2，對(duì)于存儲(chǔ)系統(tǒng)中的高故障率節(jié)點(diǎn)，可能無(wú)法確保數(shù)據(jù)的可靠訪問(wèn)，須為其提供更高等級(jí)的保護(hù).利用正交拉丁方完備組構(gòu)造可以靈活調(diào)節(jié)可用性參數(shù)的局部修復(fù)碼.

故障率 τ 是指節(jié)點(diǎn)發(fā)生故障的頻率，即單位時(shí)間內(nèi)節(jié)點(diǎn)發(fā)生故障的次數(shù)[20].通常用系統(tǒng)的平均無(wú)故障時(shí)間(mean time to failure,MTTF)來(lái)表示節(jié)點(diǎn)故障率，即

式中：MTTF為系統(tǒng)從開(kāi)始運(yùn)行到發(fā)生故障的平均工作時(shí)間.

對(duì)第2章中的構(gòu)造進(jìn)行擴(kuò)展，將方陣X與s個(gè)m階相互正交拉丁方疊合，其中 2 ≤s≤m-1，m為素?cái)?shù)冪，且m≥3，s的取值規(guī)則為

式中：τmax為系統(tǒng)中信息位節(jié)點(diǎn)故障率的最大值，τmax=,i=1,2,···,k.

其中，0≤k≤(s+1)m,0≤j≤m2.

定理9在關(guān)聯(lián)矩陣M1右邊級(jí)聯(lián)(s+1)m階單位矩 陣I(s+1)m×(s+1)m，構(gòu)造校 驗(yàn)矩陣H3，即H3=[M1|I(s+1)m×(s+1)m]，其中m為素?cái)?shù)冪，且m≥3.由校驗(yàn)矩陣H3可構(gòu)造參數(shù)為n=sm+m+m2、k=m2、t=s+1、r=m的單校驗(yàn)IS-LRCs，且最小距離最優(yōu)，d=s+2=t+1.

證明由校驗(yàn)矩陣H3可知構(gòu)造的局部修復(fù)碼碼長(zhǎng)n=sm+m+m2，且右邊級(jí)聯(lián)單位矩陣使得校驗(yàn)矩陣H3滿秩，因此局部修復(fù)碼的維度k=m2.矩陣H3的前m2列對(duì)應(yīng)信息位，后(s+1)m列對(duì)應(yīng)校驗(yàn)位.將關(guān)聯(lián)矩陣M1的行按順序分為s+1 組，每組包含m個(gè)行向量，每組對(duì)應(yīng)一個(gè)子集Bh(h=1,2,···,s,c)，集合 Ω 中的每個(gè)元素在每個(gè)子集Bh(h=1,2,···,s,c) 中出現(xiàn)一次，故關(guān)聯(lián)矩陣M1的列重 為s+1，且每列“1”元素所在s+1 行中任 意2行的支撐集只在該“1”元素坐標(biāo)處相交，所以每個(gè)信息位具有s+1 個(gè)不相交的局部修復(fù)組，即可用性為t=s+1.同時(shí)，校驗(yàn)矩 陣H3的行重為m+1，所以當(dāng)某個(gè)信息位符號(hào)丟失時(shí)須獲得其他m個(gè)符號(hào)位的信息才能恢復(fù)，故修復(fù)局部性r=m，且每個(gè)局部修復(fù)組中只有一個(gè)校驗(yàn)符號(hào).

類(lèi)似于定理8，可以證明校驗(yàn)矩陣H3中任意s+1 列線性無(wú)關(guān)，且存在s+2 列線性相關(guān)，故最小距離為d=s+2.此外，將碼的參數(shù)代入式(1)得到

代入式(2)得到

因此最小距離d=t+1，定理9構(gòu)造的IS-LRCs最小距離最優(yōu).

例3令m=4，則 Ω={1，2，···，16}，矩陣X為

假設(shè)系統(tǒng)中至少有一個(gè)信息節(jié)點(diǎn)在單位時(shí)間內(nèi)的故障次數(shù)大于等于4，即 τmax≥4，則s=m-1=3.給出3個(gè)兩兩正交的4階拉丁方:

由集合B和集合 Ω 的映射關(guān)系得到關(guān)聯(lián)矩陣M16×16，由H3=[M16×16|I16×16] 可以得 到參數(shù) 為n=32、k=16、t=4、r=4的IS-LRCs，且最小距離d=t+1=5.

假設(shè)系統(tǒng)中所有信息節(jié)點(diǎn)在單位時(shí)間內(nèi)的故障次數(shù)均小于4，且最大故障率為3，即 τmax=3，則s=τmax-1=2.任意選擇2個(gè)4階正交拉丁方與集合Bc構(gòu)造關(guān) 聯(lián)矩陣M12×16，由H3=[M12×16|I12×12] 可以得到參數(shù)為n=28、k=16、t=3、r=4的IS-LRCs，且最小距離d=t+1=4.

定理9構(gòu)造的IS-LRCs局部性r與維度k的比值為

在大規(guī)模分布式存儲(chǔ)系統(tǒng)中，局部性r與維度k的比值將隨著拉丁方階數(shù)m的增大而顯著減小，因此該IS-LRCs能夠有效減小故障節(jié)點(diǎn)修復(fù)時(shí)間，提升修復(fù)效率.

進(jìn)一步可以得到碼率：

又因?yàn)?2≤s≤m-1，故

即定理9構(gòu)造的IS-LRCs碼率下界為0.5.

如表2所示為幾種典型的基于校驗(yàn)矩陣構(gòu)造的IS-LRCs與定理9構(gòu)造的IS-LRCs的碼率對(duì)比.表中，參數(shù)n、k均用可用性t和局部性r表示，基于陣列LDPC碼構(gòu)造的IS-LRCs可用性t只能取偶數(shù)，v為大于1的正整數(shù).

表2 幾種典型IS-LRCs構(gòu)造參數(shù)對(duì)比Tab.2 Comparison of structural parameters of several typical IS-LRCs

為了更加直觀地對(duì)比幾種方法構(gòu)造出的局部修復(fù)碼的碼率，如圖2所示給出了當(dāng)局部性r=11時(shí)，幾種方法構(gòu)造出的局部修復(fù)碼碼率與Tamo等[14]提出的碼率上界的比較.可以看出，定理9構(gòu)造的IS-LRCs碼率始終大于基于陣列LDPC碼和基于正則矩陣構(gòu)造的IS-LRCs碼率，當(dāng)局部性r取其他值時(shí)，可以得到相同的結(jié)論.隨著可用性t的增大，系統(tǒng)中存儲(chǔ)的冗余數(shù)據(jù)增多，碼率將緩慢減小，體現(xiàn)了可用性t和碼率R這2個(gè)參數(shù)之間的均衡關(guān)系.此外，Tamo等[14]提出的碼率上界適用于有限域Fq上的二元及多元局部修復(fù)碼，而定理9構(gòu)造的是二元局部修復(fù)碼，有限域的大小在一定程度上限制了碼率的提高.

圖2 局部性 r=11 時(shí)的碼 率比較Fig.2 Code rate comparison with locality r=11

4 結(jié)語(yǔ)

考慮到具有 (r,t) 局部性的局部修復(fù)碼不僅可以實(shí)現(xiàn)多故障節(jié)點(diǎn)的局部修復(fù)，還支持?jǐn)?shù)據(jù)的并行讀取，提出利用正交拉丁方構(gòu)造二元局部修復(fù)碼的方法，分別構(gòu)造出全符號(hào)具有 (r,t=2) 局部性和信息位具有 (r,t=2) 局部性的局部修復(fù)碼.進(jìn)一步考慮到系統(tǒng)中存在高故障率節(jié)點(diǎn)，利用正交拉丁方完備組構(gòu)造一類(lèi)擴(kuò)展可用性的單校驗(yàn)局部修復(fù)碼，提高了系統(tǒng)的可靠性.理論分析表明，所構(gòu)造的具有全符號(hào)局部性的局部修復(fù)碼碼率和碼長(zhǎng)漸近邊界條件；信息位具有 (r,t=2) 局部性的單校驗(yàn)局部修復(fù)碼的最小距離和碼率均滿足邊界條件，為最優(yōu)局部修復(fù)碼；擴(kuò)展可用性的單校驗(yàn)局部修復(fù)碼最小距離最優(yōu)，碼率較高，始終大于等于0.5.此外，所有的構(gòu)造均基于二元有限域，即所有的編解碼只涉及異或運(yùn)算，大大提高了編解碼速度，更加適用于實(shí)際的分布式存儲(chǔ)系統(tǒng).

本研究構(gòu)造的局部修復(fù)碼的參數(shù)與正交拉丁方的階數(shù)相關(guān)，故正交拉丁方的存在性在一定程度上限制了參數(shù)的取值，構(gòu)造參數(shù)能夠更加靈活取值的局部修復(fù)碼是未來(lái)值得研究的問(wèn)題.