王 靜，田松濤，雷 珂，王相隆，任亞倩

(1. 長安大學(xué)信息工程學(xué)院 西安 710064；2. 西安郵電大學(xué)通信與信息工程學(xué)院 西安 710199)

隨著全球互聯(lián)網(wǎng)的全面普及，海量數(shù)據(jù)隨之產(chǎn)生，如何高效地管理和可靠地存儲海量數(shù)據(jù)成為當(dāng)前的研究熱點。海量數(shù)據(jù)主要采用分布式存儲系統(tǒng)，為了維護系統(tǒng)的可用性和可靠性需引入冗余策略，最常見的冗余策略有復(fù)制策略和糾刪碼策略[1]，但都存在一定的局限性。隨后，文獻[2]將網(wǎng)絡(luò)編碼應(yīng)用到分布式存儲系統(tǒng)中，提出了再生碼的概念。再生碼雖然在一定程度上減小了修復(fù)帶寬開銷，但修復(fù)故障節(jié)點過程中需連接大量存活節(jié)點，增加了系統(tǒng)的磁盤I/O 開銷。

為了解決上述問題，文獻[3]提出了局部修復(fù)碼(locally repairable codes, LRC)，有效降低了故障節(jié)點的修復(fù)局部性。文獻[4]研究了信息位具有局部性和可用性的局部修復(fù)碼的最小距離限，但關(guān)于修復(fù)局部性的邊界條件沒有研究。進一步地，文獻[5-6]分別研究了局部修復(fù)碼的構(gòu)造并且協(xié)作局部修復(fù)碼，降低了存儲開銷并降低了修復(fù)局部性。文獻[7]研究了局部性為2 且可用性不等時的局部修復(fù)碼。

最小距離和碼率是衡量局部修復(fù)碼性能的兩個主要性能指標(biāo)[8]，其中最小距離最優(yōu)的局部修復(fù)碼一般簡稱為最優(yōu)局部修復(fù)碼。文獻[9]利用射影平面和仿射平面理論構(gòu)造了3 種局部性和可用性相等的局部修復(fù)碼，達到了最優(yōu)最小距離邊界?；诓糠謳缀螛?gòu)造的最優(yōu)局部修復(fù)碼[10]，通過交換點集和線集的關(guān)聯(lián)結(jié)構(gòu)得到部分幾何的對偶，進而構(gòu)造局部性和可用性不等的局部修復(fù)碼?；贕ilbert 方法的最優(yōu)二元單校驗局部修復(fù)碼[11]，通過結(jié)合循環(huán)置換矩陣構(gòu)造了一種新的LDPC 碼，將其與單位矩陣級聯(lián)形成校驗矩陣，進而構(gòu)造出滿足最小距離界的二元單校驗局部修復(fù)碼。這3 種構(gòu)造出的局部修復(fù)碼都可達到最優(yōu)最小距離邊界，但是碼率較小。

除最小距離和碼率之外，在局部修復(fù)碼中也考慮維度這一參數(shù)。有學(xué)者基于生成矩陣、校驗矩陣和圖論相關(guān)理論構(gòu)造局部修復(fù)碼來提高碼率，但都沒有分析維度是否達到維度最優(yōu)的邊界條件。文獻[12]使用組合設(shè)計構(gòu)造了最優(yōu)二元局部修復(fù)碼，運用BIBD 和DBBD 區(qū)組設(shè)計構(gòu)造出的局部修復(fù)碼在碼率上更優(yōu)，但碼長略大。文獻[13]使用打包設(shè)計構(gòu)造了最優(yōu)局部修復(fù)碼，限制了碼長和維度的參數(shù)條件，無法靈活地構(gòu)造不同情況下的局部修復(fù)碼。文獻[14]構(gòu)造了最優(yōu)單校驗二元局部修復(fù)碼，但其維度沒有達到維度最優(yōu)的邊界條件。利用圖論相關(guān)理論來構(gòu)造局部修復(fù)碼，主要是從二分圖的角度出發(fā)構(gòu)造二元局部修復(fù)碼[15-16]，雖然能達到最優(yōu)最小距離，但是構(gòu)造算法略復(fù)雜。

