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) _______________________________________________ Linux-audio-dev mailing list [email protected] http://lists.linuxaudio.org/listinfo/linux-audio-dev
