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 2N2 multiplications and 2N(N − 1) additions. With complex signals, the computational cost reaches 4N2 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 log2 (N).
From now on, to simplify presentation, we use the example of a fast Fourier transform on N = 8 points.
We introduce the coefficient WN 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 WN coefficients. This is a reduction of this redundancy ...