Efficient decoding of Reed-Solomon codes beyond half the minimum distance
- 27 November 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
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
This publication has 4 references indexed in Scilit:
- Decoding of Reed Solomon Codes beyond the Error-Correction BoundJournal of Complexity, 1997
- A generalization of the Berlekamp-Massey algorithm for multisequence shift-register synthesis with applications to decoding cyclic codesIEEE Transactions on Information Theory, 1991
- Error-correcting codes for list decodingIEEE Transactions on Information Theory, 1991
- Shift-register synthesis and BCH decodingIEEE Transactions on Information Theory, 1969