Skip to content

NOTES

FFT — Fast Fourier Transform

Transform signals from time domain to frequency domain for spectral analysis and peak detection. Based on the Cooley-Tukey Radix-2 algorithm; \(N\) must be a power of 2.

Algorithm

From DFT to FFT

Discrete Fourier Transform (DFT):

\[ X[k] = \sum_{n=0}^{N-1} x[n] \cdot e^{-j \frac{2\pi kn}{N}} \]

  • Frequency resolution: \(\Delta f = f_s / N\)
  • Bin frequency: \(f_k = k \cdot \Delta f\), bin 0 = DC, bin N/2 = Nyquist

FFT exploits twiddle factor \(W_N^r = e^{-j 2\pi r / N}\) symmetry, reducing \(O(N^2)\) to \(O(N \log N)\).

  • DFT

    \(O(N^2)\)
    \(N = 1024\) → 1,048,576 ops

  • FFT

    \(O(N \log N)\)
    \(N = 1024\) → 10,240 ops

Algorithm Steps

Step 1 — Bit-Reversal Permutation

Reorder input by binary-reversed indices so butterfly operands are adjacent in memory (enables in-place computation).

Example \(N=8\): 0(000)→0, 1(001)→4(100), 2(010)→2(010), 3(011)→6(110)

Step 2 — Butterfly Stages

\(m = \log_2 N\) stages, \(N/2\) butterflies each. Stage \(\ell\) (stride \(s=2^\ell\)):

\[ \begin{aligned} X'[k] &= X[k] + WN^r \cdot X[k + s/2] \\ X'[k + s/2] &= X[k] - WN^r \cdot X[k + s/2] \end{aligned} \]

Step 3 — Windowing (optional)

\(x_w[n] = x[n] \cdot w[n]\), reduces spectral leakage.

Key Takeaways

Resolution vs Leakage

Larger \(N\) improves resolution. Non-integer-period truncation causes spectral leakage; windowing helps but widens the main lobe.

Zero Padding ≠ Real Resolution

Padding zeros interpolates the spectrum visually but adds no real frequency resolution.

Amplitude Correction

Divide windowed magnitudes by the window's coherent gain for correct amplitudes.

API Reference

Initialization

tiny_error_t tiny_fft_init(int fft_size);      // call once; fft_size must be power of 2
tiny_error_t tiny_fft_deinit(void);            // free resources

Forward / Inverse Transform

// Forward FFT: real input → complex spectrum
// output_fft must be ≥ input_len * 2, format: [Re0, Im0, Re1, Im1, ...]
tiny_error_t tiny_fft_f32(const float *input, int input_len,
                          float *output_fft, tiny_fft_window_t window);

// Inverse FFT: complex spectrum → real output
tiny_error_t tiny_fft_ifft_f32(const float *input_fft, int fft_len,
                               float *output);

Window enum: TINY_FFT_WINDOW_NONE · TINY_FFT_WINDOW_HANNING · TINY_FFT_WINDOW_HAMMING · TINY_FFT_WINDOW_BLACKMAN

Spectrum Analysis

// Magnitude: |X[k]| = sqrt(Re² + Im²)
tiny_error_t tiny_fft_magnitude_f32(const float *fft_result, int fft_len,
                                    float *magnitude);

// Power spectrum: P[k] = |X[k]|² / N
tiny_error_t tiny_fft_power_spectrum_f32(const float *fft_result, int fft_len,
                                         float *power);

Frequency Detection

// Find dominant frequency (skips DC, parabolic interpolation for accuracy)
tiny_error_t tiny_fft_find_peak_frequency(const float *power_spectrum,
    int fft_len, float sample_rate, float *peak_freq, float *peak_power);

// Find top N frequencies (local peak detection + 2-bin merging + interpolation)
tiny_error_t tiny_fft_find_top_frequencies(const float *power_spectrum,
    int fft_len, float sample_rate, int top_n,
    float *frequencies, float *powers);

Workflow

tiny_fft_init(256);                              // 1. One-time init

float input[256];                                // 2. Acquire signal
float spectrum[512];                             // complex: 256×2

tiny_fft_f32(input, 256, spectrum,               // 3. Windowed FFT
             TINY_FFT_WINDOW_HANNING);

float power[256];
tiny_fft_power_spectrum_f32(spectrum, 256, power); // 4. Power spectrum

float freq, mag;
tiny_fft_find_peak_frequency(power, 256,          // 5. Peak frequency
                             100.0f, &freq, &mag);

tiny_fft_deinit();                                // 6. Cleanup