Fast Fourier transform

A fast Fourier transform ( Fast Fourier Transform English, therefore, usually abbreviated to FFT ) is an efficient algorithm for computing the values ​​of a discrete Fourier transform (DFT). In such algorithms are divide-and- conquer method. In contrast to the direct calculation using a fast Fourier transform previously calculated intermediate results of arithmetic operation, and a saves operations. The best known method is James Cooley and John W. Tukey attributed, which issued in 1965. A form of the algorithm Strictly speaking already designed in 1805 by Carl Friedrich Gauss, who used it to calculate the trajectories of the asteroid ( 2) Pallas and (3) Juno. Was published for the first time a variant of the algorithm by Carl Runge in 1903 and 1905. Moreover, limited forms of the algorithm have been developed several times before Cooley and Tukey, such as by Irving John Good ( 1960). According to Cooley and Tukey, there have been numerous suggestions for improvement beyond and variations, such as Georg Bruun, CM Rader, and Leo I. Bluestein.

Similarly, there is for the discrete inverse Fourier transform is a fast algorithm ( inverse FFT - IFFT). Occur at the IFFT algorithms identical with the other coefficients in the calculation for application.

  • 8.1 General
  • 8.2 For input data without imaginary
  • 8.3 accuracy

Informal description of the algorithm ( Cooley and Tukey )

The algorithm of Cooley and Tukey is a classic divide-and -conquer method. Is a prerequisite for its application, that the number of sampling points or sampling points is a power of two. Since the number of such points in the frame of the measuring method, however, may generally be selected freely, it is not, this is a serious limitation.

The idea behind the algorithm, it is now that the calculation of a DFT of size 2n now up to two calculations of the DFT of size n divided - the vector with the entries of the even and the odd indices - and the two partial results after the transformation again can be joined together to form a Fourier transform of size 2 n.

Since the calculation of a DFT of half the length, only a quarter of the complex multiplications and additions of the original DFT needed, and depending on the length of the output vector, this provision is repeatedly applied, the recursive application of this basic idea finally allowed a calculation in time; In order to save trigonometric computing operations, the properties of the roots of unity can also be exploited from the Fourier matrix with the FFT.

Formal description of the algorithm ( Cooley and Tukey )

It should first be recalled that the discrete Fourier transform of size ( hereinafter referred to as DFT) 2n defined by the following formula:

Let's note the entries for even indices as

And denote the transform DFT of size n with

The entries for odd indices we write according as

And denote the transform DFT of size n with

Then follows:

Mathematical description (general case )

In mathematics, the fast discrete Fourier transformation is treated in a much more general context:

Be a commutative unitary ring. In the figure is a unit (ie, invertible ); also be with a root of unity. For example, in the remainder class ring

The element such a unit root, the corresponding FFT is used in Schönhage - Strassen algorithm.

Then can be with in the module to the discrete Fourier transform

Calculate optimized as follows:

First, we note that the indices and dual as follows:

Thus we have the following recursion:

Because of

We obtain from this the discrete Fourier transform.

Complexity

This classic version of the FFT by Cooley and Tukey is in contrast to the DFT only feasible if the length of the input vector corresponds to a power of two. The number of the sampling points may thus, for example, 1, 2, 4, 8, 16, 32, etc. be. This is called a radix-2 FFT. Other lengths are possible with the below alternative algorithms.

From the above recursion, the following recurrence relation for the running time of the FFT results:

Here, the term describes the effort to multiply the results by a power of the root of unity, and to add the results. There are N pairs of numbers are added and N / 2 numbers with unit roots multiplied. A total of f (N) is linear restricted:

The master theorem gives a term of:

The structure of the data flow can be described by a butterfly graph, which defines the order of calculation.

Implementation as a recursive algorithm

The direct implementation of the FFT in pseudo code by the above method is in the form of a recursive algorithm:

  • The field with the input values ​​is passed to a function as a parameter, which is in two half as long fields (one with the values ​​straight and one with the values ​​with odd index ) splits.
  • These two fields are now passed to new instances of this function.
  • At the end of each function returns the FFT of her passed as a parameter field. These two FFTs are now before an instance of the function is terminated, combined according to the formula shown above into a single FFT - and the result is returned to the caller.

This will be continued until the argument of a call to the function consists only of a single element ( recursion ): The FFT of a single value is ( he has himself as a constant component, and no other frequencies) himself The function that only still receives a single value as a parameter, so it can without any calculation, the FFT return this value - the function that called it, combines the two 1 point long FFTs, they get back, the function that this in turn has invoked the two 2 -point FFTs, and so on.

