Editing Reed–Solomon error correction (section)

=== Decoder using discrete Fourier transform ===

A discrete Fourier transform can be used for decoding.<ref>{{cite book |last1=Lin |first1=Shu |last2=Costello |first2=Daniel J. |title=Error control coding: fundamentals and applications |date=2004 |publisher=Pearson/Prentice Hall |location=Upper Saddle River, NJ |isbn=978-0130426727 |pages=255–262 |edition=2.}}</ref> 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:
<math display="block">R_j = E_j = S_j = r(\alpha^j) \qquad \text{for } 1 \le j \le t</math>

Use <math>R_1</math> through <math>R_t</math> 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 <math>E_1</math> to <math>E_t</math>, the error locator polynomial, and these formulas
<math display="block">\begin{align}
E_0 &= - \frac{1}{\Lambda_v}(E_{v} + \Lambda_1 E_{v-1} + \cdots + \Lambda_{v-1} E_{1}) \\
E_j &= -(\Lambda_1 E_{j-1} + \Lambda_2 E_{j-2} + \cdots + \Lambda_v E_{j-v})
& \text{for } t < j < n
\end{align}</math>

Then calculate ''C''(''x'') = ''R''(''x'') − ''E''(''x'') and take the inverse transform (polynomial interpolation) of ''C''(''x'') to produce ''c''(''x'').