On deep holes of standard Reed-Solomon codes  

作　　者：WU RongJun HONG ShaoFang 

机构地区：[1]Mathematical College, Sichuan University, Chengdu 610064, China [2]Yangtze Center of Mathematics, Sichuan University, Chengdu 610064, China

出　　处：《Science China Mathematics》2012年第12期2447-2455,共9页中国科学：数学（英文版）

基　　金：supported by National Natural Science Foundation of China (Grant No.10971145);by the Ph.D. Programs Foundation of Ministry of Education of China (Grant No. 20100181110073)

摘　　要：Determining deep holes is an important open problem in decoding Reed-Solomon codes. It is well known that the received word is trivially a deep hole if the degree of its Lagrange interpolation polynomial equals the dimension of the Reed-Solomon code. For the standard Reed-Solomon codes [p-1, k]p with p a prime, Cheng and Murray conjectured in 2007 that there is no other deep holes except the trivial ones. In this paper, we show that this conjecture is not true. In fact, we find a new class of deep holes for standard Reed-Solomon codes [q-1, k]q with q a power of the prime p. Let q≥4 and 2≤k≤q-2. We show that the received word u is a deep hole if its Lagrange interpolation polynomial is the sum of monomial of degree q-2 and a polynomial of degree at most k-1. So there are at least 2(q-1)qk deep holes if k q-3.Determining deep holes is an important open problem in decoding Reed-Solomon codes. It is well known that the received word is trivially a deep hole if the degree of its Lagrange interpolation polynomial equals the dimension of the Reed-Solomon code. For the standard Reed-Solomon codes [p-1, k]p with p a prime, Cheng and Murray conjectured in 2007 that there is no other deep holes except the trivial ones. In this paper, we show that this conjecture is not true. In fact, we find a new class of deep holes for standard Reed-Solomon codes [q-1, k]q with q a power of the prime p. Let q≥4 and 2≤k≤q-2. We show that the received word u is a deep hole if its Lagrange interpolation polynomial is the sum of monomial of degree q-2 and a polynomial of degree at most k-1. So there are at least 2（q-1）qk deep holes if k q-3.

关 键 词：deep hole Reed-Solomon code cyclic code BCH code DFT IDFT 

分 类 号：TN919.8[电子电信—通信与信息系统] TN911.22[电子电信—信息与通信工程]