Discrete Fourier transform

The discrete Fourier transform or DFT is a transformation from the region of the Fourier analysis. It forms a time-discrete, finite signal which is periodically continued on a discrete periodic frequency spectrum, which is also referred to as the image area. The DFT has for signal analysis of great importance in the digital signal processing. Here you can find optimized variants in the form of the fast Fourier transform ( english Fast Fourier Transform, FFT) and its inverse application.

DFT is used in the signal processing for many tasks, such as

• To determine the in a sampled signal mainly occurring frequencies,
• For the determination of the individual amplitudes of these frequencies
• For the implementation of digital filters with large filter lengths

Of the inverse DFT may be reconstructed in the time domain of the short IDFT frequency components again the signal. By coupling of the DFT and IDFT, a signal can be manipulated in the frequency domain as applied in the equalizer. The discrete Fourier transformation is related by the Fourier transform of time-discrete signals (English Discrete -Time Fourier Transform, DTFT ) to distinguish the form of time-discrete signals, a continuous frequency spectrum.

• 3.1 Simple aperture
• 3.2 Picture with periodic structures

• 5.1 discretization of the Fourier transform
• 5.2 Discretization of a Fourier series

• 6.1 Spectrum of sampled functions
• 6.2 aliasing
• 6.3 DFT of a time-limited function
• 6.4 leakage effect ( leakage effect)
• 6.5 Sliding DFT as a band filter bank
• 6.6 uncertainty relation of the sliding DFT

Definition

The discrete Fourier transform processing, a sequence of numbers which are formed, for example, as the measurement values ​​from a period of a periodic signal. The entries of the sequence are as values ​​of a polynomial

Presented with complex coefficients. The arguments N points are chosen on the unit circle of the complex plane, which are uniformly distributed, that is, the N- th roots of unity

If now the polynomial A (z) associated with a uniformly the unit circle rotating function, this results in a continuous-time periodic function

Assumes the at times just the function values ​​. The powers of z (t) have the form of

And hence the period T / k and the frequency k / T and the angular frequency. Thus the sequence of the measured values ​​has been shown and interpolated by the superposition of a constant level for k = 0, a basic vibration when k = 1, and harmonics at k > 1.

These above mentioned interpolation is not the only one that can be constructed in this way. Each of the functions

Has this interpolation property.

DFT and IDFT of a complex vector

The discrete Fourier transform of a complex vector, the coefficients

This is called the even Fourier coefficients or Fourier components.

The inverse DFT ( IDFT ) of the coefficients has

Special case: DFT of a real vector

Certain symmetry laws apply as for the Fourier transform for the DFT. Thus, a real signal in the period to a Hermitian signal () in the frequency domain:

This means that in the frequency domain are present only independent complex coefficients. This fact can be utilized in the implementation of the DFT, it is known that the input signal is purely real. Are then used for the representation of the result do not (as with the full DFT ), but only complex numbers necessary. The other complex numbers can be reconstructed by elementary calculation (see formula above). The hermitian symmetry refers to the middle element of the signal.

Conversely accordingly: Meets the requirement for all and so the inverse DFT is a real vector.

Generalization: Mathematical definition of the DFT

In mathematics, the discrete Fourier transform is considered in a very general context. It is among other things in the computer algebra in a variety of efficient algorithms for exact arithmetic application, for example in rapid multiplication of integers with Schönhage - road algorithm.

Is a commutative unitary ring in which the number (which is the sum of the times ) is one unit. Furthermore, there is a primitive root of unity. At a " vector" is then the discrete Fourier transform by

Explained. Under the given conditions in order to exist, the discrete inverse Fourier transform with the coefficients

In the all-important special case of the root of unity is used for the DFT usually. This results in the formula in the first section.

Multidimensional DFT

The DFT can be easily extended to multi-dimensional signals. You will then be applied once on all coordinate directions. In the important special case of two dimensions ( image processing ) is approximately valid:

For and

The inverse transformation is accordingly:

For and

