Non-Powers-of-2 FFTs and Why You Should Use Them

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.

What this presentation is about and why it matters

This talk explains why you dont have to be "handcuffed" to radix-2 (power-of-two) FFT sizes and shows practical, efficient alternatives for arbitrary transform lengths. Many real systems (radio front-ends, legacy sampling rates, matched-bandwidth detectors) use sample rates and desired frequency resolutions that dont line up with 2^n sizes. Forcing a power-of-two FFT often costs sensitivity (worse bin matching), extra resampling, wasted compute, or extra noise. The presenter surveys generalizations of CooleyTukey (mixed-radix and four-step), the prime-factor algorithm, and lower-level methods (Rader, Winograd), and discusses where each method can reduce multipliers, trades adders for multiplies, or eliminate twiddle factors. If you design DSP systems, firmware for FPGAs/ASICs, or high-performance signal-processing software, these alternatives can save resources and improve detection performance.

Who will benefit the most from this presentation

• DSP engineers who design spectral processing chains (detectors, channelizers, spectrometers).
• Hardware implementers writing FFT kernels for FPGAs, ASICs, or DSPs who need resource-efficient layouts.
• Software engineers optimizing FFT-based systems where memory and cache patterns matter.
• Students and researchers who want to understand how number theory and algorithm choices affect practical FFT cost and performance.

What you need to know

Familiarity with the Discrete Fourier Transform (DFT), complex exponentials, and the basics of the CooleyTukey FFT will make the talk much easier to follow. The N-point DFT is usually written as

$X[k]=\sum_{n=0}^{N-1} x[n]\,e^{-j2\pi kn/N}$

Key background topics that will be referenced:

• CooleyTukey factoring: splitting an N-point DFT into smaller DFTs by factoring N. This yields radix-2, radix-4, and mixed-radix FFTs and explains the usual O(N log N) savings.
• Twiddle factors: the multiplicative complex weights introduced when combining sub-DFTs. They cost complex multiplies in implementation.
• Four-step FFT: reorganizes the computation into input sub-FFTs, twiddle multiplications, a matrix transpose (data rearrangement), then output sub-FFTs. This emphasizes memory and transpose costs.
• Prime-factor algorithm (GoodThomas): when N = n1*n2 with n1 and n2 coprime, inputs/outputs can be remapped so twiddle factors disappear; uses number-theoretic index remapping (Chinese Remainder / modular inverses).
• Rader and Winograd methods: low-level techniques for prime or small composite sizes. Rader turns a prime-length DFT into a cyclic convolution; Winograd uses number theory and cyclotomic structures to minimize multipliers (often trading more additions for fewer multiplies).

Also useful: basic modular arithmetic (modular inverses, Chinese remainder theorem), convolution properties of DFTs, and some understanding of hardware costs (why multiplies are more expensive than adds, and why memory transposes are nontrivial in FPGAs/ASICs).

Glossary

• DFT  Discrete Fourier Transform, mapping an N-sample sequence to N frequency bins via complex exponentials.
• FFT  Fast Fourier Transform, any algorithm that reduces the DFTs O(N^2) cost toward O(N log N).
• CooleyTukey  A general factoring approach that splits the DFT by integer factors of N (radix-2, radix-4, mixed-radix).
• Twiddle factors  The complex exponential multipliers introduced when combining sub-DFTs in factorization.
• Mixed-radix  An FFT built from stages of different radices (e.g., radix-2 then radix-4), useful for composite N with varied prime factors.
• Four-step FFT  A reorganization into sub-FFTs, twiddles, a transpose, and final sub-FFTs; highlights memory layout and transpose cost.
• Prime-factor algorithm (PFA)  An FFT method for coprime factorization of N that removes twiddle factors via index remapping.
• Raders algorithm  Converts a prime-length DFT into a cyclic convolution to leverage convolution techniques for efficiency.
• Winograds algorithm  Uses number-theoretic and cyclotomic constructions to minimize multipliers (often more adders) for small transform sizes.
• Bluestein (chirp Z)  A method that computes arbitrary-frequency or arbitrary-length DFTs via chirp convolution; useful when direct factorization is awkward.

When you watch: listen for the practical trade-offs (multiplier vs adder cost, transpose/memory cost, and when remapping removes twiddles), and for the example pipeline (360-point FFT decomposed to 8, 9 and 5point stages) that shows why a non-power-of-two choice can improve detection sensitivity with less total effort than heavy resampling.

This overview is AI-generated from the session transcript. Spot an issue? Let us know.