Algorithms of fast Fourier transform FFT (fast Fourier transform). Principle of construction

Fourier analysis today is without doubt the most common analysis tool that is used in all branches of science and technology. However, before the advent of computers, the discrete Fourier transform (DFT) was rarely used, since the calculation of the DFT of 32 samples requires 1024 operations of complex multiplication and addition, which in manual count for quite a long time. However, the first mention of the fast Fourier transform algorithm refers to the work of Gauss, in which he used the periodicity properties of trigonometric functions to calculate the DFT. However, no one paid attention to this work for a long time, until personal computers were widely used.

The first software implementation of the FFT algorithm was carried out in the early 60s of the 20th century by John Cooley at the IBM computer center under the supervision of Tesca John Tukey, and in 1965 they themselves published an article on the Fast Fourier Transform algorithm. From this moment begins the real FFT-mania. Thousands of papers devoted to the FFT algorithm are published, monographs are published one by one, programmers compete in the efficiency of the algorithm implementation. FFT becomes the main tool for spectral analysis of signals.

What gave impetus to this rapid development? Consider the expression for the discrete Fourier transform:

DFT signal readings (generally complex) puts in compliance complex spectrum readings , and to calculate a single spectral reference is required operations of complex multiplication and addition. Thus, the computational complexity of the DFT algorithm is complex multiplications and additions. In this case, it can be noted that if one DFT on points (counts) to replace the calculation of two DFT on points, this will reduce the number of operations by 2 times. Replacement -point DFT two -point presented in Figure 1.

In addition, each of - point DFT can also be calculated by replacing -point DFT for two -point. In this case, the number of computational operations is equal to . In this way, it is possible to continue splitting the source sequence as long as it is possible to divide the sequence into two. Obviously, if , - positive integer, we can split the sequence in half time. For ( ) such a partition is presented in Figure 2.

Each partition divides the sequence into two half-lengths (red and blue), and each join “assembles” one of the doubled lengths from the two sequences.

FFT algorithms that use length samples are called “base 2 FFT algorithms”. These algorithms are the most common, due to the fact that in machine arithmetic is a “round” number. Further, we will consider only the algorithms for base 2.

Obviously, it is possible to divide the sequence into two differently, but it depends on whether we can get an undistorted signal spectrum when combined and what it will cost us in terms of computational costs. It can be said that the efficiency of the FFT algorithm depends entirely on the method of splitting and combining the sequence, since if we disregard the operations on splitting-combining, then to calculate the spectrum is required calculate the DFT times by 2 points, as a result, the total number of computational operations will be , that is, the number of operations linearly depends on the size of the sample.

We consider two ways of splitting - combining: thinning by time and thinning by frequency. An example of software implementation and use of the FFT algorithm will also be given.

Before considering the methods of splitting - combining, we need to consider the inverse discrete Fourier transform (IDFT):

Having an FFT calculation algorithm, I would very much like to use it for the inverse transformation. To do this, pay attention to the fact that:

In other words, the complex exponentials in the expression for the direct and inverse DFT are complex conjugate (the bar above means complex conjugation). Now consider two complex numbers and .

Now consider the product of complex conjugate on :

Comparing (4) and (5) we can conclude:

With reference to the expression of IDFT, you can write:

Thus, a complex conjugate spectrum is taken. the direct DFT is performed and the result is subjected to complex conjugation. Calculation of ODP with the use of DFT is shown in Figure 3.

If instead of the DFT we use the FFT, then we obtain the inverse fast Fourier transform (OBFT). In this case, to perform complex conjugation, it is only necessary to change the sign in front of the imaginary part of the spectrum before calling the FFT function and the result after the FFT.

Thus, we considered the way of acceleration of calculations in the calculation of the DFT, and also reduced the IDFT to a direct one. Now it is necessary to consider partitioning methods — unions that provide a significant reduction in computations. In the following articles, we will examine in detail the FFT algorithms for base two with decimation by time and frequency by frequency.