TL;DR
You may find the Discrete Fourier Transform algorithm in JavaScript Algorithms repository.
Discrete Fourier Transform
Even though Discrete Fourier Transform or DFT is probably not the thing you work with daily it might still be a very interesting algorithm to play with. Not because it is quite complex but because of its interesting meaning.
This algorithm allows you to split the input signal that is spread in time into the number of frequencies of certain length, amplitudes, and phases so that all those frequencies together will form the original signal. So it actually converts the domain of time into the domain of frequencies and backward.
It may sound complicated so let's think about it from another angle.
Smoothie Example
Imagine you have a smoothie. DFT then will allow you to split the smoothie into its ingredients! Imagine that you provide the bottle of smoothie as input for DFT function and it splits it out to three smaller bottles of pure carrot, apple, and orange juices! This is what DFT does - it splits the whole input into its ingredients.
Paints Example
Or imagine that you want to paint the fence and you've mixed several paints up so that it started to be of homogenous color. DFT function then will be able to split your mixed paint into several pure colors that will together form that initial color! Isn't it sound like magic, is it?
The Algorithm
All algorithm beauty and complexity is hidden in the following formula:
You may find the direct and simple implementation of this formula in JavaScript Algorithms repository. This is just a simple and not really efficient (O(n^2)) implementation of the transform. But the purpose of those functions is just to scratch the surface of such a complex, deep, and magic topic as Fourier Transform.
There is a really good article about this topic. I suggest you read it if you're interested in learning more since there are many visual and interactive Fourier Transform examples and explanations.
I hope you found this Fourier thing interesting. Have fun with algorithms!
Top comments (5)
The first image is the best illustration ever!
Yeah! That's true
Hi Oleksii, thanks for this article and for your GitHub repo (javascript-algorithms) in general, i will need this tutorial to code a specific audio feature one day into a JS music app. The FFT is quite hard to apprehend.
Yes, for me personally it is also not an easy topic. Good luck with JS music app!
It was in 1974 when I first saw a similar frequency domain image in an introductory electronics book: it clarified everything!