Orchid XP v8 wrote:

> 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.

Yep. I pretty much figured that out ... real is the cosine, imaginary is 
the sine components. Add those components together, and you get the 
original time-domain signal. (Well, really average)

> 
> 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.
> 

That much I got, and the order of the data seemed to make sense to me, 
what's racking my brain is the butterfly... That seems to be the "magic" 
piece that makes the whole thing work.

> 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.

Yep, figured that part out, too. Realizing that 1 sample is essentially 
DC, and the real value at index 0 is the DC component made that clear.

> 
>> 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.)
> 

I'm supposing this is where Hamming and Blackmann windows come into play?

> Any further questions?
> 

Heh, as more come to me. I'm tossing together a little C# app to play 
around with the FFT and be able to examine it in both rectangular and 
polar forms.

I knew you'd have something to add to this, since you seem to be quite 
advanced in mathematics.

Post a reply to this message