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

Question

jon 2013-6-2

1
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/77768-cooley-tukey-fft-you-don-t-have-to-zeropad-to-a-power-of-2

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 个评论
显示 -2更早的评论隐藏 -2更早的评论

请先登录，再进行评论。

请先登录，再回答此问题。

Answer 1

Walter Roberson 2013-6-2

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/77768-cooley-tukey-fft-you-don-t-have-to-zeropad-to-a-power-of-2#answer_87451

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 个评论
显示 4更早的评论隐藏 4更早的评论

jon 2013-6-4

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 2013-6-5