LRC碼最小距離限的深入分析

郝曉慧，車書玲，張欣瑜

(西安電子科技大學 綜合業務網理論及關鍵技術國家重點實驗室，陜西 西安 710071)

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

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

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

1 LRC的最小距離限

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

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

定義2 最小距離(minimum distance，d): 假設u和v是碼C任意兩個非零且不相同的碼字，則碼C的最小距離d= min {d(u，v)}，d是u和v之間的漢明距離，簡單來說，C的最小距離就是C的任意兩個碼字之間不同元素數量的最小值[6]． 對于任意[n，k，d] LRC，任意d-1 個刪除節點都可以被修復．

定義3 局部性(Locality，r): 修復一個節點需要訪問的最大節點數．

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

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

d≤n-k+1 ．

(1)

定理3 Singleton-like限：[n，k，r] LRC信息位符號局部性為r時，則最小距離滿足[7]

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

(2)

定理2及定理3沒有考慮有限域的大小對最小距離限的影響，下面提供了和域相關的LRC最小距離限．

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

(3)

定理5 當[n，k，r，t] LRC有t個大小為r的不相鄰恢復集時，則最小距離滿足[9]

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

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

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

(6)

下文中用到以上各個公式時，均由定理m中的式(n)表示，m和n分別表示定理的標號和公式的標號，Singleton限及Singleton-like限仍由該名稱表示． 下面將介紹通過理論推導提出LRC的最小距離限．

2 LRC的新最小距離限

由上節的最小距離限可知，定理6中的式(6)的最小距離限是基于Singleton-like限推導出來的，但是在推導過程[10]中，存在范圍限制，并不適合所有碼字．因此，文中提出一個新的適合所有碼字的最小距離限，該限基于Singleton-like限進行推導． 在該新限基礎上，結合定理6中的式(6)的最小距離限，推導出另外一個適合一定范圍內的最小距離限．

定理7 對于任意的[n，k，r] LRC，其最小距離滿足

證明 當r|k時，由Singleton-like限得證．

當r|/k時，有

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

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

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

推論1 當nmod(r+1)≥k+k/rmod(r+1)，且r|/k時，有最小距離滿足

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時，

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

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

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

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

圖1 n=63和r=2時的仿真圖

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

證明 當k>r時，d≤n-k-k/r+2≤n-k-1+2=n-k+1，且由推論2，得證．

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

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

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

以上推論可由圖1直觀地表示出來．

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

式(6)的最小距離限: 當r|k時，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)的最小距離限．

證明 當r|/k時，0

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

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

以上推論可以由圖2直觀地表示出來．

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

從另外一個不同的角度思考時，則有以下結論．

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

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

以上推論可以由圖3直觀地表示出來．

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

推論6 當nmod(r+1)≥k+k/rmod(r+1)，且r|/k時，有

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

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

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

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

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

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

推論7可以由圖2直觀地表示出來．

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

證明 當r|/k時，式(8)可化為

推論8可以由圖4直觀地表示出來．

以上關系由表1舉例說明．

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

圖4 n=42和r=3時的仿真圖

表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 結 束 語

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

(1) 通過理論推導提出了兩個新的最小距離限，分別適用于所有碼字和一定范圍內碼字，并與已存在的限通過理論推導及仿真進行了分析比較，得出了新提出的最小距離限的優越性．

(2) 理論推導并仿真分析得出已有最小距離限間的內在聯系，為接下來對最小距離限的研究提供了一定的理論基礎．