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 2*N*^{2} multiplications and 2*N*(*N* − 1) additions. With complex signals, the computational cost reaches 4*N*^{2} multiplications and 2*N*(2*N* − 1) additions. The fast method consists of operating by dichotomy, which reduces, as we will see later, to a calculatory complexity as *N* log_{2} (*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 ...

Start Free Trial

No credit card required