On the list and bounded distance decodability of Reed-Solomon codes
文献类型：期刊论文
| 作者 | Cheng, Qi; Wan, Daqing |
| 刊名 | SIAM JOURNAL ON COMPUTING
 |
| 出版日期 | 2007 |
| 卷号 | 37期号:1页码:195-209 |
| 关键词 | list decoding algorithm bounded distance decoding algorithm Reed-Solomon codes discrete logarithm problem |
| ISSN号 | 0097-5397 |
| DOI | 10.1137/S0097539705447335 |
| 英文摘要 | For an error-correcting code and a distance bound, the list decoding problem is to compute all the codewords within a given distance to a received message. The bounded distance decoding problem is to find one codeword if there is at least one codeword within the given distance, or to output the empty set if there is not. Obviously the bounded distance decoding problem is not as hard as the list decoding problem. For a Reed-Solomon code [n, k](q), a simple counting argument shows that for any integer 0 < g < n, there exists at least one Hamming ball of radius n-g, which contains at least ((n)(g))/q(g-k) many codewords. Let (g) over cap (n, k, q) be the smallest positive integer g such that (g(n))/q(g-k) <= 1. One knows that k - 1 <= (g) over bar (n, k, q) <= root n(k-1) <= n. For the distance bound up to n - root n(k - 1), it is known that both the list and bounded distance decoding can be solved e. ciently. For the distance bound between n- root n(k - 1) and n-(g) over bar (n, k, q), we do not know whether the Reed - Solomon code is list or bounded distance decodable; nor do we know whether there are polynomially many codewords in all balls of the radius. It is generally believed that the answer to both questions is no. In this paper, we prove the following: ( 1) List decoding cannot be done for radius n-(g) over cap (n, k, q) or larger, unless the discrete logarithm over F-q (g) double under bar (n,F- k,F- q)- k is easy. (2) Let h and g be positive integers satisfying q >= max(g(2), (h - 1)(2+is an element of)) and g = (4/is an element of + 2)(h+1) for a constant is an element of > 0. We show that the discrete logarithm problem over F-q(h) can be e. ciently reduced by a randomized algorithm to the bounded distance decoding problem of the Reed-Solomon code [q, g-h](q) with radius q - g. These results show that the decoding problems for the Reed-Solomon code are at least as hard as the discrete logarithm problem over certain finite fields. For the list decoding problem of Reed - Solomon codes, although the infeasible radius that we obtain is much larger than the radius, which is known to be feasible, it is the first nontrivial bound. Our result on the bounded distance decodability of Reed - Solomon codes is also the first of its kind. The main tools for obtaining these results are an interesting connection between the problem of list decoding of Reed-Solomon code, the problem of a discrete logarithm over finite fields, and a generalization of Katz's theorem on representations of elements in an extension finite field by products of distinct linear factors. |
| WOS研究方向 | Computer Science ; Mathematics |
| 语种 | 英语 |
| WOS记录号 | WOS:000246923400009 |
| 出版者 | SIAM PUBLICATIONS |
| 源URL | [http://ir.amss.ac.cn/handle/2S8OKBNM/5237]  |
| 专题 | 中国科学院数学与系统科学研究院 |
| 通讯作者 | Cheng, Qi |
| 作者单位 | 1.Univ Oklahoma, Sch Comp Sci, Norman, OK 73019 USA 2.Univ Calif Irvine, Dept Math, Irvine, CA 92697 USA 3.Chinese Acad Sci, Inst Math, Beijing 100080, Peoples R China |
| 推荐引用方式 GB/T 7714 | Cheng, Qi,Wan, Daqing. On the list and bounded distance decodability of Reed-Solomon codes[J]. SIAM JOURNAL ON COMPUTING,2007,37(1):195-209. |
| APA | Cheng, Qi,&Wan, Daqing.(2007).On the list and bounded distance decodability of Reed-Solomon codes.SIAM JOURNAL ON COMPUTING,37(1),195-209. |
| MLA | Cheng, Qi,et al."On the list and bounded distance decodability of Reed-Solomon codes".SIAM JOURNAL ON COMPUTING 37.1(2007):195-209. |
入库方式： OAI收割
来源：数学与系统科学研究院
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。