2

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 it's 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 shortcuts 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.

Scott Stensland
  • 26,870
  • 12
  • 93
  • 104
Seph Reed
  • 8,797
  • 11
  • 60
  • 125
  • 1
    Symmetry and periodicity of trig functions comes to mind. I think Gil Strang at MIT gives a terrific explanation: https://ocw.mit.edu/courses/mathematics/18-085-computational-science-and-engineering-i-fall-2008/video-lectures/lecture-31-fast-fourier-transform-convolution/ – duffymo Jun 08 '17 at 18:41
  • 2
    An FFT is quicker than a DFT largely because it involves fewer calculations. There's shortcuts available in the maths if the number of samples is 2^n. There are some subtleties; some highly optimised (fewest calculations) FFT algorithms don't play well with CPU caches, so they're slower than other algorithms. Don't worry - if you use a pre-optimised library like FFTW you're getting an FFT algorithm that's optimised for speed, not for the fewest number of calculations. A lot of the speed comes from pre-calculating the FFT's exponentials (they’re constants). – bazza Jun 08 '17 at 19:16
  • I also asked this question at DSP, though the answers are not trivial to translate into code. https://dsp.stackexchange.com/questions/41558/what-are-some-of-the-differences-between-dft-and-fft-that-make-fft-so-fast/41566#41566 – Seph Reed Jun 08 '17 at 21:39
  • 2
    Essentially it's just that DFT = O(n^2), FFT = O(n log n). – Paul R Jun 09 '17 at 07:00

1 Answers1

2

see How to compute Discrete Fourier Transform?

The idea is that N-point DFT discrete sum integration can be split into 2 N/2-point halves where both halves can be expressed as function of N/2-point DFT and some minor tweaking to combine them into final result. That lead to almost half of operations needed per whole dataset. If you apply this recursively you got O(n.log2(n)) instead of O(n^2) with naive approach.

There are 2 well known ways to split the equation to two similar half sums one is called decimation in time and the other decimation in frequency. Booth splits the original sum algebraically (exploiting symmetry of W weights matrix) so just google.

The tweaking usually involves splitting into even and odd entries of dataset and or reordering them using butterfly shuffle which involves bit reversal of index order and can be hardwired really fast ... That is used for HW DFFT implementations... for more info see Wiki Butterfly diagram

Spektre
  • 49,595
  • 11
  • 110
  • 380
  • @PaulR wasn't here for a while I think I finally spotted the ill-worded part (took me a while my English is not as good as it should be and some parts got lost in (re)translation but not all was caused by translation though) Thx for spotting it ... – Spektre Jun 12 '17 at 05:49
  • Thanks for improving the question - down-vote removed. – Paul R Jun 12 '17 at 05:51
  • 1
    @PaulR most likely scenario was I was thinking one thing and writing other. It happens to me time to time but usually in spoken language where I got direct feedback from people I spoke to. This is the first time I spot it in written language. With combination with memory sight I did read back what I was thinking instead of what I was writing. After few days I forgot and finally read the real deal ... :) cause of that I got a lot of typos overlooked and edit a lot afterwards... – Spektre Jun 12 '17 at 05:57