Digital

/ˌɛf ɛf ˈtiː/

n. "Efficient algorithm computing Discrete Fourier Transform converting time signals to frequency domain via divide-and-conquer."

FFT is a fast algorithm that decomposes time-domain signals into frequency components using Cooley-Tukey radix-2 butterflies, reducing O(N²) DFT complexity to O(NlogN)—essential for SDR spectrum analysis, Bluetooth channel equalization, and EMI diagnosis. Radix-2 decimation-in-time recursively splits even/odd samples computing twiddle factors e^(-j2πkn/N) across log2(N) stages.

Key characteristics of FFT include:

• Complexity Reduction: O(NlogN) vs O(N²) direct DFT; 1024-pt FFT needs 5K ops vs 1M.
• Radix-2 Butterfly: X(k)=X_even(k)+W^k*X_odd(k) pairs inputs across stages.
• Power-of-2 Sizes: 256/1024/4096-pt optimal; zero-padding handles arbitrary lengths.
• Windowing: Hanning/Hamming reduces spectral leakage from non-periodic signals.
• Real FFT: 2x throughput via conjugate symmetry for real-valued inputs.

A conceptual example of FFT spectrum analysis flow:

1. Capture 1024 IQ samples @10Msps from SDR ADC
2. Apply Hanning window: x[n] *= 0.5*(1-cos(2πn/N))
3. FFT 1024-pt radix-2 → 512 frequency bins 0-5MHz
4. Compute PSD: |X(k)|² / (fs*N) dB/Hz
5. Peak detect Bluetooth 2402-2480MHz channels
6. Waterfall display 100ms frame updates

Conceptually, FFT is like sorting a deck of cards by color and number simultaneously—divide-and-conquer splits time samples into even/odd halves recursively until single frequencies emerge, revealing FHSS hops or EMI spurs invisible in time domain.

In essence, FFT powers modern DSP from HBM-fed AI accelerators analyzing PAM4 eyes to HPC climate models, enabling SerDes equalization and LED driver harmonic analysis on ENIG boards.