For generalized Reed-Solomon codes, it has been proved GuruswamiVa05 that the problem of determining if a received word is a deep hole is co-NP-complete. The reduction relies on the fact that the evaluation set of the code can be exponential in the length of the code -- a property that practical codes do not usually possess. In this paper, we first presented a much simpler proof of the same result. We then consider the problem for standard Reed-Solomon codes, i.e. the evaluation set consists of all the nonzero elements in the field. We reduce the problem of identifying deep holes to deciding whether an absolutely irreducible hypersurface over a finite field contains a rational point whose coordinates are pairwise distinct and nonzero. By applying Schmidt and Cafure-Matera estimation of rational points on algebraic varieties, we prove that the received vector @math for Reed-Solomon @math , @math , cannot be a deep hole, whenever @math is a polynomial of degree @math for @math .
The pursuit of efficient decoding algorithms for Reed-Solomon codes has yielded intriguing results. If the radius of a Hamming ball centered at some received word is less than half the minimum distance, there can be at most one codeword in the Hamming ball. Finding this codeword is called unambiguous decoding . It can be efficiently solved, see @cite_6 for a simple algorithm.
@cite_6
1871606885
Error correction for polynomial block codes is achieved without prior evaluation of power sum symmetric functions. The received word R (z) is reduced mod G (z), the generator of the code and a function F (z) of error locator polynomial W(z), errata values Y and code dependent functions f(xi) of the error positions xi given by ##EQU1## is decomposed into a rational polynomial function N (z) W (z) for which deg (N (z) )<deg ( W (z) )<number of correctable errors. W (z) is the error locator polynomial, the roots of which are the errata locations X and Y, the correction to the received character is obtained from ##EQU2## evaluated at Xi using non-erased check symbols of R (z). Correction is carried out in a crossbar switch structure which recalls a stored copy of R (z) and corrects bits as specified by (Xi, Yi). Another embodiment interposes a matrix transform to transform the symbols of the received word so as to treat a selected set of symbols as erased checks and to present error location corrections directly to the crossbar. Only when changes occur in the pattern of errata is this error corrector apparatus required to operate and to redetermine the transform executed on incoming data R (z).