Shifting and scaling in the time and frequency

In the calculation of DFT and IDFT formulas, the summation ( index variable above) rather than just running over a shifted range when the vector is periodically continued to all integer indices, because it is. So we can move the summation limits arbitrarily, as long as a segment of length N is swept into the integers.

Let us now turn back to the complex case. In practical applications, one would like to combine the indices with an equidistant sequence of time points,

Which also has the length N. It is also desirable to assign the frequencies calculated coefficients which are centered about 0

K near N / 2

One of the selected points in time " measured " function returns the observation vector with the coefficients, the DFT is taken in the Fourier analysis. Then

And

Examples

The Fourier transform transforms a function f (t ) to g ( ν ) * t from a time chart in the reciprocal space frequency ν: = 1 / t. This also applies to local features that are defined on a (1D ), two ( 2D) or more spatial directions. These are converted by the Fourier transform, one by one in each direction in space frequencies. Diffraction phenomena in the optical or X-ray analysis can be interpreted directly as the intensity distribution of a Fourier transform. The phase relationship is what photography is normally lost. Only in the case of holography, the phase relationship is recorded by superimposition with a reference beam.

Simple aperture

The pictures on the right illustrate two-dimensional Fourier transformation ( 2D FFT) on geometric patterns, calculated for squares of discrete size of a × a pixel. The picture above left shows a gap of size e × f pixels, next to the intensity distribution of the diffraction pattern. The spatial variable r is converted into reciprocal complex values ​​r *. At the selected one pixel sizes is transferred to the reciprocal value of 1 / a reciprocal pixels. The width of the gap by e pixels appear in the reciprocal space as the value of the variable r * = a / e, the height r * = a / f, with harmonic frequencies of higher order. The calculated diffraction patterns indicate the intensity distributions of the complex variable r * again. That they carry only half of the image information can be identified by their rotational symmetry.

The periodic peaks correspond to the spatial frequencies of higher order of a square wave. Similar examples can be found under the headings of Fourier analysis, Fourier transform, or Airy disk.

In the second field a regular hexagon is diffracted. Again, the size of the figure appears as a period in the diffraction image to the right. 6- fold symmetry is clearly visible. A shift of the output image - as opposed to a rotation - would have an impact only in the phase relationship that is not visible in the chosen representation as intensity distribution.

The lower part of image on the right shows the calculated diffraction pattern of a triangle. The 6- fold symmetry is only feigned, which can be seen in the lack of modulation of the diffraction star.

The second image series compares the diffraction of two circular openings. A large circle creates a small diffraction pattern, and vice versa. In a telescope, the light diffraction limits the resolution of the lens opening. The larger the diameter, the smaller the diffraction image of a star, the better closely spaced star be differentiated.

The image below is an example of a diffraction at a circular structure with no sharp boundary. With a sinusoidal intensity decrease at the wheel occur no higher order diffractions (see also zone plate ).

Image with periodic structures

The image on the left shows a SAR image of the Indian Ocean with water waves of different wavelengths. The internal waves top right have a wavelength of about 500 m. The surface waves generated by wind can not be seen in the reduced representation. The calculated diffraction pattern of the two dark reflections give (see short arrow ), both the direction and the mean wavelength of the regular long-period water waves. The wavelengths of the surface wave varies strongly, so they do not provide sharp reflexes. There are two excellent directions for the wave propagation, which are only dimly visible in the direct image. The wavelengths are approximately 150 m (long arrow ) and 160 m (slightly shorter arrow).

Mathematical basis

Occurring in the discrete Fourier transformation complex numbers

Are the N-th roots of unity, that is, they are solutions of the equation. Be the "smallest ", ie primitive root in the first quadrant. This satisfies the following identity geometric sums of roots of unity:

Because: for.

This is the " deep reason " why the inverse DFT works.

We define the vectors, n = 0, ..., N-1, they form an orthonormal basis for the inner product

It is

Each vector may be represented in the orthonormal basis:

