一類最優局部修復碼的構造

蔣靜 王金玉

摘 ? 要：有多個互不相交修復集合的局部修復碼是一類很重要的能應用于提高分布式存儲系統修復效率的碼。本文利用多種組合結構，如填充、平衡不完全區組設計等，構造了參數較小的最優局部修復碼，其中每一個修復集合至多包含4個元素且恰有一個是校驗元。

關鍵詞：局部修復碼 ?分布式存儲系統 ?填充 ?平衡不完全區組設計

中圖分類號：TN911 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 文獻標識碼：A ? ? ? ? ? ? ? ? ? ? ? 文章編號：1674-098X（2019）02（a）-0088-05

在大數據環境下，分布式存儲系統被應用于海量數據的存儲。在分布式存儲系統中，原始數據被分成k個等大小的片段，然后被編碼成n個片段存儲在n個不同的節點中，使得當要修復1個節點時，我們只需連接其中部分節點。根據實際需求選用特定的編碼是分布式存儲的一項關鍵技術，其中用到的局部修復碼是近幾年非常熱門的一個研究方向。最近，Cai等[1]在假設每個節點有多個修復集合，且每一個修復集合只包含一個校驗元的前提下，利用組合結構填充（packing）構造了一些最優局部修復碼的無窮類。本文基于文獻[1]的結果，利用多種組合結構構造了若干最優局部修復碼。

1 ?相關概念

1.1 局部修復碼

定理1的證明：由推論1-4和引理7-8可知，存在一個（δ-1）-正則（k，R，1）-填充，其中（k，δ-1，R）的值為表1中列出的值。由引理1可知，存在一個擁有局部信息（r，δ，1）c的最優對稱碼。

2 ?結語

本文基于文獻[1]的結果，構造了當k（δ-1）≡0，3（mod 4）且k≤20時，擁有局部信息（4，δ，1）c的最優對稱碼。本文方法也可以用于構造k>21時的最優局部修復碼，但這樣的局部修復碼結構較復雜、相應的構造也更加困難，需要對構造方法做進一步地改進。

參考文獻

[1] Cai H， Cheng M， Fan C， et al. Optimal Locally Repairable Systematic Codes Based on Packings[J]. IEEE Transactions on Communications， 2019， 67（1）： 39-49.

[2] Huang C， Chen M， Li J. Pyramid Codes： Flexible Schemes to Trade Space for Access Efficiency in Reliable Data Storage Systems[J]. ACM Transactions on Storage， 2013， 9（1）：3.

[3] Wang A， Zhang Z. Repair Locality with Multiple Erasure Tolerance[J]. IEEE Transactions on Information Theory， 2014， 60（11）： 6979-6987.

[4] Rawat A S， Papailopoulos D S， Dimakis A G， et al. ?Locality and Availability in Distributed Storage[J]. IEEE Transactions on Information Theory， 2016， 62（8）： 4481-4493.

[5] Chung H， Kumar P V. Optical Orthogonal Codes-New Bounds and an Optimal Construction [J]. IEEE Transactions on Information Theory， ?1990， 36（4）： 866-873.

[6] Yin J. Some Combinatorial Constructions for Optical Orthogonal Codes[J]. Discrete Mathematics， 1998， 185（1-3）： 201-219.

[7] Colbourn C J， ? Dinitz J H. Handbook of Combinatorial Designs[M]， Chapman & Hall/CRC， vol. 42， 2006.