Understanding the Discrete Fourier Transform and the FFT

Imagine you are running vibration analysis on some piece of hardware you are developing. And the hardware is on a vibrating table that applies random vibrations to the hardware. And you measure how the hardware responds with accelerometers. This measurement is captured with a digital computer. And so what you get is a finite amount of data that is sampled at regular intervals. Now, in the case of vibrations, as in many other applications, it is often useful to observe the spectrum of the signal, that is, to separate the signal in the time domain into the frequency components that compose it.

And, once we have frequency information, we can now choose to look at the amplitude spectrum or the power spectrum or the power spectral density. And each of these provides insight into the signal that we can't get from the time domain alone. Now, with finite and

discrete

data, like what we have here, the first step in arriving at any of these representations is the Discrete Fourier Transform, or DFT. And the most efficient way to calculate the DFT is to use a fast Fourier

transform

or FFT algorithm. So for this video, what I want to do is answer some common questions you may have about DFT and FFT.

I think it will be quite interesting and useful. So I hope you stay there. I'm Brian and welcome to a MATLAB technical talk. Okay, so to start our first question, we want to ask: why do we use the

discrete

Fourier

transform

? Well, DFT transforms a signal from the time domain or a spatial domain like distance to the frequency domain. And one of the main reasons for performing this transformation is that the characteristics of a signal that we are interested in are not always obvious in the temporal or spatial domain. For example, here I have two time domain signals that are sampled at 200 hertz.

And the question I have for you is: which of these has a significant 60 hertz component? It's not very obvious, is it? They both look quite similar. But if we transform them to the frequency domain, it is much easier to answer. I mean, it's clearly this first signal because there's a big 60 Hz peak. So we can use the frequency domain to understand the frequency composition of a signal. To understand how DFT is performing this transformation, we need to look at Eq. And I know there are a lot of symbols here, but it's actually pretty simple. This blue x sub n variable is the discrete time domain signal we started with.

And we are going to transform it into the signal in the frequency domain x sub k. And, to do this, we multiply the time signal by this yellow part, which is raised to a complex number. And if you're not familiar with complex exponentials, this is equal to the cosine of the exponent plus i multiplied by the sine of the exponent. So essentially what DFT does is multiply the time signal by a sine and cosine signal of a particular frequency given by this variable k. And then it's adding the result. And we do this sum for different values ​​of k, or for different frequencies.

Alright, now I think we can get a little insight into how this equation works with just a simple graphical demonstration. Alright, I created a little MATLAB application here to show you how DFT works. Here the x sub n time signal is simply a pure sine wave with 10 samples. So, according to the DFT definition, we multiply this signal with e raised to an imaginary exponent, which I call all of this the correlative signal. And hopefully the name will make sense soon. Now, if we set k equal to 0, then our correlation signal is simply e to the power of 0, which produces a constant real value of 1 and an imaginary value of 0.

And, when we multiply this with our time signal and then add the result, we obtain a value that is really low. And mathematically, this is because when we multiply the timing signal by 1, we get exactly the same signal. And so, essentially, we're just adding the values ​​in our timing signal. And there are equal positive values ​​(they are these four here) and negative values, which are these four. And then they cancel each other out until close to 0. And the way we can think of this really low value is that our signal in the time domain is not very correlated with a signal with 0.

Frequency. Now let's move on to a new set of frequencies, say, k is equal to 1. Our correlation signal now consists of a sine and cosine wave with a period equal to the length of the time signal. And if we multiply them by x sub n and then add the result, the value is greater. And we can visually see that the correlated signal is close to the same frequency as our time signal. And so, at least for the imaginary component, which is perfectly out of phase with our temporal signal, the product of 2 is always negative. And, therefore, the sum will also be negative.

So there is a strong correlation between the two at k equals 1. And if we move to k equals 2, the correlation drops again. And this is all the DFT is doing. It goes through n different frequencies where k goes from 0 to n minus 1 and calculates the correlation between this and the time signal. It's cool that we can think of DFT as producing the correlation between our timing signal and a bunch of different frequencies. But there is another interesting way we can think about DFT. And that's like a rotation with matrix multiplication. If we go back to the equation, we can rewrite it as matrix multiplication. x sub n is just a 1 by n vector of discrete time data.

And the yellow exponential is an n by n matrix of complex numbers. And the first column is the sines and cosines associated with k equals 0. And the second column is k equals 1, and so on, until k equals n minus 1. And now, when you do this multiplication, for the first component of x of sub k, we get the inner product between the time signal and the frequencies at k equals 0. The second component is the inner product with k equals 1 and so on, until the end. So this way, it's a little bit easier to see that the DFT is doing this rotation between one set of basis functions, this x sub n, to another, this capital X of k.