The coefficients are called ( in general with arbitrary orthonormal ) Fourier coefficients, ie the DFT maps a vector x to within an additive constant of the vector X = DFT ( x) of the Fourier coefficients.

Y = DFT (y ) to a further vector, the Parseval equation for the Fourier coefficient is considered:

Interpretations of the DFT

Discretization of the Fourier transform

The Fourier transform allows functions with real argument ( and various constraints such as: integrability, waste at infinity ) to think composed of vibrations:

An important finding of the Fourier theory is that the amplitude can be determined similar to

If we choose a radius R such that outside the interval [-R, R ] is only an insignificant part of f, f is also continuous and a number N chosen so large that T: = R / N is small enough, to f singular sense, i.e., the function values ​​f ( kT) to scan, the Fourier integral can be replaced useful in the transformation formula is represented by a sum of:

This corresponds, up to a constant factor, the calculation formula of the DFT. The vector x = (f ( NT ), ..., f ( NT) ) has 2N 1 elements. We already know that it is sufficient that the frequency coefficients for the frequencies of 2N 1, n = -N, ..., -1,0,1, ..., to N, determined in order to reconstruct the function values ​​in the vector x. With the necessary adjustment of the constants in the IDFT we obtain

Diskretisierungsabstand the frequency domain is proportional to 1 / R, that is, by assumption, is also small, so that the calculation of the discretization of the inverse Fourier transform corresponds.

In the transition from the Fourier transform to the DFT so the following changes are noted:

• The signal is discrete, equidistant time points before (T: distance between two consecutive time points), 0 is one of these time points.
• The signal has a finite length (2N 1: the number of values ​​), which are interpreted as values ​​within a large interval [- NT, NT ].
• The integrals in the calculation of the Fourier coefficients in the DFT to totals.
• The spectrum is calculated only for a finite number of (circular ) frequencies ( ω = (2 π ) · n / ( (2N 1) · T), n = -N, ..., -1,0, 1, 2, ..., N) and is periodic in frequency, the period (2 π ) / T by assumption (T small) is very large.

Discretization of Fourier series

Any periodic function with a real argument (and again restrictions as: integrability, no poles ) and period L can have as a function series with sinusoids that are fractions of L as period are shown ( so-called Fourier series ):

Let's break the series expansion for large limits below 1-M and NM from above, we obtain with T: = L / N

, That is, we obtain a form of the inverse DFT. Thus, the DFT coefficients can be approximated to

In the limiting case of an infinitely large N, the known coefficients of integrals of Fourier series result:

Properties

Spectrum of sampled functions

The discrete Fourier transform has a periodic spectrum which is repeated at the sampling frequency and is symmetrical with respect to the sampling frequency. The following applies:

If the sampled signal frequency components above half the sampling frequency, the spectra of the original signal with the mirrored at the sampling frequency signal components overlap, and it comes to aliasing.

Aliasing

In general, the time-discrete signal is formed by discretization of a continuous signal. The products resulting from the DFT spectra are only identical to the spectra of the underlying continuous signal, if in sampling, the sampling was not injured. For signals in the baseband will be that the sampling frequency must be more than twice as large as the maximum occurring frequency ( Nyquist frequency). In violation of the sampling occurs a distortion of the original signal on (aliasing in the time domain ). A possibility of anti-aliasing, the band limiting of the signal at the input of the system, to avoid this effect.

DFT of a time-limited function

For periodic functions results ( in analogy to the continuous Fourier Transform) is a line spectrum with a frequency spacing of 1/Periodenlänge.

A timed discrete function g ( kT) can be derived from a periodic discrete function f ( kT) by precisely cutting out a period over a time window w (t).

Since the Fourier transform corresponds to a multiplication of functions in the time domain convolution of the Fourier transform in the frequency domain, the DFT of the time-limited function G ( ω ) is given by the convolution of the DFT of the periodic function F ( ω ) of the Fourier transform the time window W ( ω ).

