Monday 27 July 2015

What are some of the differences between DFT and FFT that make FFT so fast?


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

readings - Appending 内 to a company name is read ない or うち?

For example, if I say マイクロソフト内のパートナーシップは強いです, is the 内 here read as うち or ない? Answer 「内」 in the form: 「Proper Noun + 内」 is always read 「ない...