Digital Filters Design for Signal and Image Processing

3.4. The fast Fourier transform (FFT)

In 1965, Cooley and Tuekey proposed a fast algorithm for calculating the discrete Fourier transform. With real signals, the direct calculation of equation (3.66) requires 2N² multiplications and 2N(N − 1) additions. With complex signals, the computational cost reaches 4N² multiplications and 2N(2N − 1) additions. The fast method consists of operating by dichotomy, which reduces, as we will see later, to a calculatory complexity as N log₂ (N).

From now on, to simplify presentation, we use the example of a fast Fourier transform on N = 8 points.

We introduce the coefficient W_N called the “Twiddle factor”, which corresponds to the complex root of the unity represented by:

We can then rewrite equation (3.69) in the form:

For N = 8, equation (3.71) leads to the following matricial equation:

The complex roots of the unity have specific qualities that can be exploited to simplify equation (3.72). Actually, the “Twiddle factors” satisfy the following properties and . We thus show the redundancy of the W_N coefficients. This is a reduction of this redundancy ...