## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

No credit card required

## 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 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 ...

## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

No credit card required