基于MOLS 的最優(yōu)二元局部修復(fù)碼構(gòu)造*

王 娥 李靜輝 楊佳蓉

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

1 引言

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

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

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

2 基礎(chǔ)知識(shí)

2.1 局部修復(fù)碼

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

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

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

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

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

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

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

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

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

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

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

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

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

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

定義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)是一個(gè)m×s矩陣，若A的任一行是集[1，n]的一個(gè)s-排列，任一列是集[1，n]的一個(gè)m-排列，則稱A是一個(gè)m×s的拉丁矩(m≤n，s≤n)。若m=s=n，則稱A為一個(gè)n階拉丁方（Latin Square）。

定義6［18］設(shè)A=(aij)，B=(bij)是兩個(gè)不同的n階拉丁方，如果n2個(gè)有序?qū)Χ际遣煌?，則稱拉丁方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是素?cái)?shù)，α是正整數(shù)，則一定存在由n-1 個(gè)n階拉丁方組成的完備正交組。

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

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

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

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

2）令矩陣：

3）由以上定義的q+1 個(gè)矩陣Ao(o=-1，0，…q-1) 構(gòu)造(b=q2+q，v=q2，r'=q+1，k'=q，λ=1) -設(shè)計(jì)。具體的，給定q2元集X=xj(j=1，2，…，q2)，由Ao確定q2+q個(gè)區(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)，集合x(chóng)j(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前面級(jí)聯(lián)一個(gè)q2+q階單位矩陣I得到統(tǒng)一的生成矩陣G=(I|A)(q2+q)×(2q2+q)。則由生成矩陣G定義的二進(jìn)制線性碼C是信息符號(hào)具有(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)造過(guò)程。

令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)造的碼是單校驗(yàn)(n=10，k=6，r=3，t=2)i-BLRCs，最小距離d=t+1=3，碼率R=k/n=0.6 。若信息節(jié)點(diǎn)c1故障，有c1=c3+c5+c7=c4+c6+c8。因此，c1的修復(fù)集為φ1(1)={3，5，7}，φ2(1)={4，6，8}。同理，可以得到其他碼字符號(hào)的修復(fù)集。

4 性能分析

4.1 最小距離

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

將基于MOLS 構(gòu)造的信息符號(hào)具有(r=q+1，t=q) -局部性的單校驗(yàn)(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)造的單校驗(yàn)(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)碼率邊界進(jìn)行比較。

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

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

4.3 與其他碼的比較

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

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

碼長(zhǎng)n的比較：

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

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

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

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

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

圖1 t=2 時(shí)，碼長(zhǎng)n 的對(duì)比分析圖

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

碼率R的比較：

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

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

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

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

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

圖2 t=2 時(shí)，碼率R 的對(duì)比分析圖

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

5 結(jié)語(yǔ)

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