:= 1 i := 0 while degree of Ri ≥ t/2 i := i + 1 Q := Ri-2 / Ri-1 Ri := Ri-2 - Q Ri-1 Ai := Ai-2 - Q Ai-1 to set low order term of Λ(x) to 1, divide Λ(x) and Ω(x) by Ai(0): Ai(0) is the constant (low order) term of Ai. Example Using the same data as the Peterson–Gorenstein–Zierler example above: Decoder using discrete Fourier transform A discrete Fourier transform can be used for decoding. To avoid conflict with syndrome names, let c(x) = s(x) the encoded codeword. r(x) and e(x) are the same as above. Define C(x), E(x), and R(x) as the discrete Fourier transforms of c(x), e(x), and r(x). Since r(x) = c(x) + e(x), and since a discrete Fourier transform is a linear operator, R(x) = C(x) + E(x). Transform r(x) to R(x) using discrete Fourier transform. Since the calculation for a discrete Fourier transform is the same as the calculation for syndromes, t coefficients of R(x) and E(x) are the same as the syndromes: Use through as syndromes (they're the same) and generate the error locator polynomial using the methods from any of the above decoders. Let v = number of errors. Generate E(x) using the known coefficients to , the error locator polynomial, and these formulas Then calculate C(x) = R(x) − E(x) and take the inverse transform (polynomial interpolation) of C(x) to produce c(x). Decoding beyond the error-correction bound The Singleton bound states that the minimum distance d of a linear block code of size (n,k) is upper-bounded by . The distance d was usually understood to limit the error-correction capability to . The Reed–Solomon code achieves this bound with equality, and can thus correct up to errors. However, this error-correction bound is not exact. In 1999, Madhu Sudan and Venkatesan Guruswami at MIT published "Improved Decoding of Reed–Solomon and Algebraic-Geometry Codes" introducing an algorithm that allowed for the correction of errors beyond half the minimum distance of the code. It applies to Reed–Solomon codes and more generally to algebraic geometric codes. This algorithm produces a list of codewords (it is a list-decoding algorithm) and is based on interpolation and factorization of polynomials over and its extensions. Soft-decoding The algebraic decoding methods described above are hard-decision methods, which means that for every symbol a hard decision is made about its value. For example, a decoder could associate with