Cooley-Tukey FFT: You don't have to zeropad to a power of 2?
3 views (last 30 days)
Show older comments
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?
0 Comments
Answers (2)
Walter Roberson
on 2 Jun 2013
Correct. Do not pad to a power of 2 when using that algorithm.
Note: The MATLAB fft() and fft2() calls do not require padding to powers of 2.
6 Comments
Malcolm Lidierth
on 5 Jun 2013
Can you really do 0.4918530963 complex multiplications? Perhaps with Wisdom=Norman!
See Also
Categories
Find more on Fourier Analysis and Filtering in Help Center and File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!