Discrete Fourier Transform - Simple Step by Step

if you've ever taken calculus before you're probably familiar with the Fourier series which takes any periodic function in time and decomposes it into the sum of a constant and then a series of sines and cosines or sinusoids each of these sinusoids are defined by their frequency and we're summing over each individual frequency of sine and cosine let's look at this white noise signal as an example this signal is represented in what is called the time domain because each point on its plot represents amplitude as a function of time this erratic scribble is what your eardrum actually vibrates at when you're listening to white noise which is pretty unpleasant but despite it being so messy in the time domain if we instead decide to translate it to what is called the frequency domain using a Fourier series we get something really neat a nice straight line the line is really straight because each frequency from say 20 Hertz to 20,000 Hertz is equally represented in a white noise signal this is because a white noise signal is composed of a sum of all the cosines and sines of all different frequencies in practice your signal is not going to look this straight it will probably look more like this for two reasons firstly the white noise signal that you're recording on your sensor is unlikely to be perfectly white and secondly the sensor that you're using is not going to be equally sensitive to all frequencies so we have a periodic signal which we can decompose into sines and cosines of various frequencies the next question then is how do we calculate those coefficients at each particular frequency the answer is to use a Fourier transform now if you're familiar with calculating correlations the Fourier transform is essentially the same thing you're multiplying a function or in our case the signal by an analysing function which in our case are sinusoids wherever the function in the analyzing function are similar they'll multiply and sum to a large coefficient and wherever the function and analyzing function are is similar they'll multiply and sum to a small coefficient now we can represent the sinusoids the analyzing function as a complex exponential but if you're afraid of complex notation don't be discouraged this representation actually makes the integral much easier to use and the result is you get one complex coefficient for frequency if you insist on working in real notation you can however you'll end up having to calculate two different integrals one to correlate the signal with a cosine function and one to correlate the signal with a sine function and the result is you get two real coefficients for frequency now the question is do you would you rather work with one complex coefficient or two real coefficients and most engineers find that working with one complex coefficient and completing just one integral makes things a lot easier and in the coming slides you'll find that it's actually not too difficult to work with the complex notation something else that may be disconcerting to you about this equation is having to run the integral from negative infinity to infinity luckily you don't ever have to do this in practice because you're always collecting data on a signal within a finite time frame in an analog to digital converter also cannot sample continuously so what you end up with is a set of discrete points running from time equals zero to the nth sample that you were able to take in order to conduct the Fourier transform on a discrete set of samples we have to use a discrete Fourier transform which is only slightly different from the continuous Fourier transform which we were describing earlier rather than running an integral from negative infinity to infinity we're instead evaluating a summation from the N equals 0 sample to the M minus 1 sample we're still looking for frequency coefficients but rather than being able to evaluate at any frequency we want we're restricted to a set of frequency bins which is determined by their spire sampling frequency and the number of samples that we're looking at you'll notice also a difference in the exponent and this is similar to the last point that I just made because we can't look at frequency and time fenty continuously we instead look at the Cape frequency bin and the little end sample so K over large n which is a total number of samples corresponds to the frequency F and little n corresponds to T or time let's focus on expanding the summation for the discrete Fourier transform in order to simplify things during our expansion let's call everything after the complex J term B sub n that way when we expand the summation we get a sum of all the samples multiplied by complex Exponential's now how do we deal with this complex exponential we we use an identity through Euler's formula which states that e to the power of j x equals cosine X plus J sine X that way when we use this identity we can expand the entire frequency bin equation into a bunch of sines and cosines once we sum everything up what we end up with is a constant complex number but how do we use this complex number well you can plot this complex number on a complex plane by using the real and the imaginary parts of the number as coordinates once you apply the point you can extract information about this vectors magnitude by using Pythagorean theorem and extract information about its phase or its angle by using an arctangent the magnitude that you can end up calculating corresponds to the amplitude of the sinusoid at that frequency bin and the phase or angle corresponds to how much that sinusoid at that frequency bin is shifted the best way to understand all of this is to try out an example let's look at an incredibly simple sinusoid a 1 Hertz sine wave that amplitude equals 1 because the Fourier transform decomposes a signal into a set of sinusoids we expect to see a 1 amplitude value at the 1 Hertz frequency bin once we've calculated the Fourier transform first first let's set some parameters though the sampling frequency for this example is going to be 8 Hertz and we're going to use 8 samples so the samples are going to look like this across the sign it there are sine wave we can get the values at those particular points and once we have those values we have enough information to begin doing our discrete Fourier transform so let's begin looking at the zeroth frequency bin we can we can see that the K term is equal to 0 and that gets rid of the exponential term or makes it equal to 1 plus the 0th frequency bin is simply the sum of all the samples from X 0 to X 7 which we can see is 0 so we can move on from that term the first frequency bin is going to we can expand out the Exponential's and then use use Euler's formula to change that into a set of sines and cosines and we can perform those operations and add it all together and what we end up with for the first frequency bin is negative 4 J now for the second frequency bin we can do the same thing write out the values inside the Exponential's and then replace those Exponential's with cosines and sines using Euler's formula and then perform those operations and then sum it all together and you'll find that the second frequency bin is equal to 0 now if we calculate the rest of the Fourier coefficients or frequency bins we'll find that only the 1st and the seventh frequency bin have values that aren't equal to 0 we can calculate the magnitudes of those frequency bins and find that they're equal to 4 and then we can plot all the magnitudes of all the frequency bins on a spectrum plot now the frequency resolution of the frequency bins is equal to the sampling frequency divided by the number of samples in our case that's 8 divided by 8 so that equals 1 Hertz so each subsequent frequency bin is 1 Hertz greater than the previous frequency bin we can see that we get a value for the first frequency bin and that makes sense because that corresponds to one Hertz and we have a one Hertz sine wave but why is there one over at the seven Hertz frequency bin well this is what's called a two-sided frequency plot and everything above and it's impossible to measure frequencies above the Nyquist limit which is the sampling frequency divided by two so what you do is you get rid of all the values above the Nyquist limit and simply double the value that you have everything that every value that you have below the Nyquist limit so in our case we get a magnitude of eight well eight still isn't equal to one which is the amplitude that we expect and that's because we use eight samples to calculate our Fourier coefficients so we actually need to a bridge it out over the eight samples to get our amplitude equal to one so divided by eight the number of samples so we have a single sided Fourier coefficient of 0 minus 8 J and we can plot that on a complex plane if we measure the angle off of the positive real axis we get a phase angle of 3 PI over 2 as a result we have an amplitude equal to equal to 1 and the phase angle of 3 PI over 2 how do we know that's correct well the angle of the phase is based off of a cosine wave so if we shift over to 3 PI over 2 on the cosine wave you'll find that actually that's just a sine wave so that's what we end up with a sine wave of amplitude equals 1

Channel: Simon Xu

Views: 655,901

Rating: 4.9375606 out of 5

Keywords: Discrete Fourier Transform, Signal Processing (Field Of Study)

Id: mkGsMWi_j4Q

Length: 10min 34sec (634 seconds)

Published: Mon Aug 03 2015

Reddit Comments

[u/highfrequency]

Would have been nice to have during my signal processing courses.

[u/Handtuch1]

rather looks like he is mixing up different things.

Fourier Series = periodic continous signals = Frequency spectrum with discrete Lines (for example cos(t) -> 1 discrete Signal in Frequency spectrum). Instead of that he shows white noise with a continous frequency spectrum... But his visuals are pretty well made

[u/jschievink]

If you prefer text with animations instead of a video, this one's also pretty good: https://jackschaedler.github.io/circles-sines-signals/dft_introduction.html