O'Reilly logo

Digital Filters Design for Signal and Image Processing by Mohamed Najim

Stay ahead with the world's most comprehensive technology and business learning platform.

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

Start Free Trial

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.

images

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

images

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

images

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

images

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.

Start Free Trial

No credit card required