Fast Fourier Transform (FFT)

The core achievement of the FFT is reducing the computational complexity of the DFT from O(N²) to O(N log₂ N), where N is the number of data points. This exponential speedup is achieved by recursively decomposing the DFT into smaller transforms, exploiting symmetries (periodicity and conjugate symmetry) in the complex exponentials (twiddle factors). For example, a 1024-point DFT requires ~1 million operations naively, but an FFT reduces this to ~10,000, enabling real-time processing on microcontrollers.

Most FFT algorithms, like the Cooley-Tukey and Radix-2 variants, are designed for in-place computation. This means the algorithm overwrites the input array with the output frequency-domain data, requiring only O(N) additional memory for temporary variables. This minimal memory footprint is critical for TinyML deployment on microcontrollers where RAM is severely limited (often < 512 KB). The trade-off is that the original time-domain data is destroyed unless explicitly copied first.

For embedded deployment, FFT implementations often use fixed-point arithmetic instead of floating-point to save memory, increase speed, and reduce power consumption. The algorithm's structure, dealing with multiplications by pre-computed twiddle factors, is well-suited to fixed-point quantization. Careful scaling is required at each butterfly operation stage to prevent overflow, a key consideration in microcontroller inference optimization.

The two primary FFT algorithm families differ in their decomposition strategy:

• Decimation-in-Time (DIT): Re-orders the input time-domain sequence into bit-reversed order and produces a naturally ordered frequency output. The famous Cooley-Tukey algorithm is a DIT FFT.
• Decimation-in-Frequency (DIF): Takes a naturally ordered input and produces a bit-reversed frequency output. Both have identical computational complexity. The choice affects data access patterns and can influence cache performance and implementation simplicity on target hardware.

Since most sensor data (audio, vibration, IMU) is real-valued, specialized Real FFT algorithms are used. They exploit the conjugate symmetry of the DFT output for real inputs, effectively halving the required storage and computation. A standard N-point real sequence can be transformed using an N/2-point complex FFT, followed by post-processing to derive the full N-point spectrum. This is a critical optimization for sensor data processing on edge devices.

The standard FFT assumes the input signal is periodic within the analyzed window. When this isn't true (the norm for real-world signals), spectral leakage occurs—energy smears across frequency bins. To mitigate this, the time-domain data is multiplied by a window function (e.g., Hamming, Hann, Blackman) before the FFT. This trades off frequency resolution for reduced leakage. Selecting and applying the optimal window is a fundamental step in feature extraction for TinyML pipelines.

The Discrete Fourier Transform (DFT) is the fundamental mathematical operation that the FFT accelerates. It transforms a finite sequence of equally-spaced samples of a function into a same-length sequence of equally-spaced samples of its Discrete-Time Fourier Transform (DTFT), revealing the signal's frequency composition. The naive computation of the DFT has O(N²) complexity, which the FFT reduces to O(N log N).

• Core Operation: Decomposes a signal from the time domain into its constituent frequencies in the frequency domain.
• Direct Computation: Requires N² complex multiplications for a sequence of length N.
• Relation to FFT: The FFT is not a different transform; it is a family of efficient algorithms (e.g., Cooley-Tukey, Prime-Factor) for computing the DFT exactly.

The Short-Time Fourier Transform (STFT) is a Fourier-related transform used to analyze non-stationary signals whose frequency content changes over time. It works by dividing a longer time signal into shorter segments of equal length (using a windowing function) and computing the FFT on each segment separately. The result is a spectrogram, a visual representation of the spectrum of frequencies as they vary with time.

• Application: Essential for audio analysis (speech, music), vibration monitoring, and any signal where frequency components are transient.
• Parameters: Defined by window length (time resolution) and hop size (overlap between windows). A trade-off exists between time and frequency resolution.
• TinyML Consideration: Computing the STFT in real-time on a microcontroller requires careful optimization of the windowing and FFT operations to meet latency and memory constraints.

The Discrete Cosine Transform (DCT) expresses a finite sequence of data points as a sum of cosine functions oscillating at different frequencies. It is closely related to the DFT but uses only real numbers and is particularly efficient for compressing signals with energy compaction properties, meaning it concentrates most of the signal information into a few low-frequency coefficients.

• Primary Use: The foundation for lossy audio and image compression standards (e.g., MP3, JPEG, AAC).
• Type-II DCT: The most common form, used in JPEG compression.
• Comparison to FFT: While the FFT is ideal for spectral analysis and convolution, the DCT is superior for compression and feature extraction (e.g., it is a key step in calculating Mel-Frequency Cepstral Coefficients (MFCCs) for speech recognition).

The Wavelet Transform provides a multi-resolution analysis of a signal, representing it in terms of scaled and translated versions of a finite-length oscillatory waveform called a mother wavelet. Unlike the FFT, which provides perfect frequency resolution but no time localization, wavelets offer a variable-sized time-frequency window, making them ideal for analyzing transient, non-stationary signals.

• Time-Frequency Localization: Uses short windows at high frequencies and long windows at low frequencies, matching many natural signals.
• Applications: Feature extraction for transient events (e.g., ECG spikes, mechanical fault impacts), image compression (JPEG 2000), and signal denoising.
• Discrete Wavelet Transform (DWT): A computationally efficient, sub-sampled version implementable with filter banks, suitable for real-time processing on edge devices.

The Convolution Theorem states that convolution in the time domain is equivalent to pointwise multiplication in the frequency domain. This is a critical property leveraged by the FFT to dramatically accelerate convolutional operations, which are fundamental to digital filtering and the convolutional layers in Convolutional Neural Networks (CNNs).

• Mathematical Form: FFT( f * g ) = FFT(f) ⋅ FFT(g), where '*' denotes convolution and '⋅' denotes element-wise multiplication.
• Computational Advantage: Direct convolution has O(N²) complexity. Using the FFT-based method reduces this to O(N log N), a massive saving for large filters or kernels.
• TinyML Impact: Enables efficient implementation of FIR filters and small CNNs for audio or vibration classification on microcontrollers by performing the heavy computation in the frequency domain.

Spectral leakage is an artifact in FFT analysis where energy from a signal's true frequency components "leaks" into adjacent frequency bins. This occurs because the FFT assumes the input sequence is exactly one period of an infinitely repeating signal. If the sequence's length is not an integer multiple of the signal's period, discontinuities are introduced at the boundaries, causing leakage.

• Windowing Function: To mitigate leakage, the signal segment is multiplied by a window function (e.g., Hamming, Hann, Blackman) before the FFT. This function tapers the signal to zero at the edges, reducing discontinuity.
• Trade-off: Windowing reduces leakage but broadens the main lobe of frequency components, slightly reducing frequency resolution.
• Design Choice: Selecting the right window is crucial for TinyML applications like Acoustic Event Detection (AED) to accurately resolve closely spaced frequencies with limited compute.