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

Well, you *could* take the time-domain signal and cut it into two 
halves. But that's not very easy to undo in the frequency domain. So 
what they usually do is take all the odd samples and all the even samples.

Taking all the even samples is just halving the sampling rate. [Assuming 
0-based indexing!] Halving the time domain means doubling the frequency 
domain. (Think about it: You take a sound, cut out half the samples, 
that's like doubling the playback speed. All the pitches are twice as high!)

Taking all the odd samples is like shifting one sample to the side and 
then halving the sampling rate as per above. In the frequency domain, 
such a time shift is a multiplication by a sinewave.

So, to undo all this, double both signals, multiply one by a sinewave, 
then add them back together. Hence, the butterfly.

>> Combining in the frequency domain must undo what was done 
>> by splitting in the frequency domain...

Grr... "Combining in the *frequency domain* must ondo what was done by 
splitting in the *time domain*." Get it right, boy! >_<

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

No. Those come into play if you're trying to desing a digital filter. 
(E.g., a "perfect" lowpass filter has an infinite frequency response, 
but we can't do that. If you just chop the ends off it screws up the 
frequency response. Using (say) a Hamming window reduces the effect - 
but doesn't eliminate it.)

Recall that the convolution of a signal by some kernel is *longer* than 
the original signal. This is the effect you have to repeat when doing 
FFT convolution. (The details escape me at this exact moment... Suffice 
it to say that your inverse-FFT results have to be overlapped to get a 
smooth result.)

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

Meh. I wanted to build a digital filter, so I read a rather excellent 
book on the subject. ;-)

Wanna see the Z-transform?

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message