Improved schemes for asymptotically optimal repair of MDS codes
Improved schemes for asymptotically optimal repair of MDS codes
复制标题
DOI：
10.1109/allerton.2017.8262840
复制
发表时间：
2017-10
期刊：
影响因子：
--
通讯作者：
Ameera Chowdhury;A. Vardy
中科院分区：
文献类型：
--
作者：
Ameera Chowdhury;A. Vardy
在有限域\(F\)上，一个长度为\(n\)、维度为\(k\)且子分组化级别为\(l\)的\((n,k,l)\)MDS码是\(F\)上\(n\)个长度为\(l\)的符号向量的集合，其具有任何\(k\)个向量都能恢复\(kl\)个符号的全部数据这一性质。当一个节点失效时，我们可以通过从幸存节点下载符号来恢复它，在最坏情况下下载的符号总数就是该码的修复带宽。根据割集界，\((n,k,l)\)MDS码的修复带宽至少为\((n - 1)l/(n - k)\)。有几种\((n,k,l)\)MDS码的构造，其修复带宽达到或渐近达到割集界。令\(r = n - k\)表示校验符号的数量，Ye和Barg构造了渐近达到割集界的\((n,k,rn)\)里德 - 所罗门码。Ye和Barg还构造了最优带宽和最优更新的\((n,k,rn)\)MDS码。这些构造中的一个关键思想是在基数\(r\)下展开整数。我们在本文中表明，当\(r\)是一个整数幂时，我们可以在实现渐近最优修复带宽的同时显著降低Ye - Barg构造的子分组化级别。例如，当\(r = 2^m\)时，我们实现了子分组化级别为\(2^{m + n - 1}\)，这比Ye - Barg构造中的\(2^{mn}\)的子分组化级别有所改进。一般来说，当\(r = s^m\)（\(s\geq2\)为整数）时，我们的码具有子分组化级别\(l = s^{m + n - 1}=r^{s^{n - 1}}\)。具体地，在\(r = s^m\)的情况下，我们得到一个\((n,k,s^{m + n - 1})\)里德 - 所罗门码和一个最优更新的\((n,k,s^{m + n - 1})\)MDS码，它们都具有渐近最优修复带宽。为了得到这些结果，我们扩展和推广了Ye - Barg构造中的\(r\)进制展开思想。即使当\(r\)不是一个整数幂时，我们仍然可以通过选择正整数\(s\)和\(m\)使得\(s^m\leq r\)来获得\((n,k,s^{m + n - 1})\)里德 - 所罗门码和最优更新的\((n,k,s^{m + n - 1})\)MDS码。然而，在这种情况下，所得的码具有接近最优而非渐近最优的带宽。
An (n, k, l) MDS code of length n, dimension k and sub-packetization l over a finite field F is a set of n symbol vectors of length l over F with the property that any k vector can recover the entire data of kl symbols. When a node fails we can recover it by downloading symbols from the surviving nodes, and the total number of symbols downloaded in th worst case is the repair bandwidth of the code. By the cut-se bound, the repair bandwidth of an (n, k, l) MDS code is at leas (n − 1)l/(n − k). There are several constructions of (n, k, l) MDS codes whose repair bandwidths meet or asymptotically meet the cut-se bound. Letting r = n − k denote the number of parities Ye and Barg constructed (n, k, rn) Reed-Solomon codes the asymptotically meet the cut-set bound. Ye and Barg also constructed optimal bandwidth and optimal update (n, k, rn MDS codes. A key idea in these constructions is to expand integers in base r. We show in this paper that, when r is an integral power, w can significantly reduce the sub-packetization of the Ye-Barg constructions while achieving asymptotically optimal repair bandwidth. As an example, when r = 2m, we achieve the sub-packetization of 2m+n−1, which improves upon the sub packetization of 2mn in the Ye-Barg constructions. In general when r = sm for an integer s 2, our codes have sub packetization l = sm+n−1 = rsn−1. Specifically, in the casi r = sm, we obtain an (n, k, sm+n=1) Reed-Solomon code an an optimal update (n, k, sm+n−1) MDS code, which both have asymptotically optimal repair bandwidth. In order to obtain these results, we extend and generalize the r-ary expansion idea in the Ye-Barg constructions. Even when r is not an integral power, we can still obtain (n, k, sm+n−1) Reed-Solomon codes and optimal update (n, k, sm+n−1) MDS codes by choosing positive integers s an m such that sm r. In this case, however, the resulting codes have bandwidth that is near-optimal rather than asymptotically optimal.