And this n by n matrix is ​​what achieves this rotation of time to complex exponentials. And actually, this is a nice transition to the fast Fourier transform. This matrix multiplication is easy to perform if the signal length is relatively short. If there are only 10 samples, then this is a 10 by 10 matrix. But if you are working with a signal that has thousands or tens of thousands of samples, performing this matrix multiplication could be computationally expensive. But it turns out that, due to various symmetries in this multiplication, many operations are duplicated. And then you can perform a calculation once and then complete that answer in multiple locations.

And FFT algorithms take advantage of duplicate operations to reduce the amount of overhead calculations. Therefore, they produce exactly the same result as DFT, just in a more efficient way. And, for a good explanation of the FFT algorithm and how these computational efficiencies really made DFT a viable option for science and engineering, check out Veritasium's excellent video on the topic. The link is in the description below. Alright, now that we know that foot is just an efficient way to calculate DFT, I want to use the last part of this video to answer some practical questions and dive a little deeper into how we use and interpret the results.

And the first question is: why do we sometimes just look at the absolute value of the FFT? Well, let's remember that the ft produces a complex result. And the way we can interpret this is that the real part of the FFT is how well the temporal signal correlates with a cosine wave of a given frequency. And the imaginary part is how well it correlates with a sine wave of the same frequency. And knowing both is necessary if you want to know the phase of the frequency in your original signal or if you want to be able to reconstruct that signal exactly from frequency data.

But if all you are interested in is the magnitude of the frequency, that is, how much of a particular frequency is in your signal, regardless of phase, then you only need to look at the absolute value. So for many signal processing applications, like answering our 60 hertz question, you don't need a real and imaginary component to determine it. You just need the magnitude. So we take the absolute value to get that magnitude. Alright, for the next question, I want to talk about what the difference is between a one-sided and a two-sided FFT. The answer involves

understanding

that the FFT returns both positive and negative frequencies, that is, two sides.

And if you take the FFT starting at k equals 0 and go up to k equals n minus 1, then the positive frequencies are on the left and the negative frequencies are on the right. And the Nyquist frequency is the boundary between the two. This is based on the Nyquist sampling theorem which states that we can only know signal information up to half the sampling frequency. Now, sometimes it is useful to change the FFT so that the negative signals are on the left and the positive signals are on the right. But it's not necessary as long as you understand which are negative and which are positive.

Alright, back to the question. If you look at the entire range of the FFT, then this is a two-sided FFT, whereas, with a one-sided FFT, you only look at the positive frequencies, just one side of the spectrum. And why would we do this? I mean, why would we throw out half the information? Well, first of all, if x sub n is a real signal, i.e. not complex, and we take the absolute value of the FFT of x sub n, then the resulting spectrum is reflected between the positive and negative frequencies. And we can see why this is the case here.

Let me hide the time signal so we can see the correlative signal. We know that, when k is equal to 0, this corresponds to frequency 0. It is neither positive nor negative. But, for k equals 1, the frequency has a period equivalent to the duration of the temporal signal. And going to k is equal to 2, the frequency has a period 1/2 the duration of the time signal. And this continues as k increases. We obtain 1/3 and 1/4 and so on, until we reach the Nyquist frequency. Now I know this is going to be a little difficult to watch. But if we increase k beyond this point, the frequency starts to decrease.

And not only that, but the frequency is also negative. And we can see that a little bit easier here. Note that between k equals 9, which is the lowest negative frequency, and k equals 1, which is the lowest positive frequency, the correlated signal is exactly the same frequency. It's just negative. Now you'll notice that the actual component doesn't change the sine here. And that's because the cosine is an even function. So the cosine of a positive number is the same as the cosine of a negative number. But the imaginary component changes the sine since the sine is an odd function.

This means that between k equals 1 and k equals 9, the magnitude of the FFT remains the same. And the same is true for k equals 2 and 8 and 3 and 7 and so on until we reach the Nyquist frequency. Now, k is equal to 0 and k is equal to whatever Nyquist is, both are unique values ​​that are not duplicated anywhere else. That's why we want to keep both frequencies in a one-sided FFT, along with the rest of the positive frequencies. So when there are an even number of time samples, like we have here with n equal to 10, then for a one-sided FFT, we need to keep n divided by 2 plus 1 points in our FFT.

