Editing Reed–Solomon error correction (section)

==== Discrete Fourier transform and its inverse ====

A [[discrete Fourier transform (general)|discrete Fourier transform]] is essentially the same as the encoding procedure; it uses the generator polynomial <math>p_m</math> to map a set of evaluation points into the message values as shown above:
<math display="block">C(m) = \begin{bmatrix}
p_m(a_0) \\
p_m(a_1) \\
\cdots \\
p_m(a_{n-1})
\end{bmatrix}</math>

The inverse Fourier transform could be used to convert an error free set of ''n'' < ''q'' message values back into the encoding polynomial of ''k'' coefficients, with the constraint that in order for this to work, the set of evaluation points used to encode the message must be a set of increasing powers of ''α'':
<math display="block">a_i = \alpha^i</math>
<math display="block">a_0, \dots, a_{n-1} = \{ 1, \alpha, \alpha^2, \dots, \alpha^{n-1} \}</math>

However, Lagrange interpolation performs the same conversion without the constraint on the set of evaluation points or the requirement of an error free set of message values and is used for systematic encoding, and in one of the steps of the [[#Gao decoder|Gao decoder]].