Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. Jun 2, 2013 #1
    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?
  2. jcsd
  3. Jun 3, 2013 #2
  4. Jun 3, 2013 #3
    @Bill Simpson: Are you sure that those are all Cooley-Tukey FFTs?
  5. Jun 4, 2013 #4
    Anyone else here?
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook