Complexity of Decoding Positive-Rate Primitive Reed–Solomon Codes
Complexity of Decoding Positive-Rate Primitive Reed–Solomon Codes
复制标题
DOI：
10.1109/tit.2010.2060234
复制
发表时间：
2010-10
影响因子：
2.5
通讯作者：
Qi Cheng;D. Wan
中科院分区：
文献类型：
--
作者：
Qi Cheng;D. Wan
证明了Reed-Solomon码的最大似然译码问题是NP难的。然而，证明中的代码长度最多是字母表大小的多对数。对于原始Reed-Solomon码的最大似然解码的复杂性，其长度小于字母表的大小，唯一已知的结果表明，在某些情况下，当信息速率不幸地变为零时，它至少与离散对数一样困难。本文在一个著名的密码学硬度假设下证明了：1）对于Reed-Solomon码族[q，k（q）]q，不存在随机多项式时间极大似然译码器，其中k（x）是Z+ → Z+中的任意函数，在时间xO（1）上可计算，满足n x ≤ k（x）≤ x -n x。2)不存在用于原始Reed-Solomon码的随机多项式时间有界距离解码器，其距离为对于任何常数0 <; 1/3的最小距离的2/3 + 1/4。特别是，这排除了多项式时间算法的可能性的最大似然译码问题的原始Reed-Solomon码的任何速率的假设下。
It has been proved that the maximum likelihood decoding problem of Reed-Solomon codes is NP-hard. However, the length of the code in the proof is at most polylogarithmic in the size of the alphabet. For the complexity of maximum likelihood decoding of the primitive Reed-Solomon code, whose length is one less than the size of alphabet, the only known result states that it is at least as hard as the discrete logarithm in some cases where the information rate unfortunately goes to zero. In this paper, it is proved under a well known cryptography hardness assumption that: 1) There does not exist a randomized polynomial time maximum likelihood decoder for the Reed-Solomon code family [q, k(q)]q, where k(x) is any function in Z+ → Z+ computable in time xO(1) satisfying √x ≤ k(x) ≤ x - √x. 2) There does not exist a randomized polynomial time bounded-distance decoder for primitive Reed-Solomon codes at distance 2/3 + ϵ of the minimum distance for any constant 0 <; ϵ <; 1/3. In particular, this rules out the possibility of a polynomial time algorithm for maximum likelihood decoding problem of primitive Reed-Solomon codes of any rate under the assumption.