Nonlinear Repair of Reed-Solomon Codes
Nonlinear Repair of Reed-Solomon Codes
复制标题
Reed-Solomon 码的非线性修复
DOI：
10.1109/tit.2022.3167615
复制
发表时间：
2021
影响因子：
2.5
通讯作者：
Itzhak Tamo
中科院分区：
文献类型：
--
作者：
Roni Con;Itzhak Tamo
修复线性代码，尤其是Reed所罗门（RS）代码的问题近年来引起了很多关注，因为它们对分布式存储系统的极为重要。在此问题中，需要通过从其余节点的子集中下载尽可能少的信息来修复失败的代码符号（节点）。到目前为止，有一些RS代码具有有效修复方案的例子，有些甚至达到了切割式结合。但是，这些方案在几个方面都缺乏。他们需要相当大的现场扩展学位。他们没有在主要领域提供任何非平凡维修计划。最后，它们都是线性维修，即计算的函数在基础场上是线性的。由Guruswami and Wootters（2017年）关于非线性修复方案的力量提出的一个问题，我们研究了RS代码的非线性修复方案的问题。我们的主要结果是具有渐近最佳修复带宽的RS代码的第一个非线性修复方案（渐近与切割机结合匹配）。这是任何代码的非线性修复方案的第一个示例，也是非线性维修方案胜过所有线性的第一个示例。最后，我们证明，使用加法组合制剂的想法证明了更严格的界限，用于RS代码的剪辑键在Prime字段上并不紧张。
The problem of repairing linear codes and, in particular, Reed Solomon (RS) codes has attracted a lot of attention in recent years due to their extreme importance to distributed storage systems. In this problem, a failed code symbol (node) needs to be repaired by downloading as little information as possible from a subset of the remaining nodes. By now, there are examples of RS codes that have efficient repair schemes, and some even attain the cut-set bound. However, these schemes fall short in several aspects; they require a considerable field extension degree. They do not provide any nontrivial repair scheme over prime fields. Lastly, they are all linear repairs, i.e., the computed functions are linear over the base field. Motivated by these and by a question raised by Guruswami and Wootters, 2017, on the power of nonlinear repair schemes, we study the problem of nonlinear repair schemes of RS codes. Our main results are the first nonlinear repair scheme of RS codes with asymptotically optimal repair bandwidth (asymptotically matching the cut-set bound). This is the first example of a nonlinear repair scheme of any code and also the first example that a nonlinear repair scheme can outperform all linear ones. Lastly, we show that the cut-set bound for RS codes is not tight over prime fields by proving a tighter bound, using additive combinatorics ideas.