C++语言FFT算法实现（手把手教你用C++编写快速傅里叶变换进行信号处理）

什么是FFT？

FFT是离散傅里叶变换（DFT）的一种高效算法。DFT的计算复杂度为 O(N²)，而FFT通过分治策略将其优化到 O(N log N)，大大提升了计算速度。特别适用于数据点数为2的幂次（如 2, 4, 8, 16, ..., 1024 等）的情况，这类算法称为基-2 FFT。

前置知识

• 复数的基本运算（加法、乘法）
• C++中的结构体或类（用于表示复数）
• 递归或迭代思想（本文采用递归方式便于理解）

步骤一：定义复数结构

由于FFT涉及复数运算，我们先定义一个简单的复数结构体：

struct Complex {    double real, imag;    Complex(double r = 0.0, double i = 0.0) : real(r), imag(i) {}    // 复数加法    Complex operator + (const Complex& b) const {        return Complex(real + b.real, imag + b.imag);    }    // 复数减法    Complex operator - (const Complex& b) const {        return Complex(real - b.real, imag - b.imag);    }    // 复数乘法    Complex operator * (const Complex& b) const {        return Complex(real * b.real - imag * b.imag,                       real * b.imag + imag * b.real);    }};

步骤二：实现FFT核心函数

我们采用经典的Cooley-Tukey递归算法。基本思想是：将长度为N的序列分成偶数索引和奇数索引两部分，分别进行FFT，再合并结果。

#include <cmath>#include <vector>const double PI = acos(-1.0);void fft(std::vector<Complex>& a, bool invert) {    int n = a.size();    if (n == 1)        return;    // 分成偶数和奇数下标    std::vector<Complex> even(n/2), odd(n/2);    for (int i = 0; i < n/2; ++i) {        even[i] = a[2*i];        odd[i]  = a[2*i + 1];    }    // 递归处理    fft(even, invert);    fft(odd, invert);    // 合并结果    double ang = 2 * PI / n * (invert ? -1 : 1);    Complex w(1), wn(cos(ang), sin(ang));    for (int i = 0; i < n/2; ++i) {        a[i]     = even[i] + w * odd[i];        a[i + n/2] = even[i] - w * odd[i];        if (invert) {            a[i].real /= 2;            a[i + n/2].real /= 2;            a[i].imag /= 2;            a[i + n/2].imag /= 2;        }        w = w * wn;    }}

说明：

• invert = false 表示正向FFT（时域→频域）
• invert = true 表示逆FFT（频域→时域），此时需除以2进行归一化

步骤三：使用示例

下面是一个完整的测试程序，对一个简单信号进行FFT，并输出频谱幅度：

#include <iostream>#include <vector>#include <cmath>// （此处插入上面的 Complex 结构体和 fft 函数）int main() {    // 构造一个长度为8的实信号（必须是2的幂）    std::vector<Complex> signal = {        Complex(1,0), Complex(1,0), Complex(1,0), Complex(1,0),        Complex(0,0), Complex(0,0), Complex(0,0), Complex(0,0)    };    // 执行FFT    fft(signal, false);    // 输出频谱幅度 |X[k]| = sqrt(real^2 + imag^2)    std::cout << "频谱幅度:\n";    for (size_t i = 0; i < signal.size(); ++i) {        double magnitude = sqrt(signal[i].real * signal[i].real +                                signal[i].imag * signal[i].imag);        std::cout << "X[" << i << "] = " << magnitude << std::endl;    }    return 0;}

注意事项

• 输入数据长度必须是2的整数幂，否则需要补零（zero-padding）
• 本实现为教学目的，未做性能优化；实际项目可考虑使用FFTW等专业库
• FFT结果是对称的（对于实信号），通常只需关注前 N/2 个点

总结

通过本文，你已经掌握了如何用C++语言实现FFT算法。这不仅是学习快速傅里叶变换C++的关键一步，也为后续深入C++信号处理打下坚实基础。希望这个FFT实现教程能帮助你理解背后的数学原理与编程技巧。

动手试试吧！修改输入信号，观察频谱变化，你会发现信号世界的奇妙之处。