Discrete Fourier Transform (general) - Polynomial Formulation

Polynomial Formulation

Sometimes it is convenient to identify an -tuple with a formal polynomial

By writing out the summation in the definition of the discrete Fourier transform (2), we obtain:

This means that is just the value of the polynomial for, i.e.,

The Fourier transform can therefore be seen to relate the coefficients and the values of a polynomial: the coefficients are in the time-domain, and the values are in the frequency domain. Here, of course, it is important that the polynomial is evaluated at the th roots of unity, which are exactly the powers of .

Similarly, the definition of the inverse Fourier transform (3) can be written:

With

this means that

We can summarize this as follows: if the values of are the coefficients of, then the values of are the coefficients of, up to a scalar factor and reordering.