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

  • Thread starter Thread starter JonMuchnick
  • Start date Start date
  • Tags Tags
    Fft Power
AI Thread Summary
The discussion centers on the Cooley-Tukey FFT algorithm, highlighting its applicability to any composite length, not just powers of 2. It emphasizes that while the algorithm performs best with highly composite lengths, particularly powers of 2, it is a misconception that signals must be zero-padded to these lengths for the algorithm to work. The example of processing a 1920x1080 image illustrates that zero-padding to a size like 2048x2048 is not necessary when using the Cooley-Tukey FFT. The conversation also references a Wikipedia page that discusses generalized factors beyond powers of 2, prompting questions about the classification of certain FFTs.
JonMuchnick
Messages
7
Reaction score
0
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?
 
Technology news on Phys.org
@Bill Simpson: Are you sure that those are all Cooley-Tukey FFTs?
 
Anyone else here?
 

Thread 'Learning Assembly and computer architecture for x86'

Dear Peeps I have posted a few questions about programing on this sectio of the PF forum. I want to ask you veterans how you folks learn program in assembly and about computer architecture for the x86 family. In addition to finish learning C, I am also reading the book From bits to Gates to C and Beyond. In the book, it uses the mini LC3 assembly language. I also have books on assembly programming and computer architecture. The few famous ones i have are Computer Organization and...
View full post »

Thread 'Learning data structures and algorithms in different programming languages'

I have a quick questions. I am going through a book on C programming on my own. Afterwards, I plan to go through something call data structures and algorithms on my own also in C. I also need to learn C++, Matlab and for personal interest Haskell. For the two topic of data structures and algorithms, I understand there are standard ones across all programming languages. After learning it through C, what would be the biggest issue when trying to implement the same data...
View full post »

Similar threads

Mathematica This Week's Finds in Mathematical Physics (Week 226)
Replies
7
Views
3K
Mathematica This Week's Finds in Mathematical Physics (Week 226)
Replies
7
Views
4K

Hot Threads

Recent Insights

Back
Top