針對以上問題，本文提出一種基于Hadamard矩陣的最優(yōu)局部修復(fù)碼的構(gòu)造方法。首先基于Hadamard 矩陣構(gòu)造局部修復(fù)碼的校驗矩陣，通過校驗矩陣構(gòu)造局部修復(fù)碼，構(gòu)造的局部修復(fù)碼能達到最優(yōu)最小距離界，但是維度沒有達到最優(yōu)維度邊界條件。為了進一步提高維度，將校驗矩陣中的關(guān)聯(lián)矩陣0 和1 元素互換得到新的關(guān)聯(lián)矩陣，通過和新的關(guān)聯(lián)矩陣級聯(lián)進行擴展，構(gòu)造的擴展局部修復(fù)碼不僅能達到最優(yōu)最小距離界，且能達到維度最優(yōu)的邊界條件。此外，基于Hadamard 矩陣構(gòu)造的擴展局部修復(fù)碼的碼率也更逼近局部修復(fù)碼最優(yōu)碼率的邊界，參數(shù)選擇更加靈活。

局部修復(fù)碼作為廣義上的糾錯碼，適用于分布式存儲系統(tǒng)。分布式存儲系統(tǒng)中存儲的文件采用局部修復(fù)碼進行編碼，并將編碼后的信息存于存儲節(jié)點中。當(dāng)有部分存儲節(jié)點故障，則可以利用其余存活節(jié)點修復(fù)故障節(jié)點，實現(xiàn)分布式存儲系統(tǒng)中數(shù)據(jù)的可靠存儲。本節(jié)主要介紹局部修復(fù)碼的一些相關(guān)原理。

1.1 ( r,t)可用性

定義1[8]在有限域Fq上的 [n,k,d]q線性分組碼中，給定[n]={1,2,···,n} ， 碼字c=(c1,c2,···,cn)。如果其中一個編碼符號ci具 有局部性r和可用性t，需滿足下列條件：

稱φj(i)(j∈[t])為ci的修復(fù)集合。如果局部修復(fù)碼的所有信息位碼元都具有 (r,t)可用性，那么稱該碼為具有 (r,t)可 用性的局部修復(fù)碼，記作(n,k,r,t)iLRC。若每個信息位碼元的每個修復(fù)集只有一個校驗位碼元，則這個碼稱作單校驗 (n,k,r,t)iLRC。本文主要研究單校驗 (n,k,r,t)iLRC，該碼由關(guān)聯(lián)矩陣和單位矩陣拼接而成，其中關(guān)聯(lián)矩陣的行重為局部性r，列重為可用性t。

1.2 最小距離

定理1[10]若一個線性分組碼C是信息位具有局部性r和可用性t的局部修復(fù)碼，最小距離應(yīng)滿足：

定理2[13]若局部修復(fù)碼的所有信息位碼元的每一個修復(fù)集中只含有一個校驗位，且該單校驗(n,k,r,t)iLRC 的最小距離滿足：

1 局部修復(fù)碼相關(guān)概念

稱達到邊界(2)的局部修復(fù)碼是最小距離最優(yōu)的單校驗(n,k,r,t)iLRC。

1.3 碼率和維度

一般地，每個碼的信息位個數(shù)k與碼元數(shù)n之間的比值稱作碼率，用R=k/n表示。

定理3[17]若 (n,k,r,t) L RC 具有 (r,t)可用性，且該碼碼率滿足：

則達到邊界(3)的局部修復(fù)碼的碼率最優(yōu)。

定理 4[18]特別地，可用性t=2的最優(yōu)碼率的(n,k,r,t=2)單校驗局部修復(fù)碼滿足的碼率邊界條件為：

定理 5[19](維度C-M 邊界限)在有限域GF(q)中的(n,k,r)單校驗局部修復(fù)碼的維度應(yīng)滿足：

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

2.1 基于Hadamard 矩陣的局部修復(fù)碼構(gòu)造

