基于MOLS 的最優二元局部修復碼構造*

王 娥 李靜輝 楊佳蓉

（長安大學 西安 710064）

1 引言

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

目前有許多學者對(n，k，r)局部修復碼展開研究。Tamo 等［9］基于Reed-Solomon 編碼塊構造了一種最小距離最優的局部修復碼，但是該碼不能在較小的有限域上實現，其編碼和修復復雜度較高。Wang 等［10］基于球面填充方法推導出(n，k，r)二元局部修復碼的維度k的上界，并將邊界和碼的構造擴展到了q元域上，但是構造的碼既沒有實現最小距離最優也沒有實現碼率最優。Chen 等［11］利用常環MDS 碼構造了七類具有新參數的最優(r，δ)-局部修復碼，但是該碼的參數選擇不夠靈活。……