Discrete Fourier Transform (DFT)

Often in the literature on digital signal processing, the expression for the discrete Fourier transform (DFT) is given “as a given”, and the expression for the direct and inverse DFT is not given due attention. However, an understanding of this transition will make it possible to better understand the properties of the DFT and the essence of digital spectral analysis as a whole. To begin with, we also write down the expressions for the continuous and discrete Fourier transform, and then we go to the DFT from the Fourier integral.

Time sampling. Discrete signal spectrum

So a pair of continuous Fourier transform (Fourier integral) has the form:

The expressions for the direct DFT and inverse discrete Fourier transform (IDFT) are:

The expression for the DFT matches signal readings , , generally integrated, spectrum readings , .

It can be noted that, both in the continuous and in the discrete case, there is a normalization coefficient in the expression for the inverse transformation. In the case of the Fourier integral, this in the case of ODPP - . It can be noted that in the case of continuous conversion, the normalization coefficient It is designed to correctly display the scaling of the signal in time in the frequency domain and vice versa. In other words, if we sequentially calculate the spectrum of a certain signal, and then take the inverse Fourier transform, then the result of the inverse transform should completely coincide with the original signal. Normalization factor reduces the amplitude of the signal at the output of the inverse transform so that it coincides with the amplitude of the original signal.

Consider now the signal as a result of multiplying a continuous signal on the lattice function

We calculate the spectrum of a discrete signal, for this we substitute the expression for the discrete signal (3) in the expression for the Fourier transform (1), we get:

Swap the operations of summation and integration and recall the filtering property of the delta function:

Then the expression (5) in view of (6):

Thus, we got rid of the integration in infinite limits, replacing the complex summation of the complex exponentials. But while the frequency varies on the entire number axis. However, it can be noted that the complex exponents under the sum sign in expression (7) are periodic functions with a period:

It should be noted that excluded from expression (8), since complex exponent is one for all frequencies. Thus the maximum repetition period of the spectrum will be at and is equal to

As a result, only one repetition period can be considered. at

The repetition of the signal in time. Discrete Fourier Transform

Digital processing requires both discrete signal samples and discrete spectrum samples. It is known that the discrete (or as they say line spectrum) have periodic signals, and the line spectrum is obtained by expanding the Fourier series of a periodic signal. So, to get a discrete spectrum, you must make the original discrete signal periodic, or in other words you must repeat this signal in time an infinite number of times with a certain period then its spectrum will contain discrete harmonics multiple . Graphically, the process of repeating a signal in time is presented in Figure 2.

The original signal is shown in black, its repetition is grayed out after a certain period. .

As follows from Figure 2, the signal can be repeated with a different period. However, it is necessary that the repetition period be more than or equal to the duration of the signal, i.e. . The minimum repetition period of the signal

This is the minimum period at which the signal and its repetition do not overlap each other. Repetition signal with a minimum period presented in Figure 3.

By repeating a signal with a minimum period, we obtain a line spectrum of the signal, consisting of harmonics of multiples

Thus, we can discretize the spectrum of a discrete signal in one repetition period. with step and thereby spectrum readings. We take into account the above in expression (7), we get:

If we omit in the expression (13) the discretization time step and by frequency then we get the final expression for the DFT:

It can be concluded that the DFT sets discrete signal samples samples of the discrete spectrum, while it is assumed that both the signal and the spectrum are periodic and analyzed on the same period.

Details of the DFT properties will be analyzed below. We will deal with the withdrawal of the PDPF.

Similarly to (3), we can write the expression for the discrete spectrum through the lattice function

Take discrete samples after interval , then (17) can be written:

We take into account (11) and get:

Omitting the frequency and time sampling intervals in expression (19), leaving only the indices, we obtain an expression for the IDFTs in which the coefficient of proportionality is unknown:

In order to calculate the coefficient , it is necessary to substitute the expression for calculating the spectrum using the DFT (14) in the expression for IDFT (20), we get:

Swap the summation procedure in (21) and combine the exponents:

Let us consider in more detail the sum of the complex exponentials included in (22). With we get:

Now consider the same amount when . Let be then we get:

Then each complex exponent included in the sum is a vector on the complex plane of unit length, rotated by an angle:

From Figure 4, it is indeed possible to conclude that for all , , , , sums of complex exponentials (24) are really zero. Then in expression (22) of the amount of will only add to . Then you can write (22):

From (26) we can conclude that . Thus, the expression for IDFT can be finally written down:

Indexing spectral samples. Rearrangement of spectral samples

Thus, we obtained expressions for both the direct and inverse DFTs. We make a few comments.

Remark 1. The DFT and ODPF are calculated on the basis of time indices. and spectral counts without taking into account the sampling frequency. This allows the use of expressions for the DFT and IDFT at any sampling rate without changing the computational program. This is a definite plus of the DFT, and if you need to link the indices to the sampling frequency (to the real frequency axis), then you need to remember that the frequency spectrum was sampled in increments rad / c, or Hz where , - sampling rate in Hz. Thus, if the sampling rate is known, then - th spectral count corresponds to frequency happy / c or Hz For example, at the sampling rate kHz with , spectral count corresponds to the frequency kHz

Remark 2. The discretization of the spectrum in the DFT was carried out on one period of the repetition of the spectrum. . Moreover, due to the periodicity of the spectrum of a discrete signal, the samples at correspond to both frequencies and frequencies where , i.e at correspond to negative frequencies i.e. physically at the second half of the spectrum is the frequencies from - . This is vividly illustrated by figure 5. In order from the spectrum in the frequency range calculated using the discrete Fourier transform, obtain the spectrum of the signal in the interval it is necessary to swap the two halves of the spectral samples (see figure 5).

Note 3. If the original signal is valid, i.e. for then

Zero spectrum report is a constant component of the signal. If a - even, then

The central spectral reading also has no imaginary part.

Consider now , and :

Consider that , then we can conclude: , that is, the second half of the spectral samples is complexly coupled with the first. Figure 6 shows a view of the real and imaginary parts of the complex spectrum of the real signal with an even . Red marked pure real and .

In this article, we made the transition from the Fourier integral to the discrete Fourier transform by sampling the signal both in time and frequency. We obtained expressions for the direct and inverse DFT and considered some properties of the DFT. The properties of the DFT will be discussed in more detail in the following articles.