構(gòu)造基于Hadamard 矩陣的局部修復(fù)碼，關(guān)鍵在于構(gòu)造局部修復(fù)碼的校驗矩陣。局部修復(fù)碼的校驗矩陣用H=[M|I]表 示，I是單位矩陣，單位矩陣的列對應(yīng)局部修復(fù)碼的校驗位符號；M是對應(yīng)的關(guān)聯(lián)矩陣，關(guān)聯(lián)矩陣的列對應(yīng)信息位符號。碼字和校驗矩陣的關(guān)系為c·H⊥=0，通過此關(guān)系可知每個信息位碼字的修復(fù)集，一個基于校驗矩陣構(gòu)造的具有可用性(r,t)的 局部修復(fù)碼，它的關(guān)聯(lián)矩陣的行重r用來保證局部性，列重t用來保證可用性。

本節(jié)主要基于Hadamard 矩陣構(gòu)造關(guān)聯(lián)矩陣，關(guān)聯(lián)矩陣級聯(lián)單位矩陣生成校驗矩陣，通過校驗矩陣來構(gòu)造局部修復(fù)碼。

定義2k′階 方陣Hk′，若其元素為1 或-1，且滿足：

稱Hk′為k′階 Hadamard 矩陣，其中Ik′是k′階單位陣。

若Hk′首 行首列均為全1 向量，則該Hk′為標(biāo)準(zhǔn)Hadamard 矩陣。本文所涉及的Hadamard 矩陣均為標(biāo)準(zhǔn)Hadamard 矩陣。

5) 將矩陣H(2k′-1)×(4k′-2)作為局部修復(fù)碼的校驗矩陣，構(gòu)造得到(n=4k′-2,k=2k′-1,r=k′,t=k′)局部修復(fù)碼，其中可用性t為2 的倍數(shù)。

推論1 構(gòu)造1 中(n=4k′-2,k=2k′-1,r=k′,t=k′)局部修復(fù)碼為最小距離最優(yōu)的局部修復(fù)碼，且碼的最小距離d=t+1。

證 明：將 (n=4k′-2,k=2k′-1,r=k′,t=k′)局部修復(fù)碼的參數(shù)代入邊界條件(2)，有：

因 為k′=t，則d≤t+1。 又 根 據(jù) 式(1)得d≥t+1， 所以d=t+1，可得到基于Hadamard 矩陣構(gòu)造的局部修復(fù)碼的最小距離d=t+1，滿足邊界條件(2)，則該碼是最小距離最優(yōu)的局部修復(fù)碼。

構(gòu)造1 中的局部修復(fù)碼的碼率R=n k= 1

2，沒有達到式(3)中最優(yōu)碼率的邊界條件，故該碼不是碼率最優(yōu)的局部修復(fù)碼。

例1 令k′=4，得到方陣：

利用步驟 2) 可得到M8×8， 將M8×8的首行和首列全部刪除，得到一個7 階的關(guān)聯(lián)矩陣M7×7：

2.2 基于Hadamard 矩陣的擴展局部修復(fù)碼構(gòu)造

上述基于Hadamard 矩陣構(gòu)造的局部修復(fù)碼的局部性和可用性相等，且能夠達到最優(yōu)最小距離界，但是該局部修復(fù)碼的碼率較小，沒有達到維度最優(yōu)的邊界條件。為了進一步提高碼率和維度，將上述構(gòu)造中的關(guān)聯(lián)矩陣M(2k′-1)×(2k′-1)進行擴展，得到碼率更高并且維度最優(yōu)的擴展局部修復(fù)碼。

構(gòu)造2 基于Hadamard 矩陣的擴展局部修復(fù)碼的具體構(gòu)造步驟如下。

1) 首先將Hadamard 矩陣的1 元素全部換為0 元素，-1 元素全部換為1 元素，得到一個k′階方陣，記為Mk′×k′；

2) 根據(jù)k′階 方陣Mk′×k′構(gòu)造：

最后將M8×14作為擴展局部修復(fù)碼的關(guān)聯(lián)矩陣，和 單 位 矩 陣I8級 聯(lián) 生 成 校 驗 矩 陣H8×22=[M8×14|I8]， 由 此 可 構(gòu) 造 出 單 校 驗(n=22,k=14,r=7,t=4)局 部修復(fù)碼，此碼的最小距離d=5，碼率R=7/11，與構(gòu)造1 相比，有效地提高了局部修復(fù)碼的碼率。

