王 娥 李靜輝 楊佳蓉

（長安大學(xué) 西安 710064）

1 引言

隨著信息時代的飛速發(fā)展，海量數(shù)據(jù)隨之產(chǎn)生［1］。大型分布式存儲系統(tǒng)往往采取冗余策略來保證數(shù)據(jù)可靠性［2］。最常見的冗余策略是復(fù)制，但是由于其高存儲開銷逐漸被糾刪碼取代［3］。糾刪碼在確保數(shù)據(jù)可靠性的同時減小了存儲開銷，但是其修復(fù)帶寬開銷過大。再生碼平衡了存儲開銷和修復(fù)帶寬開銷之間的關(guān)系，但是再生碼具有較高修復(fù)局部性和計算復(fù)雜度［4］。為了解決這一問題，Gopalan 等提出了局部修復(fù)碼（Locally Repairable Codes，LRCs）的概念［5］。局部修復(fù)碼減小了故障節(jié)點修復(fù)時的磁盤I/O 開銷。對于一個[n，k，d]線性碼來說，具有局部性r 的碼字符號表示其最多可以從r個其他碼字符號中恢復(fù)。碼字符號具有局部性r 的[n，k，d] 線性碼又被稱為(n，k，r) 局部修復(fù)碼［6］。除了局部性r，可用性t也是局部修復(fù)碼的一個重要屬性［7］。這一屬性與熱數(shù)據(jù)密切相關(guān)。具有(r，t)-局部性的局部修復(fù)碼確保了熱數(shù)據(jù)在多個修復(fù)組中的局部修復(fù)和并行讀?。?］。

目前有許多學(xué)者對(n，k，r)局部修復(fù)碼展開研究。Tamo 等［9］基于Reed-Solomon 編碼塊構(gòu)造了一種最小距離最優(yōu)的局部修復(fù)碼，但是該碼不能在較小的有限域上實現(xiàn)，其編碼和修復(fù)復(fù)雜度較高。Wang 等［10］基于球面填充方法推導(dǎo)出(n，k，r)二元局部修復(fù)碼的維度k的上界，并將邊界和碼的構(gòu)造擴展到了q元域上，但是構(gòu)造的碼既沒有實現(xiàn)最小距離最優(yōu)也沒有實現(xiàn)碼率最優(yōu)。Chen 等［11］利用常環(huán)MDS 碼構(gòu)造了七類具有新參數(shù)的最優(yōu)(r，δ)-局部修復(fù)碼，但是該碼的參數(shù)選擇不夠靈活。Cai等［12］提出了一種新的最小距離界，并且給出了滿足該界的局部修復(fù)碼的顯示結(jié)構(gòu)，但是構(gòu)造的碼的碼率較低。Balaji 等［13］推導(dǎo)出(n，k，r)局部修復(fù)碼的碼率上界，并且基于校驗矩陣構(gòu)造了達到該上界的局部修復(fù)碼，但是構(gòu)造的碼不是最優(yōu)的局部修復(fù)碼。

為了解決上述問題，本文基于相互正交的拉丁方（Mutually Orthogonal Latin Squares，MOLS）提出一種信息符號具有(r，t)-局部性的二元局部修復(fù)碼（Binary Locally Repairable Codes，BLRCs）。其編碼和修復(fù)過程均在二元域上進行，有效降低了運算復(fù)雜度。除此之外，本文構(gòu)造的BLRCs是最小距離最優(yōu)的二元局部修復(fù)碼。當(dāng)可用性t=2 時，該BLRCs實現(xiàn)了碼率最優(yōu)。

2 基礎(chǔ)知識

2.1 局部修復(fù)碼

定義1［14］若φ1(i)局部修復(fù)碼的一個碼字符號可以被大小至多為r 的t 個不相交的修復(fù)集修復(fù)，則稱該碼字符號具有(r，t)-局部性。具有(r，t)-局部性的局部修復(fù)碼需要滿足：

1）φ1(i)，φ2(i)，…，φt(i)?[n]{i}；

