Finite-field discrete Fourier transform (${\hat{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}{\hat{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.