郝曉慧，車(chē)書(shū)玲，張欣瑜

(西安電子科技大學(xué) 綜合業(yè)務(wù)網(wǎng)理論及關(guān)鍵技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室，陜西 西安 710071)

在各種數(shù)據(jù)快速發(fā)展的今天，分布式存儲(chǔ)系統(tǒng)需要在保證數(shù)據(jù)的高穩(wěn)定可靠性的同時(shí)，還必須減少存儲(chǔ)花銷(xiāo)，因此數(shù)據(jù)冗余機(jī)制中最早使用的獨(dú)立磁盤(pán)冗余陣列(Redundant Array of Independent Disks， RAID)已經(jīng)不適合應(yīng)用于數(shù)據(jù)中心級(jí)的大規(guī)模部署．之后出現(xiàn)的3-副本的冗余機(jī)制可靠性高，優(yōu)化了讀性能，在數(shù)據(jù)中心級(jí)的大規(guī)模部署中多有應(yīng)用，但隨著數(shù)據(jù)的不斷增加，分布式存儲(chǔ)系統(tǒng)的不斷增大，3-副本的冗余機(jī)制需要大量的存儲(chǔ)空間來(lái)存儲(chǔ)特定的數(shù)據(jù)，造成巨大的成本壓力，不再適合應(yīng)用于大的分布式存儲(chǔ)系統(tǒng)[1]．刪除碼在分布式存儲(chǔ)系統(tǒng)中的應(yīng)用彌補(bǔ)了前面兩種機(jī)制的不足，較3-副本具有更低的成本和更高的技術(shù)含量[2-5]，雖然帶來(lái)了網(wǎng)絡(luò)負(fù)載，但是減少了額外需要冗余設(shè)備的數(shù)量，大大提高了存儲(chǔ)設(shè)備的利用效率．

局部修復(fù)碼(Locally Repairable Codes， LRCs)的提出，對(duì)刪除碼在分布式存儲(chǔ)系統(tǒng)中的研究有了進(jìn)一步的提升．對(duì)刪除碼中的LRC的研究主要分為兩類(lèi):構(gòu)造和參數(shù)分析(碼長(zhǎng)n，最小距離d，局部性r，信息位k，分組個(gè)數(shù)t等)，并討論其最佳性． 其中最小距離是衡量碼字檢錯(cuò)和糾錯(cuò)能力的依據(jù)，即碼的抗干擾能力，對(duì)LRC有重要的研究意義．文獻(xiàn)[6]介紹了Singleton限; 文獻(xiàn)[7]結(jié)合構(gòu)造算法證明了Singleton-like限; 文獻(xiàn)[8]提出了和有限域有關(guān)的最小距離限; 文獻(xiàn)[9]提出和LRC分組個(gè)數(shù)有關(guān)的最小距離限; 文獻(xiàn)[10]提出由Singleton-like限推導(dǎo)出來(lái)一定范圍碼字適用的新最小距離限．

筆者從最小距離出發(fā)，總結(jié)了已有的關(guān)于LRC的最小距離限，并基于已有的限，提出了兩種新的最小距離限，第1種新的最小距離限適用于所有碼字，第2種適用于更小范圍碼字．通過(guò)在相同碼長(zhǎng)、信息位和局部性的條件下，與已有限的分析比較得出，第1種最小距離限性能與Singleton-like限一樣好，第2種性能優(yōu)于已存在的最小距離限的結(jié)論，并給出了相應(yīng)的理論推導(dǎo)及仿真分析．

1 LRC的最小距離限

這里主要介紹有關(guān)LRC的最小距離、局部性等基本概念，以及已有的5種最小距離限，下面以定理的形式給出．

定義1 局部修復(fù)碼(LRCs)：當(dāng)[n，k，d，r] LRC的任何一個(gè)符號(hào)發(fā)生錯(cuò)誤時(shí)，只需使用本地組內(nèi)包含的其他至多r個(gè)符號(hào)即可恢復(fù)出原始數(shù)據(jù)，其中，d表示最小距離，r表示局部性．

定義2 最小距離(minimum distance，d): 假設(shè)u和v是碼C任意兩個(gè)非零且不相同的碼字，則碼C的最小距離d= min {d(u，v)}，d是u和v之間的漢明距離，簡(jiǎn)單來(lái)說(shuō)，C的最小距離就是C的任意兩個(gè)碼字之間不同元素?cái)?shù)量的最小值[6]． 對(duì)于任意[n，k，d] LRC，任意d-1 個(gè)刪除節(jié)點(diǎn)都可以被修復(fù)．

定義3 局部性(Locality，r): 修復(fù)一個(gè)節(jié)點(diǎn)需要訪(fǎng)問(wèn)的最大節(jié)點(diǎn)數(shù)．

