▲ 89 points
back
11 comments
This was a reasonable explanation of the Fourier Transform, but sadly, not the Fast Fourier Transform.
To me the easy part has always been understanding that many sines(and cosines) of different frequencies can make up pretty much any periodic signal and that time and frequency domains map back and forth without losing information.
What I still do not fully understand is how exactly FFT algorithm works. Article does not explain it and even this excellent guide: http://www.dspguide.com/ch12/2.htm skips over it, saying it is too complex(pun intended).
My very rough understanding is as follows:
Discrete time signal is taken, (optionally padded with 0s to next power of 2) Real representation is decomposed to complex (numbers not difficulty) representation, as far as I understand this is done via interpolating signals and then further dividing signal in half. Why? Not sure.
Next part is even more mysterious. Magic algorithm here to find frequencies?
Signal is now in frequency domain, just need to show it in as real numbers not complex.
So what is the magic step?
The "magic step" is simply an algebraic observation. I'll use python/scipy notation, since HN has no latex.
Let f = [ f1, f2, ..., fN] be the sequence you want to take the DFT of (has size N = power of 2). Let x = arange(0,N) = [0,1,...,N]. More numpy notation: exp(x) = [exp(0), exp(1), ..., exp(N)], and x * y = [x1 * y1, x2 * y2, ..., xN * yN].
The DFT of f can be written as:
F[k] = sum( exp(2 pi i k x /N) * f) = sum( exp(2 pi i k x /N)[0::2] * f[::2]) + sum( exp(2 pi i k x /N)[1::2] * f[1::2])
So we've now written F[k] as a sum of two DFT's: the DFT over the odd indices and the DFT over the even indices. Each of these DFT's has size N/2.
That's the divide step, now you just conquer by working down recursively.
The magic, as far as I understand it, and it has been many years since I last looked at Fourier transformation is that there is no step. That's why it is called a transform.
The 'mapping' of the frequency domain is simply a function of the original sample rate. So if you know your sample rate you'll know the center frequency of each 'bucket'.
I think you've misunderstood the question; it was "step" in the sense of "operation" or "inference in a proof", not in the sense of "difference between successive values". sireat wants to know why the FFT works, not what the relationship is between sample spacings in the input and the output.
Ah ok, I see. I got thrown off by the use of the words 'magic algorithm here to find frequencies', I thought that implied he was searching for what absolute frequency was tied to which bucket.
Sorry.
Also, the 'imaginary' bit contains the phase information, if you are only interested in the frequency domain you could discard this, but if you ever want to reconstruct the original (or if you want to construct a changed signal, such as after filtering) then you'll need that phase information.
So you'll need to keep the data in its 'complex' form if you want to do anything more than naive analysis.
Nonono, don't discard the imaginary part! If you don't care about phase information, use sqrt(real^2+imag^2) to give you the magnitude of each component.
Uhh...if I remember correctly then the Fourier transform is:
F(w) = <f(x), cos(2 pi w x)> + i <f(x), sin (2 pi w x) >
(where <_, _> is the inner product between functions, x is a time and w is a frequency).
So the imaginary component is not the phase but how much of your function is explained by a sine wave. To get the phase you should take the angle of each complex number (and to get the amplitude you take the magnitude).
Previous discussion: http://news.ycombinator.com/item?id=698929
This is a great introduction to DFTs. I wish there were more write-ups like this. So if you missed it the first time around, check it out.
This is one of my favorite programming tutorials; the FFT is not a particularly easy thing to explain (though from a mathematics POV, it's not a difficult concept).
I saw the article on the front page and thought, "Hey, didn't I submit that already?". Glad to see it again though, and it's worth taking the time to read if you've never dealt with DSP before.
I tought DSP to juniors for eight years and the results were mixed. Most do not understand the use of the (to them) complex mathematical machinery, the typical response was "why do we need this stuff".
I think teaching Fourier series is a better start than the FT, since FT more advanced. The article indeed proceeds like that so the title is a bit of a misnomer. Similar to the article I used the example of recipes, but rather than cooking I used the example of mixing drinks. It's uprising how many cocktails share the same ingredients.
In the code snippet at the bottom, there's this bit:
for (i=2; i<fftFrameSize-2; i+=2) {
for (bitm=2, j=0; bitm<fftFrameSize; bitm<<=1) {
if (bitm & i) j++;
j <<= 1;
}
if (i < j) { /* swap fftBuffer+i with fftBuffer+j */ }
}