Reed-solomon decoder

Abstract

A Reed-Solomon decoder that can correct t errors or fewer which includes: a syndrome calculation circuit for calculating syndromes S (J&equals;0, 1, . . . , 2t&minus;1) using the first codeword Y (i&equals;0, 1, . . . , n&minus;1) (so-called received codeword) that may include errors; and a coefficient calculation circuit for, by using the syndromes S , calculating coefficients &Lgr; (k&equals;1, . . . , e) of an error-locator polynomial. The coefficients &Lgr; correspond in number to e estimated errors (e&lE;t<n). The syndromes S , calculating coefficients Er (1&equals;0, . . . , &ecirc;) (&ecirc; can be as small as O(e)) of an error polynomial, and the coefficients Er correspond in number to the e estimated errors. An error value calculation circuit for calculating error values E by using the coefficients Er of the error polynomial, and for using the coefficients &Lgr; of the error-locator polynomial to generate a signal concerning the error value E to be used and an output circuit for using the first codeword Y and the error value E , which correspond to the signal used to calculate the second codeword W (so-called source codeword) in which the estimated errors are corrected. Since e&lE;t<n, and since there are e coefficients &Lgr; and e coefficients Er , the number of calculations performed by, and the sizes of the coefficient calculation circuit and the error value calculation circuit are reduced. Specifically, since the coefficient calculation circuit requires gate-consuming non-linear operations in order to calculate the coefficients &Lgr; and Er , the effects achieved by such a reduction are greater.