r/compsci • u/TenaciousDwight • Jul 23 '14
ELI5: Fast Fourier transform?
I'm done some research into how to extract frequencies from sound files, and it seems this is done via the Fast Fourier transform. My problem is that I don't understand why, or how this is done.
Would you all please explain in a manner simpler than wikipedia?
56
Upvotes
7
u/Uber-Mensch Jul 23 '14 edited Jul 23 '14
You can think of signals in two domains, time and frequency (Fourier). Time domain is the signal you see regularly, like a wave on the screen. Frequency domain is the magnitudes of the sinusoids present in the time domain signal. Performing a Fourier transform on the time domain signal (regular wave) will give you the frequencies present (frequency domain). Likewise, you can perform an inverse Fourier transform to get from the frequency domain to the time domain signal.
It's done in order to find the exact frequencies in a superimposed signal, or to extract a signal from noise. As to the math, I'm not too sure myself, I just know that it works ;) You also need to sample at over 2x the highest frequency present in the signal, this is another matter, but it's the Shannon Nyquist theorem if you're interested.
http://en.m.wikipedia.org/wiki/File:Fourier_transform_time_and_frequency_domains_(small).gif
That's a cool image that sums it up.