Linear time encodable and list decodable codes
Linear time encodable and list decodable codes
复制标题
线性时间可编码和列表可解码代码
DOI：
10.1145/780542.780562
复制
发表时间：
2003
期刊：
影响因子：
--
通讯作者：
P. Indyk
中科院分区：
文献类型：
--
作者：
V. Guruswami;P. Indyk
我们提出了第一个可以（列表）从任意接近线性的噪声分数（列表）的构造，我们会提出一个明确的代码构造，可以在线性时间内编码，并列出列表解码。在任意ε> 0的误差（1-ε）的线性时间中。构造的速率和字母大小仅取决于ε。列表解码，与所有以前的方法相反，这些方法依赖于诸如芦苇 - 固体代码等代数代码的解码算法的功能。对于要传达的每一点信息，只有在编码和持续的工作量（在发送和接收末端）中持续的冗余。错误模型，在这里我们也证明这在更强的对抗噪声模型下也是可能的。
We present the first construction of error-correcting codes which can be (list) decoded from a noise fraction arbitrarily close to 1 in linear time. Specifically, we present an explicit construction of codes which can be encoded in linear time as well as list decoded in linear time from a fraction (1-ε) of errors for arbitrary ε > 0. The rate and alphabet size of the construction are constants that depend only on ε. Our construction involves devising a new combinatorial approach to list decoding, in contrast to all previous approaches which relied on the power of decoding algorithms for algebraic codes like Reed-Solomon codes.Our result implies that it is possible to have, and in fact explicitly specifies, a coding scheme for arbitrarily large noise thresholds with only constant redundancy in the encoding and constant amount of work (at both the sending and receiving ends) for each bit of information to be communicated. Such a result was known for certain probabilistic error models, and here we show that this is possible under the stronger adversarial noise model as well.