I believe that everything is general outline know about the existence of such a wonderful mathematical tool as the Fourier transform. However, for some reason it is taught so poorly in universities that relatively few people understand how this transformation works and how it should be used correctly. Meanwhile, the mathematics of this transformation is surprisingly beautiful, simple and elegant. I invite everyone to learn a little more about the Fourier transform and the related topic of how analog signals can be effectively converted into digital ones for computational processing.
Without using complex formulas and Matlab, I will try to answer the following questions:
- FT, DTF, DTFT - what are the differences and how do seemingly completely different formulas give such conceptually similar results?
- How to Correctly Interpret Fast Fourier Transform (FFT) Results
- What to do if you are given a signal of 179 samples and the FFT requires an input sequence of length equal to a power of two
- Why, when trying to obtain the spectrum of a sinusoid using Fourier, instead of the expected single “stick”, a strange squiggle appears on the graph and what can be done about it
- Why are analog filters placed before the ADC and after the DAC?
- Is it possible to digitize an ADC signal with a frequency higher than half the sampling frequency (the school answer is incorrect, the correct answer is possible)
- How to restore the original signal using a digital sequence
I will proceed from the assumption that the reader understands what an integral is, a complex number (as well as its modulus and argument), convolution of functions, plus at least a “hands-on” idea of what the Dirac delta function is. If you don’t know, no problem, read the above links. Throughout this text, by “product of functions” I will mean “pointwise multiplication”
We should probably start with the fact that the usual Fourier transform is some kind of thing that, as you can guess from the name, transforms one function into another, that is, it associates each function of a real variable x(t) with its spectrum or Fourier image y (w):
If we give analogies, then an example of a transformation similar in meaning can be, for example, differentiation, turning a function into its derivative. That is, the Fourier transform is essentially the same operation as taking the derivative, and it is often denoted in a similar way by drawing a triangular “cap” over the function. Only in contrast to differentiation, which can also be defined for real numbers, the Fourier transform always “works” with more general complex numbers. Because of this, there are always problems with displaying the results of this conversion, since complex numbers are determined not by one, but by two coordinates on a graph operating with real numbers. The most convenient way, as a rule, is to represent complex numbers in the form of a modulus and an argument and draw them separately as two separate graphs:
The graph of a complex value argument is often called in in this case“phase spectrum”, and the module graph - “amplitude spectrum”. The amplitude spectrum is usually of much greater interest, and therefore the “phase” part of the spectrum is often skipped. In this article we will also focus on “amplitude” things, but we should not forget about the existence of the missing phase part of the graph. In addition, instead of the usual module of a complex value, its decimal logarithm multiplied by 10 is often drawn. The result is a logarithmic graph, the values of which are displayed in decibels (dB).
Please note that not very much negative numbers logarithmic graph (-20 dB or less) in this case correspond to almost zero numbers on the “normal” graph. Therefore, the long and wide “tails” of various spectra on such graphs, when displayed in “ordinary” coordinates, as a rule, practically disappear. The convenience of such a strange at first glance representation arises from the fact that the Fourier images of various functions often need to be multiplied among themselves. With such pointwise multiplication of complex-valued Fourier images, their phase spectra are added, and their amplitude spectra are multiplied. The first is easy to do, while the second is relatively difficult. However, the logarithms of the amplitude add up when multiplying the amplitudes, so logarithmic amplitude graphs can, like phase graphs, simply be added pointwise. In addition, in practical problems it is often more convenient to operate not with the “amplitude” of the signal, but with its “power” (the square of the amplitude). On a logarithmic scale, both graphs (amplitude and power) look identical and differ only in the coefficient - all values on the power graph are exactly twice as large as on the amplitude scale. Accordingly, to plot the power distribution by frequency (in decibels), you can not square anything, but calculate the decimal logarithm and multiply it by 20.
Are you bored? Just wait a little longer, we'll be done with the boring part of the article explaining how to interpret graphs soon :). But before that, there is one very important thing to understand: although all the above spectra plots were drawn for some limited ranges of values (in particular, positive numbers), all these graphs actually continue to plus and minus infinity. The graphs simply depict some “most meaningful” part of the graph, which is usually mirrored for negative values of the parameter and is often repeated periodically with a certain step when viewed on a larger scale.
Having decided what is drawn on the graphs, let's return to the Fourier transform itself and its properties. There are several different ways how to determine this transformation, differing in small details (different normalizations). For example, in our universities, for some reason, they often use the normalization of the Fourier transform, which defines the spectrum in terms of angular frequency (radians per second). I will use a more convenient Western formulation that defines the spectrum in terms of ordinary frequency (hertz). The direct and inverse Fourier transforms in this case are determined by the formulas on the left, and some properties of this transformation that we will need are determined by a list of seven points on the right:
The first of these properties is linearity. If we take some linear combination of functions, then the Fourier transform of this combination will be the same linear combination of the Fourier images of these functions. This property allows you to reduce complex functions and their Fourier transforms to simpler ones. For example, the Fourier transform of a sinusoidal function with frequency f and amplitude a is a combination of two delta functions located at points f and -f and with coefficient a/2:
If we take a function consisting of the sum of a set of sinusoids with different frequencies, then according to the property of linearity, the Fourier transform of this function will consist of a corresponding set of delta functions. This allows us to give a naive but visual interpretation of the spectrum according to the principle “if in the spectrum of a function frequency f corresponds to amplitude a, then the original function can be represented as a sum of sinusoids, one of which will be a sinusoid with frequency f and amplitude 2a.” Strictly speaking, this interpretation is incorrect, since the delta function and the point on the graph are completely different things, but as we will see later, for discrete Fourier transforms it will not be so far from the truth.
The second property of the Fourier transform is the independence of the amplitude spectrum from the time shift of the signal. If we move a function to the left or right along the x-axis, then only its phase spectrum will change.
The third property is that stretching (compressing) the original function along the time axis (x) proportionally compresses (stretches) its Fourier image along the frequency scale (w). In particular, the spectrum of a signal of finite duration is always infinitely wide and, conversely, the spectrum of finite width always corresponds to a signal of unlimited duration.
The fourth and fifth properties are perhaps the most useful of all. They make it possible to reduce the convolution of functions to a pointwise multiplication of their Fourier images, and vice versa - the pointwise multiplication of functions to the convolution of their Fourier images. A little further I will show how convenient this is.
The sixth property speaks of the symmetry of Fourier images. In particular, from this property it follows that in the Fourier transform of a real-valued function (i.e., any “real” signal), the amplitude spectrum is always even function, and the phase spectrum (if brought to the range -pi...pi) is odd. It is for this reason that the negative part of the spectrum is almost never drawn on spectrum graphs - for real-valued signals it does not provide any new information (but, I repeat, it is not zero either).
Finally, the last, seventh property, says that the Fourier transform preserves the “energy” of the signal. It is meaningful only for signals of finite duration, the energy of which is finite, and suggests that the spectrum of such signals at infinity quickly approaches zero. It is precisely because of this property that spectrum graphs usually depict only the “main” part of the signal, which carries the lion’s share of the energy - the rest of the graph simply tends to zero (but, again, is not zero).
Armed with these 7 properties, let's look at the mathematics of signal “digitization”, which allows you to convert a continuous signal into a sequence of numbers. To do this, we need to take a function known as the “Dirac comb”:
A Dirac comb is simply a periodic sequence of delta functions with unity coefficient, starting at zero and proceeding with step T. For digitizing signals, T is chosen as small a number as possible, T<<1. Фурье-образ этой функции - тоже гребенка Дирака, только с гораздо большим шагом 1/T и несколько меньшим коэффициентом (1/T). С математической точки зрения, дискретизация сигнала по времени - это просто поточечное умножение исходного сигнала на гребенку Дирака. Значение 1/T при этом называют частотой дискретизации:
Instead of a continuous function, after such multiplication, a sequence of delta pulses of a certain height is obtained. Moreover, according to property 5 of the Fourier transform, the spectrum of the resulting discrete signal is a convolution of the original spectrum with the corresponding Dirac comb. It is easy to understand that, based on the properties of convolution, the spectrum of the original signal is “copied” an infinite number of times along the frequency axis with a step of 1/T, and then summed.
Note that if the original spectrum had a finite width and we used a sufficiently high sampling frequency, then the copies of the original spectrum will not overlap, and therefore will not sum with each other. It is easy to understand that from such a “collapsed” spectrum it will be easy to restore the original one - it will be enough to simply take the spectrum component in the region of zero, “cutting off” the extra copies going to infinity. The simplest way to do this is to multiply the spectrum by a rectangular function equal to T in the range -1/2T...1/2T and zero outside this range. Such a Fourier transform corresponds to the function sinc(Tx) and according to property 4, such a multiplication is equivalent to the convolution of the original sequence of delta functions with the function sinc(Tx)
That is, using the Fourier transform, we have a way to easily reconstruct the original signal from a time-sampled one, working provided that we use a sampling frequency that is at least twice (due to the presence of negative frequencies in the spectrum) higher than the maximum frequency present in the original signal. This result is widely known and is called the “Kotelnikov/Shannon-Nyquist theorem”. However, as it is easy to notice now (understanding the proof), this result, contrary to the widespread misconception, determines sufficient, but not necessary condition for restoring the original signal. All we need is to ensure that the part of the spectrum that interests us after sampling the signal does not overlap each other, and if the signal is sufficiently narrowband (has a small “width” of the non-zero part of the spectrum), then this result can often be achieved at a sampling frequency much lower than twice the maximum frequency of the signal. This technique is called “undersampling” (subsampling, bandpass sampling) and is quite widely used in processing all kinds of radio signals. For example, if we take an FM radio operating in the frequency band from 88 to 108 MHz, then to digitize it we can use an ADC with a frequency of only 43.5 MHz instead of the 216 MHz assumed by Kotelnikov’s theorem. In this case, however, you will need a high-quality ADC and a good filter.
Let me note that “duplication” of high frequencies with frequencies of lower orders (aliasing) is an immediate property of signal sampling that irreversibly “spoils” the result. Therefore, if the signal can, in principle, contain high-order frequencies (that is, almost always), an analog filter is placed in front of the ADC, “cutting off” everything unnecessary directly in the original signal (since after sampling it will be too late to do this). The characteristics of these filters, as analog devices, are not ideal, so some “damage” to the signal still occurs, and in practice it follows that the highest frequencies in the spectrum are, as a rule, unreliable. To reduce this problem, the signal is often oversampled, setting the input analog filter to a lower bandwidth and using only the lower part of the theoretically available frequency range of the ADC.
Another common misconception, by the way, is when the signal at the DAC output is drawn in “steps”. “Steps” correspond to the convolution of a sampled signal sequence with a rectangular function of width T and height 1:
The signal spectrum with this transformation is multiplied by the Fourier image of this rectangular function, and for a similar rectangular function it is again sinc(w), “stretched” the more, the smaller the width of the corresponding rectangle. The spectrum of the sampled signal with such a “DAC” is multiplied point by point by this spectrum. In this case, unnecessary high frequencies with “extra copies” of the spectrum are not completely cut off, but the upper part of the “useful” part of the spectrum, on the contrary, is attenuated.
In practice, of course, no one does this. There are many different approaches to constructing a DAC, but even in the closest weighting-type DACs, the rectangular pulses in the DAC, on the contrary, are chosen to be as short as possible (approaching the real sequence of delta functions) in order to avoid excessive suppression of the useful part of the spectrum. “Extra” frequencies in the resulting broadband signal are almost always canceled out by passing the signal through an analog low-pass filter, so that there are no “digital steps” either “inside” the converter, or, especially, at its output.
However, let's go back to the Fourier transform. The Fourier transform described above applied to a pre-sampled signal sequence is called the Discrete Time Fourier Transform (DTFT). The spectrum obtained by such a transformation is always 1/T-periodic, therefore the DTFT spectrum is completely determined by its values on the segment )