Talk:Cooley-Tukey FFT algorithm

From Wikipedia, the free encyclopedia

[edit] Weighting

Weighting is not trivial: beautiest way to do this is by dividing each f by sqrt(2) in each step. Inverse transform is done by simply replacing the negative exponents with a positive one. --152.66.224.133 14:52, 20 May 2004 (UTC)lorro, 2004.05.20.

Weighting is generally trivial, at least in the common case of floating-point FFTs, since it's just an overall scaling. The √2 trick only works for radix-2 algorithms—moreover, it's not as efficient as doing the scaling all at once. However, the most efficient thing is for the user to simply absorb the scale factor into some other computation, which can typically be done at little or no cost. For example, FFTs are commonly used for convolution with a fixed kernel, so you can just abosrb the 1/n normalization into the kernel when you construct it.

I suspect that you're worrying about the fixed-point case, where indeed the scaling is non-trivial and has to be done at each intermediate stage, and the optimal scaling depends upon the data. However, this would be better discussed in the main fast Fourier transform article since the same principles apply to all FFTs, or (if someone is inspired to write a detailed discussion) on a fixed-point FFT algorithms sub-page linked to from that article. The algorithm-specific sub-pages like this one are about the abstract factorization of the Fourier matrix and the computational ordering; arithmetic issues are dealt with on the main FFT page. —Steven G. Johnson 17:31, May 20, 2004 (UTC)

I've edited the main fast Fourier transform to mention fixed-point scaling issues, in the Accuracy and approximations section. —Steven G. Johnson 19:37, May 20, 2004 (UTC)

[edit] Simpler way?

There's not.. um.. a more simple way of describing this, is there? For "laymen"? I understand Fourier transforms fine, have used FFTs plenty of times and used them to speed up computations of things like the Hilbert transform, but I really don't understand this article. Basically it sounds to me like they have created this formula by which you take, for instance, a 64-point DFT and break it down into 2 32-point DFTs, then you break those down into 4 16-point DFTs, and so on, until you are left with just 32 two-point DFTs to calculate? And then you calculate them and work your way back up, reassembling the results? Are there any graphical analogies? What is this "butterfly" they mention? - Omegatron 17:49, July 10, 2005 (UTC)

Butterfly_(FFT_algorithm) - look there. Fresheneesz 00:39, 24 April 2006 (UTC)

This article needs rewriting. It needs to be clear what is derivation and what is the final product. I'd make some butterfly diagrams myself, but I don't understand how to apply them to the messy math thats given. Fresheneesz 01:24, 24 April 2006 (UTC)

The derivation here is totally standard, and is not much different from what you would find in any textbook on the subject. The final product is simply to show how a DFT can be broken into smaller DFTs based on its factors. This is pointed out numerous times in the article. Can you be more specific and constructive? —Steven G. Johnson 05:37, 2 October 2006 (UTC)

It seems that it might actually be *much* clearer if the sigma notation were turned into (1st, ellipses, last) format. I'll do this in a few days myself if there are no objections. 68.163.184.132 03:39, 2 October 2006 (UTC)

Please don't. The Σ notation is not only completely standard, consistent with numerous other articles (discrete Fourier transform etc.), more readable for complicated sums, and much more compact than ellipses, it is also the only reasonable way to show nested summations (which are required to describe the general Cooley-Tukey algorithm). If a reader doesn't know what Σ means then they have no hope of understanding the other math; such a reader should stick with the English description in the introduction. —Steven G. Johnson 05:27, 2 October 2006 (UTC)

[edit] picture

I think an 8 point picture of the butterfly network would help the reader. Does anyone have one that is fair use? Jdufresne 01:01, 5 March 2006 (UTC)

Why don't we make one? I think the butterfly diagrams would help alot. Fresheneesz 00:39, 24 April 2006 (UTC)