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

  • Thread starter JonMuchnick
  • Start date
  • Tags
    Fft Power
In summary, the Cooley-Tukey FFT algorithm, presented in a classic paper by Cooley and Tukey in 1965, can be applied to any composite length. Its performance advantages are greatest for highly composite lengths, such as powers-of-2. However, it is a common misconception that the algorithm is only applicable to signals with lengths that are powers of 2. This means that when using the Cooley-Tukey FFT, there is no need to zeropad to a power of 2, even for images such as 1920x1080. The Wiki page also explains generalized factors, not just 2^n, which can be applied to the Cooley-Tukey FFT algorithm. It is worth noting
  • #1
JonMuchnick
8
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
  • #3
@Bill Simpson: Are you sure that those are all Cooley-Tukey FFTs?
 
  • #4
Anyone else here?
 
  • #5


I can confirm that the Cooley-Tukey FFT algorithm can be applied to any composite length, including signals that are not powers of 2. The misconception that it can only be used for powers of 2 stems from the fact that highly composite lengths, such as powers of 2, result in the greatest performance advantages. However, this does not mean that the algorithm cannot be applied to other lengths. Therefore, it is not necessary to zeropad a signal to a power of 2 in order to use the Cooley-Tukey FFT algorithm. In the example given, an image of 1920x1080 can be processed using the algorithm without the need for zeropadding to 2048x2048.
 

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

1. What is the Cooley-Tukey FFT algorithm?

The Cooley-Tukey FFT (Fast Fourier Transform) algorithm is a fast and efficient method for computing the discrete Fourier transform of a sequence of data points. It was developed by J.W. Cooley and John Tukey in 1965, and is widely used in various fields of science and engineering.

2. Why is it not necessary to zeropad to a power of 2 in the Cooley-Tukey FFT algorithm?

The Cooley-Tukey FFT algorithm uses a divide-and-conquer approach, where the input sequence is recursively divided into smaller sub-sequences until the size of each sub-sequence is reduced to 2. This means that the algorithm can handle any input size that is a power of 2, without the need for zeropadding.

3. Is there a limit to the input size that can be processed using the Cooley-Tukey FFT algorithm?

The only limit to the input size that can be processed by the Cooley-Tukey FFT algorithm is the available memory in the computing system. As mentioned, the algorithm can handle any input size that is a power of 2, so if the input size is not a power of 2, it can be zeropadded to the nearest power of 2 before applying the algorithm.

4. How does the Cooley-Tukey FFT algorithm compare to other FFT algorithms?

The Cooley-Tukey FFT algorithm is one of the most widely used FFT algorithms due to its simplicity and efficiency. It is faster than the direct FFT algorithm, which requires O(N^2) operations, and it is also more efficient than the Bluestein FFT algorithm, which requires O(NlogN) operations. However, there are other specialized FFT algorithms that may be more efficient in certain scenarios.

5. Are there any drawbacks to using the Cooley-Tukey FFT algorithm?

One potential drawback of the Cooley-Tukey FFT algorithm is that it requires the input size to be a power of 2. This means that if the input size is not a power of 2, it may need to be zeropadded, which can affect the accuracy of the results. Additionally, the algorithm is not suitable for non-power-of-2 input sizes, as it cannot handle them efficiently.

Similar threads

Mathematica This Week's Finds in Mathematical Physics (Week 226)
    • MATLAB, Maple, Mathematica, LaTeX
Replies
7
Views
2K
Mathematica This Week's Finds in Mathematical Physics (Week 226)
    • MATLAB, Maple, Mathematica, LaTeX
Replies
7
Views
3K

Hot Threads

Recent Insights

Back
Top