The speed advantage of the FFT over the DFT can be well estimated by this algorithm:

  • To calculate the FFT of a long vector elements, using this algorithm recursion n are necessary. It doubles in each level, the number of vectors to be calculated - while the length of each cut in half, so that exactly complex multiplications and additions are required at the end in each except for the last level of recursion. The total number of additions and multiplications is thus
  • In contrast, the DFT requires complex multiplications and additions for the same input vector.

Implementation as a non-recursive algorithm

The implementation of a recursive algorithm is terms of resource consumption is not ideal as a rule, as many function calls this necessary computing time and memory need for memorizing the return addresses. In practice, a non-recursive algorithm is therefore usually used, which can be opposite to that shown here optimized for simple understanding shape yet optimized depending on the application:

  • First, when the two halves of the array are in the above algorithm are interchanged, and then the two halves of these halves, etc. - the result is the same as if all the elements of the array are numbered in ascending order from 0 in the end - and then the order of the bits of the number of fields will be reversed.
  • When the input values ​​are in this way re-sorted only on the object, the individual short FFTs of the last recursion outward is to combine long FFTs, for example in the form of three nested loops: The outermost loop counts the recursion by ( from 0 to N -1).
  • The next loop count by the FFT sections, in which the FFT is not divided in this recursion. The count of this loop is referred to as.
  • The innermost loop is one of the element within an FFT section ( hereinafter referred to ) by (from 0 to )
  • In the innermost of these loops now always be the two samples with the following two indices:

Alternative forms of the FFT

Next to the FFT algorithm by Cooley and Tukey, also called radix-2 algorithm described above, there are also a number of other algorithms for fast Fourier transformation. The variants differ in how certain parts of the " naive " algorithm can be reshaped so that less ( high precision ) multiplications are necessary. While usually considered that the reduction in the number of multiplications, additions, as well as an increased number of the same in the memory by causing to be held intermediate results.

Below are some other algorithms are shown in an overview. Details and precise mathematical descriptions including derivations can be found in the literature below.

Radix -4 algorithm

The radix-4 algorithm is analogous to the radix -8 algorithm or generally Radix -2N - algorithm, an evolution of the above radix-2 algorithm. The main difference is that the number of data points to be processed must be a power of 4 or 4N. The processing structure remains the same here, except that in the butterfly graph per element instead of two, four or eight data paths and generally 4N data paths must be linked. The advantage consists in a further reduced computational complexity, and thus speed advantage. Thus, compared with the above algorithm by Cooley and Tukey in which radix-4 algorithm, about 25 % fewer multiplications required. In the radix- 8 algorithm reduces the number of multiplications by about 40 %.

The disadvantage of this method is the coarse structure and a complex code. Thus, with the radix-4 algorithm only blocks of lengths 4, 16, 64, 256, 1024, 4096, ... process. In the radix- 8 algorithm, the constraints can be seen analogously.

Winograd algorithm

In this algorithm, only a certain finite number of support points of the number is possible, namely:

Wherein all the combinations are permitted by Nj, where Nj used are relatively prime. This means that only a maximum block length of 5040 is possible. The possible values ​​for are in the range up to 5040 but dense on the number line as the powers of two. There is thus a better fine tuning of the block length is possible. Is built, the algorithm of basic blocks of the DFT, the lengths of which correspond with Nj. In this method, although the number of multiplications is reduced compared to the radix-2 algorithm, but at the same time increases the number of necessary additions. Moreover, a complicated permutation of the data at the input and output of each DFT necessary, which is formed according to the rules of the Chinese remainder theorem.

This type of fast Fourier transform has in practical implementations, then advantages over the radix- 2 method when the microcontroller used for the FFT does not have a multiplier and a lot of computing time has to be spent for the multiplications. In today's signal processors with its own multiplier, this algorithm has no significant meaning.

Prime factor algorithm

This FFT algorithm is based on ideas similar to the Winograd algorithm, however, the structure is simple, and thus the amount of multiplication is higher than the Winograd algorithm. The main advantage of the implementation is the efficient use of available memory by optimum adaptation of the block length. If in a particular application, although a fast multiplier is available, while the memory is limited, this algorithm can be optimal. The execution time is comparable with a similar block length with that of the algorithm of Cooley and Tukey.

Goertzel algorithm

The Goertzel algorithm is a special form for the efficient computation of individual spectral components and is in the calculation of only a few spectral components (English bins) more efficient than any block- based FFT algorithms, which always compute the complete discrete spectrum.

Chirp - z-transform

Bluestein FFT algorithm for data sets of arbitrary size (including primes ).

Interpretation of results

Generally

The FFT generated from n complex input values ​​n complex result values ​​.

The amount of each of these output values ​​corresponds to the length, and the argument of each output value of the angle of a vector at the time t = 0 If you can now revolve all the vectors with the proper speeds around zero - and added to each other, one again obtains the input values ​​.

The frequency with which the m- th vector of the calculated spectrum to be sure rotated counterclockwise, results from the formula