The result is a line spectrum, which is smeared by the Fourier transform of the time window. In Fig.3 shown on the right by broken lines, the influence of the time window on the DFT of the periodic function (thick lines). Due to the time limit frequency components are added between the analyzed frequency lines.

By the transition of a periodic function of a time-limited function does not have to be changed, the calculation procedure for the determination of the spectrum. It will continue to be calculated discrete frequency lines, as if a periodic function stands behind it. As an effect of the time window each calculated frequency line now is representative of an entire frequency range, namely the frequency range which is added by the Fourier transform of the time window. This behavior is also called leakage effect.

Leakage effect ( leakage effect)

Due to the temporal limitation of the signal, it may happen that the input signal is cut off. A clipped input signal can only be transformed to the correct DFT if it is periodically resumable. If the signal is not periodically be continued, it contains frequencies that do not belong to the one calculated by the DFT discrete frequencies. The DFT " approaches " these frequencies by the adjacent frequencies, while the energy is distributed to these frequencies. This is called leakage effect (English leakage effect).

The time limit is a multiplication with a square wave function equal to and corresponds to a convolution with a sinc function in the frequency domain. This is a different approach to the leakage effect to explain. This is also true in the case of other window functions (such as Hamming, Hann, Gaussian ). Thus, the spectrum of the window function ( or the width of the spectrum) is decisive for the leakage. The amplitude accuracy is the other criterion of a window function.

Sliding DFT as a band filter bank

A DFT of a time-limited function can also be regarded as a band filter bank.

• The center frequencies of these band filter corresponding to the frequency lines of the function that arises when the considered period repeated periodically (multiples of 1/Fensterbreite ).
• The width and slope of the bandpass filter is determined by the Fourier transform of the time window.

(see Fig.3 )

By selecting an appropriate time window function can change the characteristics of the bandpass filter.

• With a square -shaped window with points of discontinuity at the window boundaries frequencies are attenuated outside of the transmission range of the bandpass filter with 1/frequency; are obtained slopes between 6 dB / octave (see Fig.2)
• If the window function continuous, frequencies are attenuated outside the transmission range of the bandpass filter with 1/Frequenz2; we achieved higher slope of 12 dB / octave
• Is the 1st derivative of the window function continuous, frequencies are attenuated outside the transmission range of the bandpass filter with 1/Frequenz3; the slope is 18 dB / octave
• Etc.

By determining the Fourier transform of each of successive time intervals to obtain the sliding Fourier transform. With the analysis of a new time interval is then obtained new samples for the time course of spectral lines (i.e., the timing of the signals at the outputs of the " band filter ").

Uncertainty relation of the sliding DFT

Time and frequency resolution of the sliding DFT can not be chosen independently.

• If you want to analyze signals with high frequency resolution, you have to make the time window very large, you get a low time resolution.
• Do you need a high time resolution, you have to make the width of the time window is very short, but then one can determine only a few frequency lines.
• The following applies: frequency resolution ≈ 1/Zeitfensterbreite ( a frequency resolution of 1 kHz is desired, the time window must be at least 1 ms ).

FFT

For block length N, which can be represented as a power of 2, the calculation using the algorithm of the fast Fourier transform ( FFT) can be done. In general: Can be factorized the block length, N = KM, so there is a decomposition of the DFT of length N into a product of DFTs of lengths K and M as well as two simple matrices.

Goertzel algorithm

For any block length N, and for determining a single or a few spectral components, the Goertzel algorithm can be used. The advantage is a very efficient implementation in a computer system, since the calculation of each spectral component includes only a complex multiplication and two complex additions.

Applications

• Calculating the Fourier transform of a signal.
• Signal analysis.
• Vibration analysis and modal analysis.
• Processing of signals.
• Calculation of correlations.
• Calculation of Polynomprodukten in O (n * log ( n ) )

In the calculation of surface acoustic wave filters ( = SAW filters = SAW filter = surface acoustic wave - filter) - Fourier transform of the transfer function required ( represents the impulse response ), the inverse is. This task is handled by computers.