And that plus 1 represents the Nyquist frequency. However, if we have an odd number of samples, say, n equals 11, then we don't actually get the Nyquist frequency in the FFT because it sort of jumps, in this case, between k equals 5 and k is equals 6. And therefore, with an odd number, we take n divided by 2, which leaves us with 1/2 left over since it is odd. And so we rounded that up. So for 11 samples, the one-sided FFT would have 6 points. Very well, we continue talking about positive and negative frequencies. But I have not explained how the variable k corresponds to the exact frequency of the spectrum.

We know that k equal to 0 corresponds to 0 hertz. And I mentioned earlier that k equal to 1 corresponds to a frequency with a period equal to the duration of the temporal signal and that k equal to 2 produces two waves in that same period and so on. Then k to the Nyquist frequency refers to the number of cycles within a period of time equal to the length of the signal in the time domain. So if we want our spectral frequency in hertz or cycles per second, then it's just k cycles divided by the number of seconds in the signal.

Or we can write this as k times the sampling rate divided by the number of samples. We can then plot the FFT versus frequency using this conversion. Now, you may also hear the term container width. And this is the width of each frequency interval in the FFT. So if we go back to the spectrum that we calculated here, the width of the bin is just the frequency width between each of these samples. So what distance is there between thesample zero and sample one? And then from sample one to sample two and so on. And we already know this answer.

We simply set k equal to 1 in this equation. And we get the width between two samples. For example, I have this blue time signal that has a dominant frequency of 60 hertz. And I have 0.1 seconds of data at 200 hertz. The FFT is on the right. And we can see that we have a bin width of 10 hertz and there is a small peak at 60 hertz. Now, if we want a narrower bin width, it's as easy as using a longer data period or simply using more samples. Notice, as I increase the length of the sign, the width of the container becomes smaller.

And we can also see that the 60 hertz peak is really starting to become obvious. And this is because, with more data, we also increase the frequency resolution. We are receiving more signal per frequency range. However, we can also adjust the bandwidth without having to add additional data. And we can do this by simply padding the signal with zeros. For example, if we start with exactly the same 0.1 seconds of data and add 0 to the end of the signal, then we can see that once again the bandwidth is reduced. However, while this improves display, it does not increase frequency resolution.

Basically, we just interpolate the frequency signal and top it off with denser sampling. Adding 0 does not change the overall frequency resolution since we do not add any additional signal. And we can see that here with our 60 hertz peak. It's more like a small lump. Alright, I hope this whole container width thing makes sense. And I know we've talked about many different aspects of the FFT. So I think, to help it all sink in a little and maybe make approaching the FFT a little less daunting, let's look at how to write the code for a one-sided FFT in a live MATLAB script.

Alright, to start, I have this signal in the time domain. It's just a pure 3 hertz sine wave. And there are 40 samples sampled at 40 hertz. So I have 1 second of data. So now let's construct the one-sided FFT. And first of all, let's take the FFT of the signal and then plot the result. And that could be how someone new could start. It's like, hey, I took the FFT, let me plot it and see what it looks like. But since the result is a complex vector, when you plot it, it shows the real and imaginary components in a single graph.

And it really doesn't seem like a big deal. So instead, we could plot the real and imaginary components on two separate graphs. However, for this example, we only want to look at the magnitude of the response, which we can obtain by taking the absolute value. And look at this, we have our two peaks reflected in the Nyquist frequency just as we expected. Now, to get the one-sided FFT, we simply look at half the spectrum. But of course, since I have an even number of time samples, we need that plus one to be able to capture the Nyquist frequency as well.

So far, so good, except now we want to plot this against frequency in hertz. We then have k ranging from 0 to n over 2 to account for the 21 samples in our one-sided FFT. And we convert it to frequency by multiplying it by the sample frequency divided by the number of samples. And finally, we can plot this. And, as expected, the peak is right at 3 hertz. Now, you may often see the one-sided FFT being scaled to account for information at the negative frequencies that we excluded. But if your goal is simply to understand what frequencies make up your time signal, then scaling is not necessary.

For example, we can see here that there is a 3 hertz component in our signal. And it doesn't matter that the value of 20 to 3 hertz does not refer to anything concrete. Now, scaling the one-sided FFT will be important if you want to understand a quantity, like how much power is in that frequency band. But we'll talk about the energy spectrum in a future video. And we're going to cover the scale there. Alright, hopefully what we covered in this video, each of these steps to get the one-sided FFT, makes sense. And if you want to try this yourself or check out some of the resources where you can learn more, I left links to everything below.

Now, don't forget to subscribe to this channel so you don't miss any future videos. And you can also find all the Tech Talk videos on many different topics very well organized on mathworks.com. And if you liked this video, you might be interested in learning more about the Fourier transform in our video on the Z transform. Alright, thanks for watching. And I'll see you next time.