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

8 views (last 30 days)
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?

Answers (2)

Walter Roberson
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
jon
jon on 4 Jun 2013
I read that it sometimes has speed benefits when you do pad to a power of 2. What are your thoughts on that?
Wikipedia: 'The well-known radix-2 Cooley–Tukey algorithm, for N a power of 2, can compute the same result with only (N/2)log2(N) complex multiplications'
But if we don't take a power of 2: Wouldn't you get a rounding issue (log(1920*1080)/log(2))/2=10.4918530963 complex multiplications for each pixel?
Can you really do 0.4918530963 complex multiplications?
Malcolm Lidierth
Malcolm Lidierth on 5 Jun 2013
Can you really do 0.4918530963 complex multiplications? Perhaps with Wisdom=Norman!
There is lots of info on fftw at http://www.fftw.org

Sign in to comment.


jon
jon on 5 Jun 2013
Please clarify!

Categories

Find more on Fourier Analysis and Filtering in Help Center and File Exchange

Tags

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!