C++怎么实现一个快速傅里叶变换(FFT)_C++信号处理中的核心算法实现

夜明君_6912

发布时间：2025-11-23 09:14:02

416人浏览过

来源于php中文网

原创

快速傅里叶变换（FFT）通过分治法将DFT复杂度从O(N²)降至O(N log N)。C++实现需用std::complex和vector，递归拆分奇偶序列并合并结果，适用于2的幂长度信号。示例中构造含1Hz和3Hz的正弦信号，经FFT后输出频域幅度谱。实际应用建议改用迭代版、支持非2幂长度及调用FFTW等优化库以提升性能与稳定性。该实现适合教学理解，为进阶应用打下基础。

c++怎么实现一个快速傅里叶变换(fft)_c++信号处理中的核心算法实现

快速傅里叶变换（FFT）是信号处理中将时域信号转换为频域的关键算法。C++实现FFT通常基于“分治法”优化离散傅里叶变换（DFT），将复杂度从 O(N²) 降低到 O(N log N)。下面介绍一个简洁、可运行的递归版FFT实现，适用于复数序列。

1. 复数支持与头文件准备

C++标准库提供 std::complex 支持复数运算，配合 <vector> 存储数据：

#include <iostream>
#include <vector>
#include <complex>
#include <cmath>
<p>using namespace std;
using Complex = complex<double>;</p>

2. 递归实现FFT核心函数

该版本要求输入长度为2的幂。核心思想是将序列分为奇偶两部分，分别计算后合并：

vector<Complex> fft(vector<Complex> a) {
    int n = a.size();
    if (n == 1) return {a[0]};
<pre class='brush:php;toolbar:false;'>// 拆分为偶数和奇数索引子序列
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];
}

// 递归计算子问题
vector<Complex> y_even = fft(even);
vector<Complex> y_odd = fft(odd);

// 合并结果
vector<Complex> y(n);
double angle = 2 * M_PI / n;
Complex w(1), wn(cos(angle), sin(angle)); // 单位根

for (int k = 0; k < n / 2; k++) {
    y[k]         = y_even[k] + w * y_odd[k];
    y[k + n/2]   = y_even[k] - w * y_odd[k];
    w           *= wn; // 累乘单位根
}
return y;

}

立即学习“C++免费学习笔记（深入）”；

C++ Code Review Master

组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。

下载

3. 使用示例：对正弦信号进行频谱分析

生成一个含两个频率成分的合成信号，并用FFT提取频域信息：

int main() {
    const int N = 8;
    vector<Complex> signal(N);
<pre class='brush:php;toolbar:false;'>// 构造信号：sin(2πf1 t) + 0.5*sin(2πf2 t)
for (int i = 0; i < N; i++) {
    double t = i / static_cast<double>(N);
    signal[i] = sin(2*M_PI*1*t) + 0.5*sin(2*M_PI*3*t);
}

// 执行FFT
vector<Complex> result = fft(signal);

// 输出幅度谱
cout << "Frequency Magnitudes:\n";
for (int i = 0; i < N; i++) {
    double mag = abs(result[i]);
    cout << "Bin " << i << ": " << mag << '\n';
}

return 0;

}

立即学习“C++免费学习笔记（深入）”；