FFT

Basic idea

The basic idea of FFT is to sequentially decompose the original N-point sequence into a series of short sequences. Make full use of the symmetric and periodic nature of the exponential factor in the DFT calculation formula, and then find the corresponding DFT of these short sequences and combine them appropriately to achieve the purpose of eliminating duplicate calculations, reducing multiplication operations and simplifying the structure. Since then, fast algorithms such as high basis and split basis have been developed based on this idea. With the rapid development of digital technology, in 1976, the Vinograder Fourier Transform Algorithm (WFTA) based on number theory and polynomial theory appeared. ) And prime factor Fourier transform algorithm. Their common feature is that when N is a prime number, the DFT calculation can be converted into a circular convolution, thereby further reducing the number of multiplications and increasing the speed.

Algorithm type

There are many FFT algorithms. According to whether there is an exponential factor WN in the operation process, it can be divided into two types of algorithms with and without exponential factor.

Algorithm with exponential factors

Classic Curry-Tukey algorithm When the length N of the input sequence is not a prime number (prime numbers can only be divided by 1 and itself) but a highly decomposable composite number, that is, N=N1N2N3.Nr, if N1=N2=.= Nr=2, N=2, the calculation of N-point DFT can be decomposed into N=2×N/2, that is, the combination of two N/2-point DFT calculations, and the calculation of N/2-point DFT can be decomposed into N/ 2=2×N/4, which is a combination of two N/4 point DFT calculations. By analogy, the calculation of DFT forms a regular pattern, so it is called the FFT algorithm based on 2. Similarly, when N=4, it is called FFT algorithm based on 4. When N=N1·N2, it is called a mixed basis algorithm based on N1 and N2.

Among these algorithms, the base 2 algorithm is most commonly used. Usually according to the sequence decomposition process in the time domain or frequency domain, it can be divided into two types: one is the time extraction FFT algorithm (DIT), the N point DFT input sequence x (n), in the time domain is decomposed into 2 A sequence of N/2 points and x1(n) and x2(n). The former is extracted from the original sequence according to even sequence numbers, while the latter is extracted according to odd sequence numbers. DIT is such a fast algorithm composed of regular and odd order decomposition.

Split-based algorithm (RSFFT) 1984 by P. Duhamel and H. An improved algorithm derived from Herman et al. is more effective than the Kulitukey algorithm. The basic idea is to use the radix 2 algorithm in the even part of the transform and the radix 4 algorithm in the odd part of the transform. The advantage is that it has a relatively simple structure, which is very suitable for real symmetric data. It can obtain the least amount of calculation (multiplication and addition) for the length N=2, so it is an optimal compromise algorithm in the fixed base algorithm.

Calculation method

The fast method to calculate discrete Fourier transform includes FFT algorithm based on time extraction and FFT algorithm based on frequency extraction. The former sorts the time domain signal sequence according to even and odd, and the latter sorts the frequency domain signal sequence according to even and odd. They both rely on two characteristics: one is periodicity; the other is symmetry, where the symbol * represents its conjugation. In this way, the calculation of the discrete Fourier transform can be divided into several steps, and the calculation efficiency is greatly improved.

The time extraction algorithm makes the length of the signal sequence N (power of 2), which can decompose the time domain signal sequence x(n) into two parts, one is the even part x(2n), and the other is the odd part x(2n+1 ), then the discrete Fourier transform of the signal sequence x(n) can be expressed and calculated using the discrete Fourier transform of two N/2 sampling points. Considering the periodicity of the discrete Fourier transform, equation (1) can be written as

(3) Where (4a) and (4b) can be seen from this, formula (4) is two discrete Fourier transforms containing only N/2 points, G(k) includes only the sequence of even-numbered points in the original signal sequence, H(k) Then only include its odd point sequence. Although k=0, 1, 2, ., N-1, the periods of G(k) and H(k) are both N/2, and their values are repeated in N/2 periods.

Because then we get (5a) (5b) from formula ⑶ and formula ⑷

Therefore, the discrete Fourier transform of a signal sequence x(n) with N sampling points can be obtained by the discrete Fourier transform of two N/2 sampling point sequences. By analogy, this time-based extraction algorithm divides the input signal sequence into smaller and smaller sub-sequences for discrete Fourier transform calculation, and finally synthesizes into N-point discrete Fourier transform.

