Understanding the Discrete Fourier Transform and the FFT
Summary
TLDRThis MATLAB Tech Talk video, hosted by Brian, delves into the Discrete Fourier Transform (DFT) and its efficient computation through the Fast Fourier Transform (FFT) algorithm. It explains why DFT is essential for analyzing signals in the frequency domain, which isn't always apparent in the time domain. The video clarifies concepts like the amplitude spectrum, power spectrum, and power spectral density, while demonstrating the DFT's process with a graphical MATLAB app. It also addresses practical questions about interpreting FFT results, the difference between one-sided and two-sided FFTs, and the significance of bin width and frequency resolution in signal processing.
Takeaways
- π¨ The script discusses the process of analyzing hardware vibrations using a shaker table and accelerometers, emphasizing the importance of understanding frequency components of the signal.
- π The Discrete Fourier Transform (DFT) is introduced as a method to transform signals from the time or spatial domain into the frequency domain, making it easier to identify signal features.
- π The Fast Fourier Transform (FFT) algorithm is highlighted as an efficient way to compute the DFT, taking advantage of signal symmetries to reduce computational work.
- π The script explains the concept of frequency spectrum, amplitude spectrum, and power spectrum, which provide insights into the signal that time-domain analysis alone cannot.
- π The DFT equation is broken down to illustrate how the transformation works, involving multiplication of the time signal with sine and cosine signals of different frequencies.
- π A MATLAB app demonstration is used to visually explain the DFT process, showing how it correlates the time signal with different frequencies to produce a frequency domain signal.
- π The script clarifies that the FFT returns both positive and negative frequencies, with the Nyquist frequency marking the boundary between them.
- π The difference between one-sided and two-sided FFT is explained, with one-sided FFT focusing only on the positive frequencies for analysis.
- π The importance of understanding the relationship between the variable k in the FFT and the actual frequency spectrum is discussed, including the concept of bin width.
- π§ The script provides practical advice on how to perform a one-sided FFT in MATLAB, including scaling considerations and the impact on frequency resolution.
- π¬ The video concludes with a walkthrough of writing MATLAB code for a one-sided FFT, demonstrating the process from signal acquisition to frequency domain analysis.
Q & A
What is the purpose of using a shaker table in hardware testing?
-A shaker table is used to apply random vibrations to hardware in order to simulate real-world conditions and measure its response, ensuring the hardware can withstand such vibrations.
How does an accelerometer help in vibration analysis?
-Accelerometers are used to measure the response of the hardware to the vibrations applied by the shaker table, capturing the motion data which is then analyzed to understand the hardware's performance under vibration.
What is the main reason for transforming a signal from the time domain to the frequency domain?
-The transformation helps in identifying the frequency components of a signal, which may not be evident in the time domain, and provides insights into the signal's characteristics that are not apparent in the time or spatial domains.
What is the Discrete Fourier Transform (DFT) and why is it used?
-The DFT is a mathematical technique that transforms a signal from the time or spatial domain into the frequency domain, allowing for the analysis of the signal's frequency components.
How does the Fast Fourier Transform (FFT) algorithm improve upon the DFT?
-The FFT algorithm is an efficient way to compute the DFT by taking advantage of the symmetries in the matrix multiplication involved in the DFT, reducing the number of calculations required.
Why is the absolute value of the FFT often considered in signal processing applications?
-The absolute value of the FFT provides the magnitude of the frequency components, which indicates the presence and strength of specific frequencies in the signal without the need to consider their phase.
What is the difference between a one-sided and two-sided FFT?
-A two-sided FFT shows both positive and negative frequencies, while a one-sided FFT focuses only on the positive frequencies, which is often sufficient when dealing with real signals due to the mirrored nature of the spectrum.
How does the Nyquist frequency relate to the FFT?
-The Nyquist frequency is the highest frequency that can be accurately represented in the FFT and is based on the Nyquist sampling theorem, which states that the sampling rate must be at least twice the highest frequency of the signal.
What is meant by 'bin width' in the context of an FFT?
-Bin width refers to the frequency resolution of the FFT, which is the distance in frequency between adjacent points in the spectrum.
How does padding a signal with zeros affect the FFT?
-Padding a signal with zeros can improve the visualization of the FFT by reducing the bin width, but it does not increase the frequency resolution since no additional signal information is added.
Can you provide an example of how to calculate the one-sided FFT of a signal in MATLAB?
-Yes, to calculate a one-sided FFT in MATLAB, you would first take the FFT of the signal, then take the absolute value to get the magnitude, and finally, select only the first half of the spectrum, including the Nyquist frequency if present, and plot it against the corresponding frequencies.
Outlines
π Introduction to DFT and FFT
The script begins with an introduction to the Discrete Fourier Transform (DFT) and the Fast Fourier Transform (FFT), explaining their importance in analyzing hardware vibrations. It discusses how vibrations are measured and transformed from the time domain to the frequency domain using DFT, which is efficiently computed by the FFT algorithm. The video aims to answer common questions about DFT and FFT, providing insights into signal analysis that are not evident in the time domain alone. The example of distinguishing a 60 Hz component in two similar signals is used to illustrate the power of frequency domain analysis.
π Understanding the DFT Equation and its Visualization
This paragraph delves into the mathematical foundation of the DFT, explaining the transformation of a time-domain signal into the frequency domain. The script uses the DFT equation to demonstrate how the time signal is multiplied by a complex exponential, representing a sine and cosine of a specific frequency. A MATLAB app is introduced to visually show how the DFT correlates the time signal with different frequencies, highlighting the process of calculating the correlation for various frequencies and the concept of rotation through matrix multiplication.
π Exploring FFT Efficiency and Practical Signal Analysis
The script explains the computational efficiency of the FFT, which takes advantage of symmetries in the DFT matrix multiplication to reduce calculation time. It emphasizes the practical use of FFT in signal processing, discussing the interpretation of the FFT's real and imaginary components and the significance of the absolute value for determining the magnitude of frequencies in a signal. The difference between one-sided and two-sided FFT is introduced, explaining the reflection of the spectrum and the implications of the Nyquist theorem on frequency analysis.
π Bin Width, Frequency Resolution, and One-Sided FFT Coding Example
The final paragraph discusses the concept of bin width in the FFT and how it relates to frequency resolution. It explains that a longer data period or more samples can lead to a narrower bin width and improved frequency resolution. The script also addresses the misconception that padding a signal with zeros increases resolution, clarifying that it only improves visualization without adding new signal information. The paragraph concludes with a MATLAB live script example that demonstrates how to calculate and plot a one-sided FFT, emphasizing the process of converting the FFT output to a frequency spectrum and the importance of scaling for certain applications.
Mindmap
Keywords
π‘Vibration Analysis
π‘Shaker Table
π‘Accelerometers
π‘Digital Computer
π‘Discrete Fourier Transform (DFT)
π‘Fast Fourier Transform (FFT)
π‘Frequency Domain
π‘Amplitude Spectrum
π‘Power Spectral Density
π‘Nyquist Frequency
π‘One-Sided and Two-Sided FFT
π‘Bin Width
π‘Signal Length
Highlights
Introduction to vibration analysis on hardware using a shaker table and accelerometers to measure responses.
Explanation of the importance of analyzing the frequency spectrum of signals for insights beyond the time domain.
Introduction to the Discrete Fourier Transform (DFT) and its role in transforming signals from the time domain to the frequency domain.
Efficiency of the Fast Fourier Transform (FFT) algorithm in computing the DFT by reducing computational redundancy.
The rationale behind using DFT to reveal signal features not evident in the time or spatial domains.
Demonstration of how DFT can differentiate between signals with and without a significant 60 Hz component.
The mathematical formulation of DFT and its interpretation involving complex exponentials.
Graphical demonstration of the DFT process using a MATLAB app to show the correlation between time signals and different frequencies.
Understanding the DFT as a matrix multiplication that represents a rotation from time to frequency domain.
Practical use of the absolute value of the FFT for analyzing the magnitude of frequencies without considering phase.
Difference between one-sided and two-sided FFT, and the implications for analyzing positive and negative frequencies.
The concept of bin width in FFT and its relation to frequency resolution and signal sampling.
Technique of padding signals with zeros to adjust bandwidth and improve frequency signal visualization without increasing resolution.
Writing code for a one-sided FFT in MATLAB, including plotting the magnitude of the response against frequency.
Explanation of scaling the one-sided FFT for applications requiring understanding of power in frequency bands.
Resources and links provided for further learning about FFT and related signal processing topics.
Encouragement to subscribe for more Tech Talk videos and mention of the organization of videos at mathworks.com.
Transcripts
Imagine you're running a vibration
analysis on some piece of hardware
that you're developing.
And the hardware is on a shaker table
which applies random vibrations to the hardware.
And you measure how the hardware responds with accelerometers.
This measurement is captured with a digital computer.
And, therefore, what you get out is a finite amount
of data that is sampled at a regular interval.
Now, in the case of vibrations, as well as
many other applications, it's often
helpful to look at the spectrum of the signal,
that is, to separate the time domain
signal into the frequency components that make it up.
And, once we have frequency information,
now we might choose to look at the amplitude spectrum
or the power spectrum or the power spectral density.
And each of these provide some insight into the signal
that we can't get from the time domain alone.
Now, with finite discrete data, like we have here,
the first step to getting to any one of these representations
is the Discrete Fourier Transform, or DFT.
And the most efficient way to compute the DFT
is using a Fast Fourier Transform algorithm, or FFT.
And so, for this video, what I want to do
is answer a few common questions that you might have
regarding the DFT and the FFT.
I think it's going to be pretty interesting and useful.
So I hope you stick around for it.
I'm Brian and welcome to a MATLAB Tech Talk.
All right, so, to begin our first question,
we want to ask is, why are we using
the discrete Fourier transform?
Well, the DFT transforms a signal from the time domain
or a spatial domain like distance
into the frequency domain.
And one of the main reasons for making this transformation
is because the features of a signal that we're interested in
are not always obvious in the time or spatial domains.
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 terribly obvious, right?
They both look pretty similar.
But if we transform them into the frequency domain,
it's much easier to answer.
I mean, it's clearly this first signal
because there's this large 60hz peak.
So we can use the frequency domain
to understand the frequency makeup of a signal.
To understand how the DFT is doing this transformation,
we should look at the equation.
And I know that there's lots of symbols here,
but it's actually pretty straightforward.
This blue variable x sub n is the discrete time domain signal
that we're starting with.
And we're going to transform it into the frequency domain
signal x sub k.
And, to do this, we multiply the time signal
with this yellow part, which is e 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
times the sine of the exponent.
So, essentially, what the DFT is doing
is multiplying the time signal by a sine and cosine signal
of a particular frequency given by this variable k.
And then it's summing the result.
And we do this summation for different values of k,
or for different frequencies.
All right, now, I think we can get a little intuition into how
this equation works with just a simple graphical demonstration.
All right, I made a little MATLAB app here
to show you how the DFT works.
Here the time signal x sub n is just a pure sine
wave with 10 samples.
So, per the definition of the DFT,
we multiply this signal with e raised
to an imaginary exponent, which I'm calling this whole thing
the correlating signal.
And, hopefully, the name will make sense shortly.
Now, if we set k equals 0, then our correlating signal
is just e to the 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 sum the result, we get a value that is really low.
And, mathematically, this is because, when
we multiply the time signal by 1,
we get the exact same signal back.
And so, essentially, we're really just summing
the values in our time signal.
And there are equal positive values--
that's these four right here--
as there are negative values, which are these four.
And so they cancel each other out to near 0.
And the way that we can think about this really low value
is that our time domain signal is not correlated very well
with a signal with 0.
Frequency.
Now let's move on to a new set of frequencies, say,
k equals 1.
Our correlating signal now consists
of a sine and cosine wave with a period equal to the length
of the time signal.
And if we multiply these with x sub n and then sum the result,
the value is larger.
And we can visually see that the correlating
signal is near the same frequency as our time signal.
And so, at least for the imaginary component,
which is perfectly out of phase with our time signal,
the product of the 2 is always negative.
And, therefore, the summation is also going to be negative.
So there's 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's going through n different frequencies
where k goes from 0 to n minus 1 and calculates the correlation
between it and the time signal.
That's pretty cool, that we can think of the DFT
as producing the correlation between our time signal
and a bunch of different frequencies.
But there's another cool way that we
can think about the DFT.
And that is as a rotation with matrix multiplication.
If we go back to the equation, we
can rewrite it as a 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 corresponds to the sines and cosines
associated with k equals 0.
And the second column is k equal 1,
and so on, all the way up to k equals n minus 1.
And now, when you perform 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, all the way up.
So, in this form, it's a bit easier
to see that the DFT is performing
this rotation between one set of basis functions, this x sub n,
into another, this capital X of k.
And this n by n matrix is what is
achieving that rotation from time into complex exponentials.
And, actually, this is a good segue into the fast Fourier
transform.
This matrix multiplication is easy to do
if the length of the signal is relatively short.
If there's only 10 samples, then this is a 10 by 10 matrix.
But if you're working with a signal that
has thousands or tens of thousands of samples,
then performing this matrix multiplication
could become computationally costly.
But it turns out that, due to various symmetries
in this multiplication, a lot of the operations are duplicated.
And so you can perform a calculation once
and then populate that answer in several locations.
And FFT algorithms take advantage
of duplicate operations to reduce the number
of overall calculations.
So they produce the exact same result as the DFT,
just in a more efficient way.
And, for a good explanation of the FFT algorithm
and how these computational efficiencies actually
made the DFT a viable option for science and engineering,
check out Veritasium's excellent video on the topic.
Link is in the description below.
All right, now that we know that the ft is just an efficient way
to calculate the DFT, I want to use the last bit of this video
to answer a few 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, recall that the ft produces a complex result.
And the way that we can interpret this
is that the real part of the FFT is
how well the time signal correlates to a cosine wave
of a given frequency.
And the imaginary part is how well
it correlates to a sine wave of the same frequency.
And knowing both of these 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're interested in is the magnitude
of the frequency, that is, how much of a particular frequency
there is in your signal, regardless of phase,
then you just have 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 that.
You just need the magnitude.
So we take the absolute value to get that magnitude.
All right, so, for the next question,
I want to talk about what the difference is
between a one-sided and two-sided FFT.
The answer involves understanding
that the FFT returns both the positive
and the negative frequencies, so 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 1/2 of the sampling rate.
Now, sometimes it's helpful to shift the FFT such
that the negative signals are on the left
and the positive are on the right.
But it's not necessary as long as you
understand which are negative and which are positive.
All right, so back to the question.
If you're looking at the entire range of the FFT,
then this is a two-sided FFT whereas, with a one-sided FFT,
you're just looking at the positive frequencies, just one
side of the spectrum.
And why would we do this?
I mean, why would we throw away half of the information?
Well, first off, if x sub n is a real signal, that
is, it's not complex, and we take the absolute value
of the FFT of x sub n, then the resulting spectrum
is mirrored between the positive and the negative frequencies.
And we can see why this is the case here.
Let me hide the time signal so that we can just
see the correlating signal.
We know that, when k equals 0, this
corresponds to 0 frequency.
It's neither positive nor negative.
But, for k equals 1, the frequency
has a period of the length of the time signal.
And going to k equals 2, the frequency
has a period 1/2 of the length of the time signal.
And this continues as k increases.
We get 1/3 and 1/4 and so on, all the way up to the Nyquist
frequency.
Now, I know that this is going to be a little hard to see.
But if we increase k beyond this point,
the frequency starts to decrease.
And not just that, but the frequency is also negative.
And we can see that a little bit easier here.
Notice that between k equals 9, which is the lowest
negative frequency, and k equals 1, which is the lowest
positive frequency, the correlating signal
is the exact same frequency.
It's just negative.
Now, you'll notice that the real component isn't changing sine
here.
And that's because 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 does change sine
since sine is an odd function.
This means that, between k equals 1 and k equals 9,
the magnitude of the FFT stays 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 equals 0 and k equals whatever the Nyquist is
are both unique values that aren't
duplicated anywhere else.
So we want to keep both of those frequencies
in a one-sided FFT, along with the rest
of the positive frequencies.
So, when there's an even number of time samples,
like we have here with n equals 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 accounts for 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 gets jumped over, in this case,
between k equals 5 and k equals 6.
And, therefore, with an odd number,
we take n divided by 2, which leaves us with 1/2
left over since it's odd.
And, therefore, we round that up.
So for 11 samples, the one-sided FFT would have 6 points in it.
All right, we keep talking about positive and negative
frequencies.
But I haven't explained how the variable k corresponds
to the exact spectrum frequency.
We know that k equals 0 corresponds to 0 hertz.
And I mentioned earlier that k equals 1 corresponds
to a frequency with a period equal to the length of the time
signal and that k equals 2 produces two waves
in that same period and so on.
So k up to the Nyquist frequency refers to the number of cycles
within a time period equal to the length of the time domain
signal.
So if we want our spectrum frequency
in hertz or in 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 frequency divided
by the number of samples.
So we can plot the FFT against frequency
using this conversion.
Now, you might also hear the term bin width.
And this is the width of each frequency bin in the FFT.
So if we go back to the spectrum that we calculated here,
bin width is just the width in frequency
between each of these samples.
So how far is it between sample zero and sample one?
And then from sample one to sample two and so on.
And we already know this answer.
We just set k equals 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 60 hertz frequency.
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's this small peak at 60 hertz.
Now, if we want a narrower bin width,
it's as easy as using a longer period of data
or just using more samples.
Watch, as I increase the signal length,
the bin width gets smaller.
And we can also see that the 60 hertz peak really
starts to become obvious.
And this is because, with more data,
we're also increasing the frequency resolution.
We're getting more signal per frequency bin.
However, we can also adjust the bandwidth
without having to add additional data.
And we can do that simply by padding the signal with 0's.
For example, if we start with the exact same 0.1
seconds of data and we add 0's to the end of the signal,
then we can see that once again the bandwidth is reduced.
However, even though this is improving visualization,
it's not increasing frequency resolution.
We're essentially just interpolating
the frequency signal and filling it in with more dense sampling.
Adding 0's doesn't change the overall frequency resolution
since we're not adding any additional signal.
And we can see that here with our 60 hertz peak.
It's more like a little bump.
All right, I hope that all of this bin width stuff
is making sense.
And I know we've talked about a bunch of different aspects
of the FFT.
So I think, to help everything sink in a bit
and maybe make approaching the FFT a little less daunting,
let's walk through writing the code for a one-sided FFT
in a MATLAB live script.
All right, to start, I have this time domain signal.
It's just a pure 3-hertz sine wave.
And there's 40 samples sampled at 40 hertz.
So I've got 1 second of data.
So now let's build up the one-sided FFT.
And, first off, let's just take the FFT of the signal
and then plot the result. And this might
be how someone new might 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 both the real and imaginary components
on a single graph.
And it doesn't really look like much.
So, instead, we could plot the real and imaginary components
on two separate graphs.
However, for this example, we just
want to look at the magnitude of the response, which we can get
by taking the absolute value.
And check this out, we have our two peaks
mirrored about the Nyquist frequency just as we expect.
Now, to get the one-sided FFT, we just
look at half of the spectrum.
But, of course, since I have an even number of time samples,
we need that plus one in there so that we can capture
the Nyquist frequency as well.
So so far, so good, except now we
want to plot this against frequency in hertz.
So we have k going from 0 to n over 2 to account for the 21
samples in our one-sided FFT.
And we convert that 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 might often see that the one-sided FFT is scaled
to account for the information in the negative frequencies
that we excluded.
But if your goal is to just understand
which frequencies make up your time signal,
then the scaling isn't 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 at 3 hertz
doesn't relate to anything specific.
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're going to talk about the power
spectrum in a future video.
And we're going to cover scaling there.
All right, so, 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 out yourself
or check out some of the resources
where you can learn more, I've left links
to everything down below.
Now, don't forget to subscribe to this channel
so that you don't miss any future videos.
And, also, you can find all of the Tech Talk videos
across many different topics nicely organized
at mathworks.com.
And if you liked this video, then you
might be interested to learn about the Fourier
transform in our video on the Z transform.
All right, thanks for watching.
And I'll see you next time.
5.0 / 5 (0 votes)