I'm trying to understand FFTs, here's what I have so far:
In order to find the magnitude of frequencies in a waveform, one must probe for them by multiplying the wave by the frequency they are searching for, in two different phases (sin and cos) and averaging each. The phase is found by its relation to the two, and the code for that is something like this:
//simple pseudocode
var wave = [...]; //an array of floats representing amplitude of wave
var numSamples = wave.length;
var spectrum = [1,2,3,4,5,6...] //all frequencies being tested for.
function getMagnitudesOfSpectrum() {
var magnitudesOut = [];
var phasesOut = [];
for(freq in spectrum) {
var magnitudeSin = 0;
var magnitudeCos = 0;
for(sample in numSamples) {
magnitudeSin += amplitudeSinAt(sample, freq) * wave[sample];
magnitudeCos += amplitudeCosAt(sample, freq) * wave[sample];
}
magnitudesOut[freq] = (magnitudeSin + magnitudeCos)/numSamples;
phasesOut[freq] = //based off magnitudeSin and magnitudeCos
}
return magnitudesOut and phasesOut;
}
In order to do this for very many frequencies very quickly, FFTs use many tricks.
What are some of the tricks used to make FFTs so much faster than DFT?
P.S. I have tried looking at completed FFT algorithms on the web, but all the tricks tend to be condensed into one beautiful piece of code without much explanation. What I need first, before I can understand the entire thing, is some introduction to each of these efficient changes as concepts.
Thank you.
No comments:
Post a Comment