4 Mar
2014
4 Mar
'14
1:11 a.m.
On Mon, Mar 03, 2014 at 11:44:13PM +0100, "Jeremia Bär" wrote:
After a quick search, I have the impression that
"butterfly transform" is
exactly what turns DFT into FFT. Does anybody know some detail whether that's
actually the case?
What makes the FFT fast is exploiting some mathematical relations that
allow the DFT to be factored into combinations of simpler transforms,
the sizes of which are factors (integer divisors) of the DFT size. If
the DFT size contains any powers of two, then applying that trick leads
to a solution that will contains two-point transforms, which on a flow
diagram look like a butterfly.
What makes the FFT fast is the factoring trick, the butterflies are
just the result of that if the size contains a power of two. For
example a 125-point FFT will not have any butterflies, it will
consist of combinations of 5-point DFTs.
Ciao,
--
FA
A world of exhaustive, reliable metadata would be an utopia.
It's also a pipe-dream, founded on self-delusion, nerd hubris
and hysterically inflated market opportunities. (Cory Doctorow)