定理1 [n，k，d]線(xiàn)性分組碼的最小距離等于d的充要條件是:H矩陣中任意d-1列線(xiàn)性無(wú)關(guān)．

定理2 Singleton限：[n，k，d]線(xiàn)性分組碼的最大可能的最小距離[6]等于n-k+1，即

d≤n-k+1 ．

(1)

定理3 Singleton-like限：[n，k，r] LRC信息位符號(hào)局部性為r時(shí)，則最小距離滿(mǎn)足[7]

d≤n-k-k/r+2 ．

(2)

定理2及定理3沒(méi)有考慮有限域的大小對(duì)最小距離限的影響，下面提供了和域相關(guān)的LRC最小距離限．

定理4q元[n，k，r] LRC的最小距離[8]滿(mǎn)足

(3)

定理5 當(dāng)[n，k，r，t] LRC有t個(gè)大小為r的不相鄰恢復(fù)集時(shí)，則最小距離滿(mǎn)足[9]

由定理3，可推出下面定理6中的最小距離限．

定理6 [n，k，r] LRC的最小距離在nmod(r+1)≥k+k/rmod(r+1)情況下滿(mǎn)足[10]

d≤n-k-n/(r+1)+2+(n-k-n/(r+1))/r．

(6)

下文中用到以上各個(gè)公式時(shí)，均由定理m中的式(n)表示，m和n分別表示定理的標(biāo)號(hào)和公式的標(biāo)號(hào)，Singleton限及Singleton-like限仍由該名稱(chēng)表示． 下面將介紹通過(guò)理論推導(dǎo)提出LRC的最小距離限．

2 LRC的新最小距離限

由上節(jié)的最小距離限可知，定理6中的式(6)的最小距離限是基于Singleton-like限推導(dǎo)出來(lái)的，但是在推導(dǎo)過(guò)程[10]中，存在范圍限制，并不適合所有碼字．因此，文中提出一個(gè)新的適合所有碼字的最小距離限，該限基于Singleton-like限進(jìn)行推導(dǎo)． 在該新限基礎(chǔ)上，結(jié)合定理6中的式(6)的最小距離限，推導(dǎo)出另外一個(gè)適合一定范圍內(nèi)的最小距離限．

定理7 對(duì)于任意的[n，k，r] LRC，其最小距離滿(mǎn)足

證明 當(dāng)r|k時(shí)，由Singleton-like限得證．

當(dāng)r|/k時(shí)，有

根據(jù)(d+1/r-2)/(r+1)-1/r及n/(r+1)分別是整數(shù)、小數(shù)分為4種情況，驗(yàn)證每一種情況，可得

d-2-(d+1/r-2)/(r+1)-1/r≤n-k-n/(r+1)．

根據(jù)(d+1/r-2)/(r+1)-1/r分別是整數(shù)、小數(shù)分為兩種情況，由d-2為整數(shù)，可得

推論1 當(dāng)nmod(r+1)≥k+k/rmod(r+1)，且r|/k時(shí)，有最小距離滿(mǎn)足

d≤n-k-n/(r+1)+2+(n-k-n/(r+1)-1)/r．

(9)

證明 由式(8)，同定理6，有nmod(r+1)≥k+k/rmod(r+1)，且r|/k時(shí)，

3 LRC的最小距離限的分析比較

這里將對(duì)上兩節(jié)中給出的各種LRC的最小距離限從不同角度進(jìn)行分析和比較，其內(nèi)容進(jìn)一步分成兩個(gè)部分: 第1部分是已有LRC最小距離限之間關(guān)系的分析比較；第2部分是新提出的最小距離限與已有限之間關(guān)系的分析比較，分別得出新提出的最小距離限存在的優(yōu)越性，并以仿真圖的形式形象描述它們之間的關(guān)系．

3.1 Singleton限、Singleton-like限、定理5中的式(5)的最小距離限及定理6中的式(6)的最小距離限的分析比較

推論2 在GF(q)域上，相同n，k，r，t時(shí)，Singleton-like限和定理5中的式(5)的最小距離限相同[7]．

圖1 n=63和r=2時(shí)的仿真圖

推論3 當(dāng)k>r時(shí)，Singleton限始終大于Singleton-like限[7]及定理5中的式(5)的最小距離限．

證明 當(dāng)k>r時(shí)，d≤n-k-k/r+2≤n-k-1+2=n-k+1，且由推論2，得證．

推論4 Singleton-like限與定理6中的式(6)的最小距離限存在一定的關(guān)系，可分為以下3種情況:

(1)r+1|n，r≥1，Singleton-like限等于定理6中的式(6)的最小距離限．

證明 由式(6)的定義范圍可知[10]，當(dāng)r+1|n時(shí)，有r|k．

以上推論可由圖1直觀(guān)地表示出來(lái)．

