c++怎么实现一个简单的傅里叶变换_C++中手写FFT算法原理与实现-C++-PHP中文网

c++怎么实现一个简单的傅里叶变换_C++中手写FFT算法原理与实现

裘德小鎮的故事

发布： 2025-10-30 17:29:02

原创

394人浏览过

FFT通过分治法将DFT复杂度从O(N²)降至O(N log N)，核心是奇偶分解与蝴蝶操作；C++实现需用复数类、位翻转重排数据，并迭代合并子结果，正逆变换仅差符号及归一化，完整流程包括预处理、合并与还原验证。

c++怎么实现一个简单的傅里叶变换_c++中手写fft算法原理与实现

傅里叶变换（Fourier Transform）能将信号从时域转换到频域，而快速傅里叶变换（FFT）是其高效实现方式。在C++中手写一个简单的FFT算法，有助于理解其数学原理和递归结构。

1. FFT的基本原理

离散傅里叶变换（DFT）公式为：

X[k] = Σ (n=0 到 N−1) x[n] ⋅ e^(−2πi⋅k⋅n/N)

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

直接计算复杂度为 O(N²)。FFT利用分治思想，将序列分为奇偶两部分，递归计算，把复杂度降到 O(N log N)。

核心是“**蝴蝶操作**”（Butterfly Operation），结合单位根的周期性和对称性进行合并计算。

2. 复数支持与位翻转重排

C++标准库提供 std::complex，可直接用于复数运算。

FFT递归前需对输入数组做“位反转置换”（Bit-reversal Permutation），使数据按特定顺序排列，便于迭代合并。

例如长度为8时，索引二进制表示如下：

0: 000 → 000 → 0
1: 001 → 100 → 4
2: 010 → 010 → 2
3: 011 → 110 → 6
...依此类推

通过预处理生成位反转映射表，重新排列输入数据。

法语写作助手

法语助手旗下的AI智能写作平台，支持语法、拼写自动纠错，一键改写、润色你的法语作文。

查看详情

3. 迭代版FFT实现代码

以下是一个简洁的C++迭代FFT实现：

#include <iostream>
#include <vector>
#include <complex>
#include <cmath>
<p>using namespace std;
using Complex = complex<double>
const double PI = acos(-1);</p><p>// 位反转函数
int reverseBits(int x, int logN) {
int rev = 0;
for (int i = 0; i < logN; ++i) {
if (x & (1 << i))
rev |= 1 << (logN - 1 - i);
}
return rev;
}</p><p>// 快速傅里叶变换（原地FFT）
void fft(vector<Complex>& a, bool invert) {
int n = a.size();
int logN = 0;
while ((1 << logN) < n) ++logN;</p><pre class='brush:php;toolbar:false;'>// 位反转重排
for (int i = 0; i < n; ++i) {
    int ri = reverseBits(i, logN);
    if (i < ri)
        swap(a[i], a[ri]);
}

// 迭代合并
for (int len = 2; len <= n; len <<= 1) {
    double angle = 2 * PI / len * (invert ? 1 : -1);
    Complex wlen(cos(angle), sin(angle));
    for (int i = 0; i < n; i += len) {
        Complex w(1);
        for (int j = 0; j < len / 2; ++j) {
            Complex u = a[i + j];
            Complex v = a[i + j + len/2] * w;
            a[i + j] = u + v;
            a[i + j + len/2] = u - v;
            w *= wlen;
        }
    }
}

// 逆变换后归一化
if (invert) {
    for (int i = 0; i < n; ++i)
        a[i] /= n;
}

登录后复制

}

4. 使用示例与验证

测试一个简单信号的FFT：

int main() {
    vector<Complex> signal = {0,1,2,3,4,5,6,7}; // 长度必须为2的幂
    fft(signal, false); // 正向FFT
<pre class='brush:php;toolbar:false;'>cout << "频域结果：\n";
for (int i = 0; i < signal.size(); ++i) {
    cout << "X[" << i << "] = " << signal[i] << '\n';
}

fft(signal, true); // 逆FFT验证
cout << "\n逆变换还原：\n";
for (auto& x : signal)
    cout << x.real() << ' ';
cout << '\n';

return 0;

登录后复制

}

输出应接近原始信号，说明变换可逆。

基本上就这些。掌握FFT关键在于理解分治结构、单位根性质和蝴蝶操作。这个版本虽简单，但已具备实际用途，比如音频分析或多项式乘法。不复杂但容易忽略细节，如位反转和符号方向。

以上就是c++++怎么实现一个简单的傅里叶变换_C++中手写FFT算法原理与实现的详细内容，更多请关注php中文网其它相关文章！