|
 |
Mike Raiford wrote:
> I have a very good handle now on what DFT actually does, and it's a
> pretty nifty transform. What I can't seem to wrap my head around is FFT.
> But I think I'm getting there.
Every signal can be represented as a sequence of samples, or as the sum
of some sine (and cosine) components of different frequencies. Two
different ways to describe the same signal. The DFT (and its inverse)
convert one into another. This presumably you have already long figured out.
The FFT works by a divide-and-concor method, rather like quicksort and
mergesort. Take your signal, split it into two signals, transform them
both [by recursively applying the same algorithm], combine the results
back together into a single result.
The whole "swap the bits of the indicies around" trick is an
optimisation to avoid recursively shuffling the samples around. It lets
you do all the shuffling in a single step instead of log N steps, that's
all.
Much like quicksort, the DFT of 1 sample is... that 1 sample, unaltered.
Combining in the frequency domain must undo what was done by splitting
in the frequency domain... There are actually several slightly different
(but essentially equivilent) ways to arrange the FFT.
> 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.
>
> As an example, you can achieve a blur effect on an image by using
> multiply operations on the image's frequency domain data. rather than
> create a convolution matrix to do the same thing.
Multiplication in the frequency domain is convulotion in the time
domain, and vice versa. FFT convolution is mildly more tricky than it
looks at first. (You gotta chop the input into "blocks" to run it
through the FFT, and you need to overlap them after you're done or the
"blur" will stop at the block edges - which is wrong.)
Any further questions?
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
