In this post we’ll get to understand how to apply and use Fourier transformations. In further articles we’ll dive into how Fourier actually works, why it’s slow and how to make it faster.
This post served as a learning experience for me. While writing it I learn more about Fourier. Reading this post from top to bottom you’ll be able to see the approach I took to fully understand the inputs and outputs of Fourier.
Okay, understanding the fourier-transform starts with the simple question “what is it”? Well, imagine you’re in need of a scientific way to determine how many ducks there are in a pond. So you send someone out, and he says the following:
I couldn’t look across the pond, but I did measure the height of the waves over time! I measured for ten seconds.
Well, isn’t that useful… But hey, since it’s all you’ve got you decide to plot it on a chart anyways.
You look at the graph you just plotted, and remember "right, Fourier!" You apply some fancy mathematics and figure that there's five ducks in the pond bobbing up and down fast, four ducks bobbing medium-fast ducks, three ducks bobbing at a medium speed, two bobbing medium-slow, and one duck bobbing up and down slowly.
This all suddenly makes sense, doesn't it? Well, it didn't for me, so once I understood how Fourier works I decided to write my own explanation, in the hope of helping someone who reads this understand Fourier, or more specifically DFT (discrete Fourier transformation) better. And so that when I forget how it works I can read this and remember.
So, what does Fourier do?
Fourier is used to determine what frequencies at what strength and what offset make up a signal.
In our example, this means that given the waves we can make up how many ducks are bobbing up and down at what speed.
This does assume that every signal is based on a sinusoid. The following examples are all valid:
- sin(X)
- 2*sin(X)
- 5*sin(X/3)+3*sin(X/2+5)
- cos(2*x)+5
Of course more variations are possible, but this should give a pretty good idea.
Fourier will be able to, based on measurements of these signals, generate the following outputs:
- 1*1hz
- 2*1hz
- 5*0.33hz + 3*0.5hz (with a starting point of -5)
- 1*2hz (with a starting point of -90 degrees, as sin(a) = cos(a-90°)) with a base value of 5
In our example it lead to 5*5hz + 4*4hz + 3*3hz + 2*2hz + 1*1hz, the ducks I described bobbing up and down earlier.
To properly represent this we'll need some so called "complex numbers". This sounds complicated, and it kinda is. These complex numbers have the following format: ai+b. A is called the imaginary part, or "im", and b is called the real part, or "re". i is something weird, as it's the solution to i^2=-1. Now of course this doesn't exist, but mathematicans decided they needed it anyways. After applying a Fourier transformation, we get a list of complex numbers.
In i*2+3 the imaginary part represents the *2, the real part indicates the +3.
We'll use the following script, shamelessly stolen from mathjs, to be able to use complex numbers. I'm not gonna explain this in depth, but we'll need to be able to add two numbers, multiply them and divide them.
Once we've got this we can actually perform Fourier. I'll first dump it here (as stolen from mathjs), and explain it afterwards. It's easier to get once you see what we're working towards.
Now that we've defined Fourier, we'll use it. Note that we only apply Fourier our outcome numbers will be incredibly small, so we'll scale them up a bit while drawing. We're also only using the first one hundred elements, as that describes one full cycle from sin(0) through to sin(2*PI), which is nice and easy to visualize. Fourier will not give us any actual 0s, so we'll just assume that anything below 0.01 is not interesting.
Canvas 2 - Results of Fourier
What we see now is starting to get interesting. We see that our output is symmetric. Let's throw away half the outputs, and zoom in a bit.
Canvas 3 - Fourier normalized
Hmm, we're getting minuses... Let's just ignore those for now, we'll figure out why they're there later.
Okay, so now we see that there's 0.5 ducks that bobbed up and down 10 times, 1 duck that bobbed down 20 times, etc.
0.5 ducks... That doesn't work. Remember how we only took half the calculated points? That's because, for example, sin(45) and sin(135) are equal. Fourier can't know the difference between these two, so it just splits the ducks. It says that there's 0.5 duck at 45 degrees and 0.5 duck at 135 degrees. That means that either we should add the last and first result together (and the second last and second, and so on) or simply multiply our outcomes by two.
If we do that we get the following:
- 1 duck bobbed 10 times in 10 seconds
- 2 ducks bobbed 20 times in 10 seconds
- 3 ducks bobbed 30 times in 10 seconds
- 4 ducks bobbed 40 times in 10 seconds
- 5 ducks bobbed 50 times in 10 seconds
This indeed matches the formula I used to generate the waves in my example, wich was
executed ten times to get 1000 measurements.
Now, let's try some more examples. First, let's look at a simple single sinus.
Tap or click the example scripts to execute them. Some might take quite a while.
What's interesting to note here is that Fourier seems to pick up on some signals that aren't there. Let's see what happens when we take more measurements, 5000 instead of 1000.
Okay, that worked, but took forever. Let's see what happens if we throw in exactly a full cycle of sin (times 100 since I decided to divide by 100 when executing fnWave to get some more measurement points.)
Yup, that works better. So something to note is that, to get a clean Fourier output, you should either have a lot of samples or have exactly one cycle of your signal. The latter is more difficult to achieve but more efficient to perform.
Okay, let's try some composite signals (and stick with PI*2*100, 628 samples).
Flawless. Now let's try one last thing, what if a given signal does not start at zero?
This also works great. What is quite interesting to note is that at the X*2 frequency, we get 1 as opposed to -1. This makes sense, as we shifted it half a cycle, so at 0 it starts going down instead of up. That does lead to the question, what if we shift it a quarter of a cycle?
Hey, nothing is picked up! Let's try that again, but then with more samples.
Nope, still nothing. Remember how complex numbers had two parts, re and im? So far we've only looked at im. Let's see what happens when we look at re instead.
Yes, there we go! So for a sin that starts at 0 we need to use re, for one that starts at -PI/2 (or just PI/2 for that matter) we need to use im. Using this knowledge we could make the educated guess that a sin that starts at PI/4 will have an im of 0.5 and a re of 0.5. let's try that out.
Nope, that did not work. 1.41 where we expected 1. Now 1.41 is equal to roughly 2*0.7, which would make sense. In that case both re and im are 0.7, which is the same as sin(Math.PI/4). Taking this knowledge, combined with im being zero when using sin(x-Math.PI/2) and re being zero when using sin(x), it's starting to look like re and im are the outcomes of y*sin(x) and y*cos(x). If this is true, we should be able to calculate both y and x, getting the direction at x=0 and the strength. Let's give it a shot.
Now we can confirm everything we learned and/or assumed before. Looking at these results, at entry 627 (which represents entry -1 of the next wave) we see rad 0 at strength 0.5, which is exactly the same frequency 1, which has rad 3.14 (180°) and a strength of 0.5. So Fourier gives separate entries for going forward and for going backwards, which means we can indeed just throw away the last half of our results and multiply the strength by two.
Now that we fully understand how to use Fourier we can start looking at how exactly it works and how to make it faster. But we'll leave that for a next post.
As a conclusion:
Fourier is a transformation that can be used to figure out what individual signals make up a signal based on a series of measurements. An example of this is figuring out how many ducks there is in a pond and how fast they bob up and down based on a measured wave height. When inputting a series of measurements into Fourier, you'll get out a list of complex numbers. The imaginary and real part of those complex numbers make up a vector, from which the original signal can be calculated. Fourier gives the cleanest result when using either a big set of samples (which also makes it incredibly slow), or if the samples describe one full cycle of the signal (sin(0) through sin(2*PI)).