Vectors must therefore rotate at a so higher frequency, the closer they are to the center of the result of the FFT, and each vector from the upper half of the result rotates at the same frequency, but in the reverse direction as a vector of the lower half of the result does. This can be explained, for example, on the Nyquist -Shannon sampling theorem, which states that are frequencies above half the sampling frequency by sampling in the frequency domain mirrored among them; It should be noted that two of all circular movements, elliptic movements, sinus or Kosinusschwingungen can be composed with the corresponding frequency in different directions, but at the same speed rotating vectors.

For input data without imaginary

So that a signal with the imaginary part of 0 can be composed of both circular having the same frequency vectors, the real part of the two rotating vectors with the same frequency must be the same, - and the two have imaginary parts of the vector always add up to zero.

It follows:

Is well known that the input to the FFT was purely real, it is therefore worth only one (usually the lower ) to consider half of the spectrum, where the magnitude of each vector of the half amplitude of a frequency, and the argument of each vector of the phase shift of a corresponding frequency from which to compose the input signal.

Consideration should be given if necessary in some cases, the DC component, and the element that corresponds to the highest possible in the calculated spectrum frequency.

Accuracy

Tends to the quantization noise is lower than in the case of the discrete convolution in the fast Fourier transformation in the case where it is more efficient than the DFT, due to the lower number of the faulty arithmetic operations.

The inverse FFT

The close relationship between FFT and iFFT can already guess based on the following considerations:

  • Is the input signal of the FFT a at a constant speed about the origin of rotating vector, then the result of the FFT is intended an output signal to the frequency of rotation of the corresponding point, the magnitude of the amplitude and the argument of the phase of the rotation at the time t = 0 corresponds to - constant 0
  • Is the input signal of the FFT constant 0, with the exception of a single point, it follows the basic equation of the DFT, in this case a vector which revolves at a constant speed around the zero point.

For a vector, in which only a single point has an amplitude equal to 0, ie the two-time FFT of the result is similar to the baseline.

  • In addition, the FFT consists only of linear equations. This means, among other things, that when different output vectors are added and then twice be transformed by the FFT, the result of this action must be the same as if the individual signals are transformed only twice and then added together.

Together this suggests that the result of two consecutive FFT is performed for arbitrary signals resemble the original.

However, the amplitude of the result of the two times the FFT of a signal will obviously depend on the length thereof, and is in the above, the direction of the rotation of the vectors have not been taken into account for the zero point.

In fact applies to any kind of Fourier transformation:

Application

The areas of application of the FFT are so versatile that here only a selection can be given:

  • Computer Algebra Implementation of fast, polynomial -processing algorithms (eg polynomial multiplication in )
  • The calculation of option prices (see Carr / Madan 1999)
  • Acoustic (audio measurements). A trivial application are many guitar tuner or similar programs that benefit from their high speed.
  • Calculation of spectrograms ( Diagrams showing the amplitudes of the respective frequency components )
  • Reconstruction of the image in the magnetic resonance tomograph, and the analysis of crystal structure using X-rays in each of which the Fourier transform of the desired image, or the square of the Fourier transform results.
  • Digital network analyzers, to try to determine the behavior of a circuit, a component or a line on a circuit path during operation at any frequency in mixtures.
  • Synthesis of audio signals from the individual frequencies of the inverse FFT
  • To reduce the computation effort for the circular convolution in the time domain FIR filtering and substitution by the fast Fourier transform and simple multiplications in the frequency domain. (see also Fast Convolution ). The Fast Convolution for example, offers the possibility of any audio or similar signals with little computational effort by even very complex filters ( equalizers, etc. ) to transport.
  • Compression algorithms often use the FFT or, as the well-known MP3 format, which related with their discrete cosine transform. The FFT images or sounds often results in only relatively few frequencies with high amplitudes. This is advantageous if a process for storing the results is used, the lower the number of display requires less bits, such as the Huffman coding. In other cases, use is made that some of the frequencies may be eliminated without impairing the result of strong, so that the amount of data to be stored can be reduced in this way.
  • VLF reception with the PC
  • Broadband data transmission via OFDM, the basis for ADSL and Wi-Fi ( Internet ), DVB -T ( TV ), DRM, DAB ( radio) and LTE ( 4th generation mobile communications ) is. Here, the high speed is achieved, that many relatively slow data transfers operate in many carrier frequencies simultaneously. The complex signal formed by the superposition of the individual signals is then separated from the counterpart by means of the FFT signal again into single carrier.
(2) Pallas Carl David Tolmé Runge Trigonometry Unit (ring theory) Binary multiplier Bluestein's FFT algorithm Symbolic mathematics Signal analysis Convolution#Fast convolution algorithms Asymmetric Digital Subscriber Line
327202
de