2）|φj(i)|≤r，j∈[t]；

3）φj(i)∩φl(i)=?，j≠l∈[t]。

其中φj(i)(j∈[t])為ci的修復(fù)集。

定義2［15］當(dāng)(n，k，r，t)i局部修復(fù)碼的所有信息符號都具有(n，k，r，t)i-局部性時，該局部修復(fù)碼被稱為(n，k，r，t)i-LRCs。若(n，k，r，t)i-LRCs 的每個信息符號的修復(fù)集都只包含一個校驗符號，則該局部修復(fù)碼被稱為單校驗(n，k，r，t)i-LRCs。

定理1［14］單校驗(n，k，r，t)i-LRCs的最小距離滿足：

定理2［16］Prakash 等人推導(dǎo)出可用性為2 的局部修復(fù)碼的碼率滿足：

2.2 區(qū)組設(shè)計

定義3［17］設(shè)X={x1，x2，…，xv} 為一v元集，B1，B2，…，Bb是X的b個不同的k元子集。若滿足條件：

1）對?x∈X，x恰好出現(xiàn)在B1，B2，…，Bb的r個中；

2）X的每個2 元子集都恰好包含在子集組B1，B2，…，Bb的λ個中；

3）0 ＜λ，k＜v-1。

則稱B1，B2，…，Bb為一(b，v，r，k，λ)-設(shè)計。

定義4［17］設(shè)X，Bi(i=1，2，…，b)如定義3，則X關(guān)于Bi的關(guān)聯(lián)矩陣A=(aij)b×v(i=1，2，…b;j=1，2，…v)。其中：

2.3 MOLS

定義5［18］設(shè)A=(aij)是一個m×s矩陣，若A的任一行是集[1，n]的一個s-排列，任一列是集[1，n]的一個m-排列，則稱A是一個m×s的拉丁矩(m≤n，s≤n)。若m=s=n，則稱A為一個n階拉丁方（Latin Square）。

定義6［18］設(shè)A=(aij)，B=(bij)是兩個不同的n階拉丁方，如果n2個有序?qū)Χ际遣煌模瑒t稱拉丁方A與B正交。設(shè)A1，A2，…As是一組n階拉丁方，n≥s，s≥2，若只要i≠j，Ai與Aj就正交，則稱A1，A2，…As是相互正交的拉丁方（Mutually Orthogonal Latin Squares，MOLS）。

定理3［18］設(shè)n=pα，其中p是素數(shù)，α是正整數(shù)，則一定存在由n-1 個n階拉丁方組成的完備正交組。

定理4［18］令n≥2 為一整數(shù)。如果存在n-1 個n階MOLS，則存在(b=n2+n，v=n2，k=n，r=n+1，λ=1)-設(shè)計。

3 基于MOLS的局部修復(fù)碼構(gòu)造

本節(jié)基于MOLS 提出一種信息符號具有(r，t) -局部性的(n，k，r，t)i-BLRCs 的構(gòu)造算法。具體步驟如下：

1）令q=pα(p∈P，α∈N*)，給定A1，A2，…Aq-1表示q-1個q階MOLS。

2）令矩陣：

3）由以上定義的q+1 個矩陣Ao(o=-1，0，…q-1) 構(gòu)造(b=q2+q，v=q2，r'=q+1，k'=q，λ=1) -設(shè)計。具體的，給定q2元集X=xj(j=1，2，…，q2)，由Ao確定q2+q個區(qū)組Ao(z)(z=1，2，…q) 。令A(yù)o中第m行第s列的元素為Ao(m，s) ，若Ao(m，s)=z，則x(m-1)q+s∈Ao(z)。

4）將區(qū)組Ao(z) 標(biāo)記為區(qū)組Bi(i=1，2，…，q2+q)。

5）將區(qū)組Bi(i=1，2，…，q2+q)與矩陣的行關(guān)聯(lián)，集合xj(j=1，2，…，q2)與矩陣的列關(guān)聯(lián)，得到X關(guān)于Bi的關(guān)聯(lián)矩陣A=(aij)(q2+q)×q2(i=1，2，…q2+q，j=1，2，…，q2)，其中，

