Fourier Transform Without Fetishizing Math Equations
Implement the Foundation of the Most Useful Algorithm for Spotting Noise in Signal in less than 10 Minutes
TL;DR;
Signals are just intensity at specific point in time. They are composed of many different frequencies.
Magnitude of each frequency that sampled at 1000 Hz could be calculated by multiplying signal to each frequencies from 1 Hz to 1000 Hz.
If the sum at specific frequency multiplication is 0, then the frequency is NOT part of the signal.
You can see the example written in this Jupyter Notebook
Say you just recorded a song and it's the best you've ever sung. However, when you listened to it, you noticed a weird, persistent buzz. You can't let that be a distraction to your pristine voice, so you investigate the recording. The recording might look something like this:
In the simplest terms, it tells how much a speaker should vibrate at a given time. It's composed of different sine and cosine waves at different frequencies. For example, to output A Minor, you would combine note A (55 Hz) + C (65 Hz) + E (82 Hz). Remember that frequency is just how many times/cycles per second. In this case, the sound wave is sampled at 1000 Hz.
In addition to all the notes that make up A minor, I also added in "noise" (orange) at 10 Hz to depict the buzzing sound. Can you spot it just by looking at it?
Maybe, but it's hard to be certain. It gets even more complex as we stack more notes on top of each other. To spot the noise, I need to see how much of each frequency is present.
Spotting Noise In the Lens of Geometry
We first need to multiply A minor from 1 Hz to our sampling frequency, which is 1000 Hz. Multiplication is used because when a frequency is present and in phase (meaning peaks are aligned), it would result in more 'positive curves' sitting above the x-axis than negative curves below.
To correlate how much a specific frequency is present, we could calculate the difference between areas under 'positive curves' and 'negative curves'.
25 Hz (left) is NOT part of our signal. After multiplication, the wave has a relatively the same shape, therefore the difference would be close to 0.
55 Hz (right) is part of our signal. It has a much larger area under 'positive curves' than 'negative curves'.
Here’s what it looks like when we plot the frequency spectrum using the Nyquist method, which means we read the signal at 2 times the original sound wave frequency. In our case, it's at 2000 Hz, but people in the industry often sample it 10 times higher. We also need to look at it at half of the sampling frequency to prevent aliasing, which means high frequency signals could sometimes show up as low frequency signals or vice versa.
The purple section represents areas sitting under the x axis. It still has significance, since we only care about the quantity of the signal, we could just apply absolute value.
After zooming into the highest peaks, this is what we see.
We know A minor consists of (55 Hz, 65 Hz, 82 Hz), in this case, we can assume that 10 Hz could be the buzzing sound.
Cosine Matters
his is a simulated situation. In real life, signals are more complex.Sometimes signals are out of phase. They could shift left and right. To account for that situation, we also have to do the same thing above, but with cosine waves. Here is the python snippet if you’re curious.
It’s Time to Simplify
Analyzing it geometrically offers intuitive understanding, but the resulting signal can be quite noisy due to the approximate area calculation. To obtain a more accurate result, we can switch to crude algebra by simply summing up all the amplitudes after multiplication at each frequency
We removed the area calculation from the previous step, and the result is exceptionally better.
Parting Thoughts
Both sine and cosine multiplication can be simplified using Euler’s formula (e^-2jπƒt). In real-world scenarios, Fourier Transform is almost always done using the Fast Fourier Transform algorithm (FFT). As signals become larger, the time required to run the Fourier Transform grows exponentially. However, with the FFT, the computation time becomes faster as the sample rate increases, because it calculates frequency magnitude by finding common points in the signal. I’ll cover this in the near future.
If you find this post helpful, please consider subscribing.