Cooley-Tukey FFT: You don't have to zeropad to a power of 2?

  • Thread starter Thread starter JonMuchnick
  • Start date Start date
  • Tags Tags
    Fft Power
Click For Summary

Discussion Overview

The discussion centers on the applicability of the Cooley-Tukey FFT algorithm to signal lengths that are not powers of 2, specifically in the context of using the algorithm on a 1920x1080 image without zeropadding to a power of 2.

Discussion Character

  • Exploratory, Technical explanation, Debate/contested

Main Points Raised

  • Some participants note that the Cooley-Tukey FFT can be applied to any composite length, suggesting that zeropadding to a power of 2 may not be necessary.
  • One participant references a Wikipedia page that discusses generalized factors beyond powers of 2, implying that there are alternative approaches to using the FFT.
  • A participant questions whether all examples mentioned are indeed Cooley-Tukey FFTs, indicating uncertainty about the classification of certain algorithms.
  • Another participant seeks additional engagement by asking if others are present in the discussion.

Areas of Agreement / Disagreement

Participants appear to have differing views on the necessity of zeropadding to powers of 2 when using the Cooley-Tukey FFT, and the discussion remains unresolved regarding the implications of using composite lengths.

Contextual Notes

The discussion does not clarify the specific performance implications of using non-power-of-2 lengths or the conditions under which the Cooley-Tukey FFT is most effective.

Who May Find This Useful

Individuals interested in FFT algorithms, signal processing, and computational efficiency in image processing may find this discussion relevant.

JonMuchnick
Messages
7
Reaction score
0
Someone wrote "The algorithm that Cooley and Tukey presented in their classic paper (Math. Comp. 19 (1965), 297-301. http://dx.doi.org/10.1090/S0025-5718-1965-0178586-1) can be applied to any composite length. The performance advantages are greatest for highly composite lengths, of which powers-of-2 are one example, and lengths of powers-of-2 result in other advantages on binary computers, so **it has become a common misconception that the algorithm is only applicable to signals whose length is a power of 2**."

Does that mean that when you **DO use the Cooley-Tukey FFT** You don't have to zeropad to a power of 2?
Take for example an image of 1920x1080. So, if you want to use the Cooley-Tukey FFT, you don't need to zeropad the 1920x1080 image to 2048*2048?
 
Technology news on Phys.org
@Bill Simpson: Are you sure that those are all Cooley-Tukey FFTs?
 
Anyone else here?
 

Similar threads

Mathematica This Week's Finds in Mathematical Physics (Week 226)
  • · Replies 7 ·
Replies
7
Views
4K
Mathematica This Week's Finds in Mathematical Physics (Week 226)
  • · Replies 7 ·
Replies
7
Views
4K