6）在矩陣A前面級聯(lián)一個q2+q階單位矩陣I得到統(tǒng)一的生成矩陣G=(I|A)(q2+q)×(2q2+q)。則由生成矩陣G定義的二進制線性碼C是信息符號具有(q+1，q) -局部性的(n=2q2+q，k=q2+q，r=q+1，t=q)i-BLRCs。

例：以下給出(n=10，k=6，r=3，t=2)i-BLRCs的構(gòu)造過程。

令q=21=2，

令：

給定X={x1，x2，x3，x4}，則區(qū)組：

A-1(1)={x1，x2}，A(-1)(2)={x3，x4}，A0(1)={x1，x3}，A0(2)={x2，x4}，A1(1)={x1，x4}，A1(2)={x2，x3}。

則區(qū)組：

B1={x1，x2}，B2={x3，x4}，B3={x1，x3}，

B4={x2，x4}，B5={x1，x4}，B6={x2，x3}。

則X關(guān)于Bi的關(guān)聯(lián)矩陣：

則由生成矩陣G=(I|A)12×21構(gòu)造的碼是單校驗(n=10，k=6，r=3，t=2)i-BLRCs，最小距離d=t+1=3，碼率R=k/n=0.6 。若信息節(jié)點c1故障，有c1=c3+c5+c7=c4+c6+c8。因此，c1的修復(fù)集為φ1(1)={3，5，7}，φ2(1)={4，6，8}。同理，可以得到其他碼字符號的修復(fù)集。

4 性能分析

4.1 最小距離

本節(jié)討論基于MOLS 構(gòu)造的BLRCs 的最小距離，將它與最優(yōu)最小距離邊界進行比較。

將基于MOLS 構(gòu)造的信息符號具有(r=q+1，t=q) -局部性的單校驗(n=2q2+q，k=q2+q，r=q+1，t=q)i-BLRCs 的參數(shù)n=2q2+q，k=q2+q，r=q+1，t=q代入式（1）可得：

滿足式（1）上界，即基于MOLS 構(gòu)造的單校驗(n=2q2+q，k=q2+q，r=q+1，t=q)i-BLRCs 是最小距離最優(yōu)的二元局部修復(fù)碼，且最小距離d=t+1。

4.2 碼率

本節(jié)討論基于MOLS 構(gòu)造的BLRCs 的碼率，將它與最優(yōu)碼率邊界進行比較。

基于MOLS 構(gòu)造的單校驗(n=2q2+q，k=q2+q，r=q+1，t=q)i-BLRCs的碼率

當(dāng)t=2 時，基于MOLS 構(gòu)造的BLRCs 的碼率R=r/(r+2)滿足式（2）上界。即當(dāng)可用性t=2 時，基于MOLS 構(gòu)造的BLRCs 是碼率最優(yōu)的二元局部修復(fù)碼。

4.3 與其他碼的比較

下面比較基于MOLS 構(gòu)造的BLRCs 與基于陣列LDPC 碼構(gòu)造的BLRCs［19］，直積碼［20］和基于迭代矩陣構(gòu)造的BLRCs［21］的碼長n和碼率R。表1 列出了這四種BLRCs的相關(guān)參數(shù)。為方便比較，將這些碼的碼長n，信息位k，碼率R，均用局部性r和可用性t表示。

表1 四種BLRCs相關(guān)參數(shù)對照

碼長n的比較：

由表1 可知，當(dāng)r≥t≥2 時，基于陣列LDPC 碼構(gòu)造的BLRCs的碼長：

當(dāng)r≥2，t≥2 時，直積碼的碼長：

當(dāng)r＞3，t=2 時，基于迭代矩陣構(gòu)造的BLRCs的碼長：

