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

fYear

1998

fDate

16-21 Aug 1998

Firstpage

56

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;

fLanguage

English

Publisher

ieee

Conference_Titel

Information Theory, 1998. Proceedings. 1998 IEEE International Symposium on

Conference_Location

Cambridge, MA

Print_ISBN

0-7803-5000-6

Type

conf

DOI

10.1109/ISIT.1998.708637

Filename

708637