= Finite-field discrete Fourier transform
{title2=$\widehat c_\ell=\sum_{j=0}^{n-1}c_j\omega^{j\ell}$}
If $\omega$ is a primitive $n$th root in a <finite field> and the field <characteristic> does not divide $n$, the inverse transform is $c_j=n^{-1}\sum_{\ell=0}^{n-1}\widehat c_\ell\omega^{-j\ell}$. The identity $\sum_{j=0}^{n-1}\omega^{jm}=0$ unless $n\mid m$, when the sum is $n$, proves inversion. For a <primitive cyclic Reed-Solomon code>, encoding assigns the $k$ unconstrained transform values and makes the remaining values zero; received transform values at those zeros are <syndromes>.
Back to article page
