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
SUMMARY

The Cooley-Tukey Fast Fourier Transform (FFT) algorithm can be applied to any composite length, not just powers of 2, as stated in the original paper by Cooley and Tukey (Math. Comp. 19 (1965), 297-301). This misconception arises from the performance advantages seen with powers-of-2 on binary computers. Users can effectively utilize the Cooley-Tukey FFT on signals of lengths such as 1920x1080 without the need for zero-padding to the nearest power of 2, as demonstrated in discussions around generalized factors.

PREREQUISITES
  • Understanding of the Cooley-Tukey FFT algorithm
  • Familiarity with composite lengths in signal processing
  • Basic knowledge of zero-padding techniques
  • Experience with digital signal processing concepts
NEXT STEPS
  • Research the implications of using composite lengths in FFT applications
  • Explore the performance differences between zero-padding and non-zero-padding in FFT
  • Learn about generalized factors in the Cooley-Tukey FFT algorithm
  • Investigate other FFT algorithms and their applicability to various signal lengths
USEFUL FOR

Signal processing engineers, software developers working with FFT implementations, and researchers interested in optimizing performance for non-power-of-2 signal lengths.

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
3K
Mathematica This Week's Finds in Mathematical Physics (Week 226)
  • · Replies 7 ·
Replies
7
Views
4K