Mike Raiford <"m[raiford]!at"@gmail.com> wrote:

> What I can't seem to wrap my head around is FFT.
> But I think I'm getting there. I know it does a bizarre sort at the
> beginning, essentially ordering the data as if the indexes had their
> bits reversed, which allows the next step to happen. The values are then
> recombined, reversing the previous sorting process in such a way as to
> reveal the sine and cosine components of the source signal.

Yikes.  Never had to worry about those details.  I'm usually content enough just
to know that FFTW works!  That said, I'm remembering something about a recursive
factorization for the DFT matrix.  Is that the basis for the FFT, or are the
practical algorithms much more complicated than that?

Anyway, here's someone describing some of the details:
http://ocw.mit.edu/OcwWeb/Mathematics/18-06Spring-2005/VideoLectures/detail/lecture26.htm

And here's a book with some details:
http://books.google.com/books?id=coq49_LRURUC&pg=PA391&lpg=PA391

> And its entirely reversible. (!)

That's really just a property of the Fourier transform itself, isn't it?  At
least to a constant.

> The cool thing is you can take frequency domain set, multiply it by
> another frequency domain set, invert the DFT, and boom, you just
> filtered your data. No messy convolution.

Yes, very convenient.  O(n^2) to O(n log n).  Much less messy, too.

> I'm not 100 % on the theory of noise reduction...

Don't wavelets come into play here?  Fourier transforms aren't local, so doesn't
that amount to a low-pass filter?  I guess you could just break it up like jpeg,
but then you may as well move on to wavelets.  I never really had a reason to
dig into all the details, but I think it might be a worthwhile endeavor.

> Anyway, I'm rambling :)

An enjoyable ramble.

 - Ricky

Post a reply to this message