Reed-solomon decoder

Abstract

A Reed-Solomon decoder that can correct t errors or fewer which includes: a syndrome calculation circuit for calculating syndromes Sj (J=0, 1, . . . , 2t−1) using the first codeword Yi (i=0, 1, . . . , n−1) (so-called received codeword) that may include errors; and a coefficient calculation circuit for, by using the syndromes Sj, calculating coefficients Λk (k=1, . . . , e) of an error-locator polynomial. The coefficients Λk correspond in number to e estimated errors (e≦t<n). The syndromes Sj, calculating coefficients Er1 (1=0, . . . , ê) (ê can be as small as O(e)) of an error polynomial, and the coefficients Er1 correspond in number to the e estimated errors. An error value calculation circuit for calculating error values Ei by using the coefficients Er1 of the error polynomial, and for using the coefficients Λk of the error-locator polynomial to generate a signal concerning the error value Ei to be used and an output circuit for using the first codeword Yi and the error value Ei, which correspond to the signal used to calculate the second codeword Wi (so-called source codeword) in which the estimated errors are corrected. Since e≦t<n, and since there are e coefficients Λk and e coefficients Er1, 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 Λk and Er1, the effects achieved by such a reduction are greater.

Dependencies are inferred from the claim text.