The DFT and FFT

The DFT and FFT

The DFT:

To evaluate a polynomial 

of degree-bound n at 

      (that is, at the n complex nth roots of unity).

'

Assume that A is given in coefficient form: a = (a₀, a₁, . . . , a_n-1). Let us define the results y_k, for k = 0, 1, . . . , n - 1, by  

The vector y = (y₀, y₁, . . . , y_n-1) is the Discrete Fourier Transform (DFT) of the coefficient vector a = (a₀, a₁, . . . , a_n-1). It can also be written as, y =DFT_n(a).

The FFT:

By using a method known as the Fast Fourier Transform (FFT), which takes advantage of the special properties of the complex roots of unity, DFT_n(a) can be computed  in time (n lg n), as opposed to the (n²) time of the straightforward method.

The FFT method employs a divide-and-conquer strategy, using the even-index and odd-index coefficients of A(x) separately to define the two new degree-bound n/2 polynomials A^[0](x) and A^[1](x): 

A^[0](x)  =  a₀ + a₂x + a₄x² +    + a_n-2xⁿ/2-1,

A^[1](x)  =  a₁ + a₃x + a₅x² +    + a_n-1xⁿ/2-1.

Note: 

1.  A^[0] contains all the even-index coefficients of A (the binary representation of the index ends                   in 0) and 

2. A^[1] contains all the odd-index coefficients (the binary representation of the index ends in 1).

It follows that

            A(x) = A^[0](x²) + xA^[1](x²),………..           →(equation 1)

so that the problem of evaluating A(x) at

 

1. evaluating the degree-bound n/2 polynomials A^[0](x) and A^[1](x) at the points

and then

2. Combining the results according to equation 1.

By the halving lemma, the polynomials A^[0] and A^[1] of degree-bound n/2 are recursively evaluated at the n/2 complex (n/2)^th roots of unity. These sub problems have exactly the same form as the original problem, but are half the size. An n-element DFT_n computation can be successfully into two n/2-element DFT_n/2 computations. This decomposition is the basis for the following recursive FFT algorithm, which computes the DFT of an n-element vector a = (a₀, a₁, . . . , a_{n -} 1), where n is a power of 2.