The signal flow diagram of the butterfly algorithm in Fig. 1 is usually used to express the discrete Fourier transform operation of formula ⑸. For example, the discrete Fourier transform of the signal sequence x(n) at the sampling point of N=8=2 can be calculated using the signal flow graph of the FET algorithm shown in FIG. 2.

①　N=2 point discrete Fourier transform calculations are all composed of butterfly operations, and M-level operations are required. Each level includes N/2 butterfly operations, and there are a total of butterfly operations. Therefore, the total amount of calculation is complex multiplication and N log2N complex addition.

②　The FFT algorithm is iterated in stages, and the calculation formula can be written as

⑹The input signal of N sampling points has N original data x0(n). After the first stage operation, new N data x1(n) are obtained, and then through the second stage iterative operation, another N data x2 are obtained (n), and so on, until the final result x(k)=xM(k)=X(k) In the iterative calculation step by step, the output data of each butterfly operation is stored in the unit that originally stored the input data In the implementation of the so-called "in-place calculation", this can save a lot of registers for storing intermediate data.

③ In the butterfly operation, the weighting coefficient increases exponentially with the iteration number. It can be seen from Figure 2 that the coefficient changes. For the case of N=8, M=3, a three-level iterative operation is required. In the first iteration, only one weighting coefficient is used; the span interval of the butterfly operation is equal to 1. In the second iteration, two weighting coefficients are used; the span interval of the butterfly operation is equal to 2. In the third-level iteration, four different weighting coefficients, ie,, and are used; the span interval of the butterfly operation is equal to 4. It can be seen that the number of different weighting coefficients for each iteration is doubled compared to the previous iteration; the span interval is also doubled.

④　The input data sequence x(n) needs to be rearranged into x(0), x⑷, x⑵, x⑹, x⑴, x⑸, x⑶, x⑺, which is the reverse order number obtained by inverting the code position of the binary number, for example, N=8 The binary number of the median "1" is "001", and its code point is inverted to "100", which is the decimal number "4".

Frequency extraction algorithm The FFT algorithm based on frequency extraction is to decompose the frequency domain signal sequence X(k) into two parts, odd and even, but the algorithm is still calculated step by step from the time domain signal sequence. It is also divided into N/2 points to calculate FFT can reduce the N multiplications required to directly calculate the discrete Fourier transform to times.

In the case of N=2, divide the N point input sequence x(n) into two halves

⑺

The length of the time series x1(n)±x2(n) is N/2, so the discrete Fourier transform of N points can be written as

(8a)

(8b)

The frequency signal sequence X(2l) is the N/2-point discrete Fourier transform of the time signal sequence x1(n)+x2(n), and the frequency signal sequence X(2l+1) is the time signal sequence [x1(n)- x2(n)] N/2-point discrete Fourier transform, therefore, the calculation of the N-point discrete Fourier transform uses two addition (subtraction) and one multiplication to obtain two subsequences from the original sequence, so, The frequency extraction algorithm also has a butterfly operation form. The basic butterfly calculation formula of FFT based on 2 is:

⑼

The amount of calculation is exactly the same as the time extraction algorithm, that is, only multiplication operations and Nlog2N addition (subtraction) operations are required. Figure 3 shows the signal flow diagram of the discrete Fourier transform with N=8=2 points. It can be seen from the figure that it performs in-place calculation in three levels of iteration, the input data is stored in natural order, the coefficients used are also in natural order, and the final result is stored in reverse binary order.

In fact, there is a transposed relationship between the signal flow graph of the frequency extraction algorithm and the time extraction algorithm. If the flow graph is properly deformed, a variety of geometric shapes can be obtained.

In addition to the radix-2 FFT algorithm, there are radix-4, radix-8 and other high-radix FFT algorithms and any number of radix-based FFT algorithms.

Application

The obvious advantage of small calculation amount makes FFT widely used in the field of signal processing technology, and real-time processing of signals can be realized in combination with high-speed hardware. For example, the analysis and synthesis of voice signals, the multiplexing and conversion of fully digital time division and frequency division (TDM/FDM) in communication systems, filtering and correlation analysis of signals in the frequency domain, through radar, sonar , Spectrum analysis of vibration signals to improve the resolution of target search and tracking, etc., all need to use FFT. It can be said that the emergence of FFT has played an important role in the development of digital signal processing.