说明¶

FFT — 快速傅里叶变换

将时域信号变换到频域，实现频率分析、频谱分析和峰值检测。基于 Cooley-Tukey Radix-2 算法，\(N\) 须为 2 的幂。

算法原理¶

从 DFT 到 FFT¶

离散傅里叶变换（DFT）定义：

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

频率分辨率：\(\Delta f = f_s / N\)，增大 \(N\) 提高分辨率
第 k 箱频率：\(f_k = k \cdot \Delta f\)，箱 0 = 直流，箱 N/2 = Nyquist

FFT 利用旋转因子 \(W_N^r = e^{-j 2\pi r / N}\) 的对称性和周期性，将 DFT 的 \(O(N^2)\) 降至 \(O(N \log N)\)。

DFT

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

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

算法流程¶

Step 1 — 位反转重排

输入序列按二进制位反转顺序重排，使每级蝶形的操作数在内存中相邻，支持原地计算。

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

Step 2 — 逐级蝶形运算

共 \(m = \log_2 N\) 级，每级 \(N/2\) 个蝶形。第 \(\ell\) 级（步长 \(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 — 窗函数预处理（可选）

\(x_w[n] = x[n] \cdot w[n]\)，减少频谱泄漏。

关键理解¶

频率分辨率 vs 频谱泄漏

增大 \(N\) 提高分辨率，但非整周期截断会导致能量扩散到相邻频点。加窗缓解泄漏但加宽主瓣。

零填充不增加分辨率

补零可插值频谱（视觉平滑），但不增加真实频率分辨率。真实分辨率唯一取决于 \(N\) 和 \(f_s\)。

幅度校正

加窗后幅度需除以窗的相干增益（coherent gain）才能得到正确幅度。

API 参考¶

初始化¶

tiny_error_t tiny_fft_init(int fft_size);      // 必须最先调用，fft_size 须为 2 的幂
tiny_error_t tiny_fft_deinit(void);            // 释放资源

正 / 逆变换¶

// 正向 FFT：实值输入 → 复数频谱
// output_fft 大小须 ≥ input_len * 2，格式：[Re0, Im0, Re1, Im1, ...]
tiny_error_t tiny_fft_f32(const float *input, int input_len,
                          float *output_fft, tiny_fft_window_t window);

// 逆向 IFFT：复数频谱 → 实值输出
tiny_error_t tiny_fft_ifft_f32(const float *input_fft, int fft_len,
                               float *output);

窗函数枚举：TINY_FFT_WINDOW_NONE · TINY_FFT_WINDOW_HANNING · TINY_FFT_WINDOW_HAMMING · TINY_FFT_WINDOW_BLACKMAN

频谱分析¶

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

// 功率谱：P[k] = |X[k]|² / N
tiny_error_t tiny_fft_power_spectrum_f32(const float *fft_result, int fft_len,
                                         float *power);

频率检测¶

// 找主频（跳过直流，含抛物线插值提高精度）
tiny_error_t tiny_fft_find_peak_frequency(const float *power_spectrum,
    int fft_len, float sample_rate, float *peak_freq, float *peak_power);

// 找前 N 个频率（局部峰值检测 + 2-bin 合并 + 插值）
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);

使用流程¶

tiny_fft_init(256);                              // 1. 一次性初始化

float input[256];                                // 2. 采集信号
float spectrum[512];                             // 复数：256×2

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

float power[256];
tiny_fft_power_spectrum_f32(spectrum, 256, power); // 4. 功率谱

float freq, mag;
tiny_fft_find_peak_frequency(power, 256,          // 5. 主频检测
                             100.0f, &freq, &mag);

tiny_fft_deinit();                                // 6. 清理