(2)r+1|/n，r|k，Singleton-like限等于定理6中的式(6)的最小距離限加1．

式(6)的最小距離限: 當(dāng)r|k時(shí)，k+k/rmod(r+1)=k+ (k/r) mod(r+1)=k[(r+1)/r] mod(r+1)= 0，則nmod(r+1)≥ 0，即 0

(3)r+1|/n，r|/k， Singleton-like限等于定理6中的式(6)的最小距離限．

證明 當(dāng)r|/k時(shí)，0

由上述范圍，式(6)可化為d≤n-k+2+n/r-(1+1/r)n/(r+1)-k/r，式(6)減去Singleton-like限，得

由推論4可知，當(dāng)r+1|n，和r+1|/n，r|/k時(shí)，Singleton-like限等于定理6中的式(6)的最小距離限，當(dāng)r+1|/n，r|k時(shí)，定理6中的式(6)的最小距離限更緊．

以上推論可以由圖2直觀(guān)地表示出來(lái)．

圖2 n=63和r=5時(shí)的仿真圖圖3 10≤n≤120,R=2/5,r=3時(shí)的仿真圖

從另外一個(gè)不同的角度思考時(shí)，則有以下結(jié)論．

推論5 碼率R=k/n，如果R可以化簡(jiǎn)為如下形式:R=m/(r+1)，且gcd(m，r+1)=1，其中m可為任意正整數(shù)，則此時(shí)Singleton-like 限等于定理6中的式(6)的最小距離限．

證明 給定碼率R及r，R=k/n=m/(r+1)，則(r+1)|n，gcd(m，r+1)=1，m與r+1互質(zhì)，是保證碼率的分母只能為r+1，在這種情況下，和推論4的情況(1)相同．

以上推論可以由圖3直觀(guān)地表示出來(lái)．

3.2 新提出的定理7中的式(8)、推論1中的式(9)與已有的Singleton-like 限、定理6中的式(6)的最小距離限的分析比較

推論6 當(dāng)nmod(r+1)≥k+k/rmod(r+1)，且r|/k時(shí)，有

(1) 當(dāng)r|(n-k-n/(r+1)-1)時(shí)，式(8)的最小距離限等于式(9)的最小距離限;

(2) 當(dāng)r|/(n-k-n/(r+1)-1)時(shí)，式(8)的最小距離限等于式(9)的最小距離限加1．

證明 將上述條件分別代入式(8)及式(9)，根據(jù)上下取整關(guān)系，得證．

推論7 推論1中的式(9)及定理6中的式(6)中的最小距離限滿(mǎn)足nmod(r+1)≥k+k/rmod(r+1) 時(shí)，有

(1) 當(dāng)r|/k，且r|(n-k-n/(r+1))時(shí)，式(9)中的最小距離限等于式(6)中的最小距離限減1;

(2) 當(dāng)r|/k，且r|/(n-k-n/(r+1))時(shí)，式(9)中的最小距離限等于式(6)中的最小距離限．

推論7可以由圖2直觀(guān)地表示出來(lái)．

推論8 對(duì)于r|/k條件下的[n，k，r] LRC， Singleton-like 限與定理7中的式(8)的最小距離限相等．

證明 當(dāng)r|/k時(shí)，式(8)可化為

推論8可以由圖4直觀(guān)地表示出來(lái)．

以上關(guān)系由表1舉例說(shuō)明．

表1 n=20，不同k及r情況下，Singleton-like限和式(6)、式(8)、式(9)中最小距離限的緊程度

圖4 n=42和r=3時(shí)的仿真圖

表1中S和9分別表示在n，k，r情況下，Singleton-like限、推論1中的式(9)的最小距離限是最緊的；S/6、S/8、S/6/8分別表示在n，k，r情況下，定理6中的式(6)的最小距離限等于Singleton-like限、定理7中的式(8)的最小距離限等于Singleton-like限、定理6中的式(6)的最小距離限等于Singleton-like限并等于定理7中的式(8)的最小距離限，即一樣緊．

4 結(jié) 束 語(yǔ)

筆者通過(guò)對(duì)LRC最小距離限的研究，提出了適合于一定碼字的最小距離限，提供了判斷最小距離最佳性的新限，分析了已有限之間存在的內(nèi)在聯(lián)系，具體成果如下:

(1) 通過(guò)理論推導(dǎo)提出了兩個(gè)新的最小距離限，分別適用于所有碼字和一定范圍內(nèi)碼字，并與已存在的限通過(guò)理論推導(dǎo)及仿真進(jìn)行了分析比較，得出了新提出的最小距離限的優(yōu)越性．

(2) 理論推導(dǎo)并仿真分析得出已有最小距離限間的內(nèi)在聯(lián)系，為接下來(lái)對(duì)最小距離限的研究提供了一定的理論基礎(chǔ)．