故障節(jié)點的修復(fù)方法為：若信息位c1發(fā)生故障，由c·HT=0 可知，信息位c1可 根據(jù)c1=c15-c3-c5-c7-c9-c11-c13=c17-c2-c5-c6-c10-c11-c14=c19-c3-c4-c6-c9-c12-c14=c21-c2-c4-c7-c10-c12-c13進 行修復(fù)，那么信息位c1的修復(fù)集可表示為φ1={3,5,7,9,11,13,15} ，φ2={2,5,6,10,11,14,17} ，φ3={3,4,6,9,12,14,19} 和φ4={2,4,7,10,12,13,21}，各 個修復(fù)集都只有一個校驗位符號。同理，其他信息位符號也可用相同的方法進行修復(fù)。

3 性能分析

3.1 最小距離和維度分析

推論2 構(gòu)造2 得到的(n=6k′-2,k=4k′-2,r==2k′-1,t=k′)局部修復(fù)碼是最小距離最優(yōu)的局部修復(fù)碼，且碼的最小距離d=t+1。

證明：將(n=6k′-2,k=4k′-2,r=2k′-1,t=k′)局部修復(fù)碼的參數(shù)代入邊界條件(2)，可得：

因為k′=t，即d≤t+1。 又根據(jù)式(1)得d≥t+1，所以d=t+1，可以得到構(gòu)造2 中的局部修復(fù)碼的最小距離d=t+1。該局部修復(fù)碼的最小距離滿足邊界條件(2)，則該碼是最小距離最優(yōu)的局部修復(fù)碼。

推論3 構(gòu)造2 得到的(n=6k′-2,k=4k′-2,r=2k′-1,t=k′)局部修復(fù)碼是維度最優(yōu)的局部修復(fù)碼，且碼的維度k≤4k′-2。

證明：當(dāng)式(1)中最小距離d為最大值時，可以將式(5)簡化如下：

將(n=6k′-2,k=4k′-2,r=2k′-1,t=k′)LRC 的參數(shù)條件代入簡化的公式中，可得k≤4k′-2，對于?k′，基于Hadamard 矩陣構(gòu)造的擴展局部修復(fù)碼的維度都可達到最優(yōu)維度邊界條件的上界。

3.2 與現(xiàn)有局部修復(fù)碼的對比分析

基于Hadamard 矩陣構(gòu)造的擴展局部修復(fù)碼的碼率為：

則本文構(gòu)造2 中局部修復(fù)碼的碼率大于基于直積碼構(gòu)造的局部修復(fù)碼碼率。

表1 不同局部修復(fù)碼參數(shù)對比

圖1 所示為t=4時，不同局部修復(fù)碼的碼率R隨著局部性r的變化曲線，也容易看出構(gòu)造2 的碼率是最逼近局部修復(fù)碼最優(yōu)碼率界限的。

圖1 t =4情 況下，碼率R 的對比

表2 不同局部修復(fù)碼關(guān)于維度參數(shù)的對比

4 結(jié) 束 語

為了滿足在最優(yōu)最小距離邊界條件下，局部修復(fù)碼的維度也能達到最優(yōu)，本文首先構(gòu)造了基于Hadamard 矩陣的局部修復(fù)碼，此局部修復(fù)碼能達到最優(yōu)最小距離界，但是維度沒有達到維度最優(yōu)的邊界條件。為了提高維度，將校驗矩陣中的關(guān)聯(lián)矩陣0 和1 元素互換得到新的關(guān)聯(lián)矩陣，通過和新的關(guān)聯(lián)矩陣級聯(lián)進行擴展，構(gòu)造的擴展局部修復(fù)碼不僅能達到最優(yōu)最小距離界，且能達到維度最優(yōu)的邊界條件。將基于Hadamard 矩陣構(gòu)造的擴展局部修復(fù)碼和現(xiàn)有的局部修復(fù)碼相比，本文的構(gòu)造在碼率上更逼近局部修復(fù)碼最優(yōu)碼率的界限。

本文得到長安大學(xué)大學(xué)生創(chuàng)新創(chuàng)業(yè)訓(xùn)練計劃項目(G202010710031)資助，在此深表感謝！