The Discrete Fourier Transform (DFT) decomposes a finite sequence of equally spaced samples into a sum of complex sinusoids, producing a frequency-domain representation of the original discrete-time signal. It is the foundational algorithm behind spectrum analysis, filtering, and convolution in digital signal processing.
In practice
In embedded work, the DFT appears most often through its fast implementation, the FFT (Fast Fourier Transform), which computes the same result as an N-point DFT but reduces the operation count from O(N²) to O(N log N). On MCUs with enough RAM and a hardware multiplier or DSP extension -- such as ARM Cortex-M4/M7 parts, which typically include DSP instructions and an optional FPU -- real-time spectrum analysis, vibration monitoring, motor current analysis, and audio processing are all common applications. On smaller 8-bit or 16-bit devices without hardware floating-point, fixed-point DFT implementations are used, but N is typically kept small to stay within cycle budgets.
A key practical concern is understanding what the N output bins actually represent. Each bin k corresponds to a frequency of k * Fs / N, where Fs is the sample rate. The upper half of the output (bins N/2 through N-1 for real input) mirrors the lower half due to conjugate symmetry, so only bins 0 through N/2 carry unique information for real-valued signals (for even N, bin N/2 is the Nyquist bin and is self-conjugate). Misreading the bin-to-frequency mapping is a common source of errors in embedded DSP implementations.
Windowing is another practical consideration. Applying the DFT directly to a block of samples is commonly modeled as implicitly assuming the signal repeats periodically with period N, which is the standard way to explain spectral leakage. When the signal is not periodic within the window -- which is almost always the case in practice -- spectral leakage spreads energy from a single frequency across many bins. Multiplying the input samples by a window function (Hann, Hamming, Blackman, etc.) before the transform reduces leakage at the cost of frequency resolution. The blog post "Learn to Use the Discrete Fourier Transform" covers this tradeoff in detail.
For applications that require a frequency-domain result updated sample-by-sample rather than block-by-block, the sliding DFT computes only the bins of interest incrementally, updating each new output using the previous result and one new sample. This avoids recomputing the full transform every sample period. The blog post "A Fast Guaranteed-Stable Sliding DFT Algorithm" describes a numerically stable variant suitable for embedded use, since naive sliding DFT implementations can accumulate floating-point errors over time.
Learn this in DSP Foundations
Discussed on DSPRelated
Frequently asked
What is the difference between the DFT and the FFT?
The DFT is the mathematical transform; the
FFT is any of several algorithms that compute the exact same result more efficiently by exploiting divide-and-conquer factorizations and structural symmetries in the computation. The most common FFT family (Cooley-Tukey radix-2) requires N to be a power of two, though mixed-radix, prime-factor, and Bluestein/Chirp-Z variants handle other lengths. Radix-2 Cooley-Tukey reduces the asymptotic operation count from O(N²) to O(N log N), with the exact count depending on the algorithm, radix, and implementation. Libraries like CMSIS-DSP on ARM Cortex-M provide optimized FFT routines that should be used in place of a naive DFT loop in almost all embedded applications.
How do I choose the right N (DFT size) for my application?
N controls both frequency resolution (
Fs / N Hz per bin) and latency (N samples must be collected before a result is available). A larger N gives finer frequency resolution but increases memory use, computation time, and latency. For power-of-two
FFT implementations, common choices on embedded targets are 64 to 1024 points for real-time audio or vibration work, constrained by available RAM and the cycle budget per output block.
What is spectral leakage and how do I reduce it?
Spectral leakage occurs when the signal within the analysis window is not an exact integer number of cycles, causing energy from one frequency to spread into neighboring bins. Multiplying the input samples by a
window function before the DFT reduces leakage. The Hann window is a common default choice; Blackman and Kaiser windows offer lower sidelobe levels at the cost of wider main lobes. The rectangular window (no windowing) is only appropriate when the signal is guaranteed to be periodic within the block.
Can I run a DFT or FFT on a microcontroller without floating-point hardware?
Yes. Fixed-point (
Q15 or Q31)
FFT implementations are well established and are used on 8-bit and 16-bit MCUs as well as on Cortex-M0/M0+ parts that lack an FPU. CMSIS-DSP provides Q15 and Q31 FFT functions for ARM Cortex-M targets. The tradeoff is reduced dynamic range compared to
floating-point, and care must be taken with scaling between stages to avoid overflow.
What is the sliding DFT and when is it useful in embedded systems?
The sliding DFT updates a frequency-domain result one sample at a time rather than processing a full block. It is useful when low latency is required, such as detecting a specific tone (e.g.,
DTMF) or tracking a slowly varying frequency. Only the bins of interest need to be computed, which can be far more efficient than a full
FFT when just a few bins are needed. As covered in 'A Fast Guaranteed-Stable Sliding DFT Algorithm', care is needed to avoid error accumulation in recursive implementations.
Differentiators vs similar concepts
The DFT is often conflated with the
FFT, but the FFT is an algorithm that computes the DFT, not a different transform. The DFT is also distinct from the DTFT (Discrete-Time
Fourier Transform): the DTFT operates on an infinite discrete sequence and produces a continuous frequency spectrum, while the DFT operates on a finite-length block and produces a finite set of discrete frequency samples. In continuous-time signal processing, the analogous tool is the Fourier Transform or Fourier Series; the DFT is the discrete, finite-length counterpart suited to digital computation.