即相同r，t下，當(dāng)r≥t≥2 時，基于陣列LDPC碼構(gòu)造的BLRCs 的碼長始終大于基于MOLS 構(gòu)造的BLRCs 的碼長。當(dāng)r≥2，t≥2 時，直積碼的碼長始終大于基于MOLS 構(gòu)造的BLRCs 的碼長。當(dāng)r＞3，t=2 時，基于迭代矩陣構(gòu)造的BLRCs 的碼長始終大于基于MOLS構(gòu)造的BLRCs的碼長。

為了更直觀地表示表1中四種BLRCs的碼長n隨局部性r的變化趨勢，圖1 給出了可用性t=2時，碼長n隨局部性r的變化關(guān)系曲線，限于圖幅大小，局部性r取值為3 ≤r≤11。

圖1 t=2 時，碼長n 的對比分析圖

由圖1 可知，可用性t=2 時，四種BLRCs 的碼長均隨局部性r的增大而增大，且基于MOLS 構(gòu)造的BLRCs 的碼長始終小于基于陣列LDPC 碼構(gòu)造的BLRCs，直積碼和基于迭代矩陣構(gòu)造的BLRCs的碼長。證明基于MOLS構(gòu)造的BLRCs的碼長更優(yōu)。

碼率R的比較：

由表1 可知，當(dāng)r≥2，t≥2 時，基于陣列LDPC碼構(gòu)造的BLRCs的碼率：

當(dāng)r≥2，t≥2 時，直積碼的碼率：

當(dāng)r≥2，t=2 時，基于迭代矩陣構(gòu)造的BLRCs的碼率：

即相同r，t下，當(dāng)r≥2，t≥2 時，基于陣列LDPC 碼構(gòu)造的BLRCs和直積碼的碼率始終小于基于MOLS 構(gòu)造的BLRCs 的碼率。當(dāng)r≥2，t=2 時，基于迭代矩陣構(gòu)造的BLRCs 的碼率小于基于MOLS構(gòu)造的BLRCs的碼率。

為了更直觀地表示表1 中四種BLRCs 的碼率R隨局部性r的變化趨勢，圖2 給出了可用性t=2時，碼率R隨局部性r的變化關(guān)系曲線，限于圖幅大小，局部性r取值為2 ≤r≤10。

圖2 t=2 時，碼率R 的對比分析圖

由圖2 可知，可用性t=2 時，四種BLRCs 的碼率均隨局部性r的增大而增大，且r越大，碼率R的變化趨勢越緩慢。另外，基于MOLS 構(gòu)造的BLRCs 的碼率始終大于基于陣列LDPC 碼構(gòu)造的BLRCs，直積碼和基于迭代矩陣構(gòu)造的BLRCs 的碼率，且達到了Prakash 等提出的最優(yōu)碼率界。證明t=2 時，基于MOLS 構(gòu)造的BLRCs 是碼率最優(yōu)的二元局部修復(fù)碼。

5 結(jié)語

本文基于MOLS 提出一種信息符號具有(r，t)-局部性的二元局部修復(fù)碼的構(gòu)造算法。當(dāng)存儲節(jié)點故障時，構(gòu)造的BLRCs能通過t個大小至多為r的修復(fù)集進行修復(fù)。理論分析表明，該BLRCs 的最小距離滿足最優(yōu)最小距離界，是最優(yōu)的二元局部修復(fù)碼。仿真發(fā)現(xiàn)，基于MOLS 構(gòu)造的BLRCs 的碼率高于基于陣列LDPC 碼構(gòu)造的BLRCs，基于迭代矩陣構(gòu)造的BLRCs和直積碼的碼率，且可用性t=2 時，基于MOLS構(gòu)造的BLRCs的碼率達到了prakash 等提出的最優(yōu)碼率界，是碼率最優(yōu)的二元局部修復(fù)碼。除此之外，本文提出的BLRCs能通過簡單地異或運算實現(xiàn)數(shù)據(jù)的編碼，修復(fù)和并行讀取，因此對于大型分布式存儲系統(tǒng)是非常理想的。