Title :
Efficient decoding of Reed-Solomon codes beyond half the minimum distance
Author :
Roth, Ron M. ; Ruckenstein, Gitit
Author_Institution :
Dept. of Comput. Sci., Technion-Israel Inst. of Technol., Haifa, Israel
Abstract :
A list decoding algorithm is presented for the family of generalized Reed-Solomon (GRS) codes, capable of correcting a number of errors greater than half the minimum distance d of the code. Based on a previous work of Sudan (see J. Compl., vol.13, p.180-93, 1997), an extended key equation is derived for GRS codes, which is reduced to the classical key equation when the number of errors is limited to [(d-1)/2]. Using a technique due to Feng and Tzeng (1991), an algorithm is obtained for solving the extended key equation in time complexity quadratic in d. For comparison, the time complexity of the respective part in Sudan´s algorithm is cubic in the code length
Keywords :
Reed-Solomon codes; computational complexity; decoding; code length; efficient decoding; error correcting code; extended key equation; generalized Reed-Solomon codes; list decoding algorithm; minimum distance; quadratic time complexity; Computer errors; Computer science; Decoding; Ear; Equations; Error correction codes; Hamming distance; Laboratories; Polynomials; Reed-Solomon codes;
Conference_Titel :
Information Theory, 1998. Proceedings. 1998 IEEE International Symposium on
Conference_Location :
Cambridge, MA
Print_ISBN :
0-7803-5000-6
DOI :
10.1109/ISIT.1998.708637
