High-rate codes with sublinear-time decoding
High-rate codes with sublinear-time decoding
复制标题
具有亚线性时间解码的高速率代码
DOI：
10.1145/2629416
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
S. Yekhanin
中科院分区：
文献类型：
--
作者：
Swastik Kopparty;Shubhangi Saraf;S. Yekhanin
本地可解码的代码是允许有效解码算法的错误代码；在解码算法中，它已经进行了很好的研究，并且人们一直怀疑非平凡的地方必须以低利率的价格出现。对于此类代码，使用位置O（k∈）的恒定速率仅针对速率代码∈Ω（1/∈），其中k是消息的长度。 ，在本文中没有实现非平凡的位置，我们构建了一个具有非常有效的局部解码算法的局部可解码代码，同时速率接近1。 0，无限许多K存在一个代码C，该代码C用速率为1 -α编码长度k的消息，并且可以使用O（k∈）查询和时间来局部解码错误。基于评估多元多项式及其衍生物。速率和最小距离。
Locally decodable codes are error-correcting codes that admit efficient decoding algorithms; any bit of the original message can be recovered by looking at only a small number of locations of a corrupted codeword. The tradeoff between the rate of a code and the locality/efficiency of its decoding algorithms has been well studied, and it has widely been suspected that nontrivial locality must come at the price of low rate. A particular setting of potential interest in practice is codes of constant rate. For such codes, decoding algorithms with locality O(k∈) were known only for codes of rate ∈Ω(1/∈), where k is the length of the message. Furthermore, for codes of rate > 1/2, no nontrivial locality had been achieved. In this article, we construct a new family of locally decodable codes that have very efficient local decoding algorithms, and at the same time have rate approaching 1. We show that for every ∈ > 0 and α > 0, for infinitely many k, there exists a code C which encodes messages of length k with rate 1 − α, and is locally decodable from a constant fraction of errors using O(k∈) queries and time. These codes, which we call multiplicity codes, are based on evaluating multivariate polynomials and their derivatives. Multiplicity codes extend traditional multivariate polynomial codes; they inherit the local-decodability of these codes, and at the same time achieve better tradeoffs and flexibility in the rate and minimum distance.