The Fast Fourier Transform (FFT) is an algorithm that computes the Discrete Fourier Transform (DFT) of a sequence in O(N log N) time rather than the O(N²) time of a naive DFT, by recursively decomposing the transform into smaller sub-transforms. It converts a finite time-domain sequence into a discrete set of frequency-domain samples, revealing the magnitude and phase of each frequency component present in the signal.
In practice
In embedded and FPGA-based DSP, the FFT is used for spectrum analysis, audio processing, motor current signature analysis, radar/sonar signal processing, and OFDM modulation/demodulation (Wi-Fi, LTE, DAB). On MCUs, software FFT libraries like CMSIS-DSP provide optimized fixed- and floating-point implementations; parts with hardware FPUs (such as some ARM Cortex-M4 variants and Cortex-M7 parts like the STM32F4/H7 series) benefit from accelerated floating-point paths, but fixed-point implementations are also widely used on cores without FPUs. On FPGAs, dedicated FFT IP cores (Xilinx FFT IP, Intel/Altera FFT MegaCore) pipeline the butterfly operations in hardware and can process hundreds of millions of samples per second, typically at much lower latency than a software implementation for the same transform size and throughput requirement, though the comparison depends on transform size, clock rate, data width, and CPU capability.
A critical practical concern is numerical precision. Fixed-point arithmetic is common in FPGA and MCU FFT implementations, though floating-point and mixed-precision designs are also used in both domains. Fixed-point implementations introduce rounding and truncation errors that accumulate across stages. A radix-2 FFT on N points has log2(N) butterfly stages; each stage can introduce quantization noise, so a 1024-point FFT (10 stages) demands careful word-length planning. The blog post "Dealing With Fixed Point Fractions" is directly relevant here: scaling strategies such as block floating point or per-stage bit-growth must be applied deliberately to avoid overflow or excessive noise floor degradation.
Windowing is nearly always required before applying the FFT to a real-world signal. Applying a rectangular window (i.e., no windowing) to any signal that is not perfectly periodic within the analysis frame causes spectral leakage, where energy from one bin spreads into adjacent bins; a common practical trigger is capturing a non-integer number of cycles. Hann, Hamming, Blackman, and Kaiser windows trade frequency resolution for reduced leakage and are chosen based on the application's tolerance for each.
On FPGAs specifically, the FFT size N is typically constrained to a power of two when using radix-2 Cooley-Tukey IP cores, which are the most common off-the-shelf hardware implementations. Mixed-radix FFTs (supporting sizes like N = 3×2^k or arbitrary N via Bluestein's algorithm) exist and some FPGA IP cores support them, but they require more complex datapaths. Memory bandwidth and on-chip BRAM capacity often set the practical upper limit on N for streaming FPGA implementations.
Frequently asked
What is the difference between a DFT and an FFT?
The DFT and FFT compute identical results. The DFT is the mathematical transform definition, requiring O(N²) multiply-accumulate operations for N points. The FFT is any algorithm that exploits symmetry in the DFT's twiddle factors to compute the same result in O(N log N) operations. The Cooley-Tukey radix-2 algorithm is by far the most common FFT implementation in hardware and software.
How do I choose the FFT size N for my application?
N sets two competing parameters: frequency resolution (fs/N, where fs is the sample rate) and time resolution (N/fs, the duration of one frame). A larger N gives finer frequency bins but requires more samples and therefore more latency and memory. On FPGAs using standard radix-2 IP, N must be a power of two. Common sizes range from 64 to 4096 points for audio and control applications, and up to 32768 or more for radar and communications.
Why does my FFT output look noisy or wrong when using fixed-point arithmetic?
Fixed-point FFTs accumulate rounding error across each butterfly stage. With a radix-2 FFT, there are log2(N) stages, so a 1024-point FFT has 10 stages of potential error growth. Two common strategies are: (1) right-shift (scale down) the data by 1 bit at each stage to prevent overflow, at the cost of signal-to-noise ratio, or (2) use block
floating point, where a shared exponent is tracked per block to retain precision. Insufficient word length in the twiddle factor table also contributes noise. See 'Dealing With Fixed Point Fractions' for a broader treatment of fixed-point scaling trade-offs.
What is spectral leakage and how do I reduce it?
Spectral leakage occurs when a frequency component in the input signal does not fall exactly on an FFT bin boundary. Energy from that component spreads across neighboring bins, raising the apparent noise floor and potentially masking weaker signals. Applying a window function (Hann, Hamming, Blackman-Harris, Kaiser, etc.) to the time-domain frame before the FFT reduces leakage at the cost of slightly wider main lobes. The choice of window depends on the required dynamic range and frequency resolution for the specific application.
Is an FPGA FFT IP core always faster than a software FFT on a Cortex-M DSP?
Not always in terms of throughput per watt for small transform sizes, but for large N or high sample rates an
FPGA pipeline has a significant advantage. A Cortex-M7 running CMSIS-DSP can compute a 1024-point complex FFT in roughly 20-50 µs depending on clock rate and data type. A pipelined FPGA FFT core running at 100 MHz can sustain one output sample per clock cycle after the initial pipeline fill, giving far higher throughput for continuous streaming. For infrequent, small transforms, a software FFT on an MCU with an FPU is often the simpler and more cost-effective choice.
Differentiators vs similar concepts
The FFT is often conflated with the DFT (they produce the same output; FFT is just a faster algorithm), and with the STFT (Short-Time Fourier Transform), which applies a windowed FFT repeatedly over time to produce a time-frequency spectrogram. It is also sometimes confused with the IFFT (Inverse FFT), which transforms from the frequency domain back to the time domain using the same butterfly structure with conjugated twiddle factors. In
FPGA and DSP contexts, "FFT core" and "DFT" are sometimes used interchangeably in datasheets, but the implementation is always an FFT algorithm.
