0
$\begingroup$

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 that to 2048*2048?

$\endgroup$

closed as too localized by Dilip Sarwate, Peter K. Jun 8 '13 at 15:21

This question is unlikely to help any future visitors; it is only relevant to a small geographic area, a specific moment in time, or an extraordinarily narrow situation that is not generally applicable to the worldwide audience of the internet. For help making this question more broadly applicable, visit the help center. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ You're confusing the algorithm with its available implementations. Anyway, you've now asked around 10 very similar questions all on the same subject and received lots of good answers - it's probably time to actually try some of the many suggestions you've received and see what works for you. $\endgroup$ – Paul R Jun 2 '13 at 21:22
  • 1
    $\begingroup$ Different versions of this question have been posted by the OP on math.SE and cs.SE (and possibly other SE sites) in addition to dsp.SE. $\endgroup$ – Dilip Sarwate Jun 3 '13 at 10:52
  • $\begingroup$ The math.SE version appears to have been deleted. I can't see a cs.SE version. @user8005: Please be polite. Your comment was deleted by me for being borderline offensive. $\endgroup$ – Peter K. Jun 4 '13 at 0:28
  • $\begingroup$ @PeterK. Thanks. The math.SE version is still open while the cs.SE version has been closed. $\endgroup$ – Dilip Sarwate Jun 4 '13 at 2:42
  • $\begingroup$ @DilipSarwate: Thanks for the links! Google threw up this link as a search result, so I assumed the math.SE one was closed. $\endgroup$ – Peter K. Jun 4 '13 at 2:51
1
$\begingroup$

Yes. If you can factor length N, Cooley-Tukey will give you an DFT computation that uses less multiplies than an unfactored DFT. A power of 2 factorization requires less lines of text or shorter equations to explain. But any small prime factors allows a straight forward extension to the power-of-2 explanation or proof of the algorithm.

Many newer FFT libraries (iOS Accelerate for one example) allow efficient composite FFT lengths with factors of 2,3,5 and maybe more, thus requiring less padding to get to the next useful composite length.

$\endgroup$
  • $\begingroup$ "Many newer FFT libraries" But do they use the Cooley-Tukey FFT? $\endgroup$ – user8005 Jun 2 '13 at 18:36
  • $\begingroup$ @user8005 I would call anything that uses the so called FFT 'butterfly' a Cooley-Tukey FFT. $\endgroup$ – Mikhail Jun 3 '13 at 0:32
0
$\begingroup$

According to the algorithm you can find the fft of input length which is a power of something (i.e 2^n). Because it becomes easier to combine in the end all the signals to get the final fft output. But however, there are algorithms available like radix2,radix3, radix4, which can be effectively combined to get ffts of different input lengths which are power of something. Zero padding can be way to extend your length to the input length of power of something and then apply the algorithm, but I won't suggest it because it will somehow deteriorate the frequency spectrum to some extent.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.