The Fast Fourier Transform (FFT) is a fundamental algorithm in digital signal processing, and it comes in various forms. However, the most commonly used FFTs are those with sizes that are powers of 2 (e.g., 256, 512, 1024, etc.). This is due to their widespread availability, ease of implementation, and ability to achieve an efficiency of O(N log N), making them a popular choice among designers.

While powers-of-2 FFTs are convenient and efficient, they may not always be the best choice for every design. In some cases, using a power-of-2 FFT is not always the best choice from a system standpoint, and can lead to complications in other parts of the system in terms of inefficient use of resources and increased complexity.

Fortunately, there are alternative FFT algorithms that can handle any size of FFT, not just powers of 2.

This talk will describe traditional FFT implementation, more exotic FFT algorithms such as:

• Rader FFT
• Winograd FFT
• Prime Factor FFT

It will also cover how to extend Cooley-Tukey factoring to combine powers-of-2 and non-powers-of-2 FFTs, and the Four Step FFT.

Several other algorithms will be touched upon, along with their application, advantages, and disadvantages.