C++怎么实现一个快速傅里叶变换(FFT)_C++信号处理与数值计算算法-C++-PHP中文网

C++怎么实现一个快速傅里叶变换(FFT)_C++信号处理与数值计算算法

裘德小鎮的故事

发布： 2025-11-24 21:34:02

原创

914人浏览过

快速傅里叶变换（FFT）基于分治思想，采用迭代与位逆序置换实现高效DFT计算。1. 使用std::complex表示复数，利用单位根ω_N^k的周期性加速运算；2. 通过位逆序置换预处理输入，如8点FFT下标重排为[0,4,2,6,1,5,3,7]，确保内存连续访问；3. 迭代实现中，从长度2开始逐层合并，每层用单位根旋转因子更新值，支持原地计算；4. 应用于多项式乘法时，将系数转为频域相乘再逆变换，时间复杂度O(n log n)。

c++怎么实现一个快速傅里叶变换(fft)_c++信号处理与数值计算算法

快速傅里叶变换（FFT）是离散傅里叶变换（DFT）的高效算法，广泛用于信号处理、多项式乘法和数值计算。C++中实现FFT通常采用分治思想，最常见的是基于“**迭代+位逆序置换**”的Cooley-Tukey算法。

1. 基本原理与复数支持

FFT处理的是复数序列，因此需要使用std::complex来表示复数。核心是将长度为N（要求N是2的幂）的DFT分解为更小的DFT，利用单位根的周期性和对称性减少计算量。

单位根定义为：ω_N^k = exp(-2πi * k / N)，其中i是虚数单位。

2. 位逆序置换（Bit-reversal Permutation）

递归版FFT自然完成子问题划分，但迭代版需要预先将输入数组按位逆序重排。例如，8点FFT中，下标二进制表示如下：

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

0: 000 → 000: 0
1: 001 → 100: 4
2: 010 → 010: 2
3: 011 → 110: 6
4: 100 → 001: 1
5: 101 → 101: 5
6: 110 → 011: 3
7: 111 → 111: 7

重排后顺序为 [0,4,2,6,1,5,3,7]，这样每一层合并都能连续访问内存。

3. 迭代实现FFT

以下是一个完整的C++实现，支持原地计算：

轻幕

轻幕是一个综合性短视频制作平台，诗词、故事、小说等一键成片转视频，让内容传播更生动！

查看详情

#include <iostream>
#include <vector>
#include <complex>
#include <cmath>
<p>using namespace std;
using Complex = complex<double>
const double PI = acos(-1);</p><p>// 位逆序置换
void bitReverse(vector<Complex>& a) {
int n = a.size();
int bits = 0;
while ((1 << bits) < n) bits++;</p><pre class='brush:php;toolbar:false;'>for (int i = 0; i < n; i++) {
    int rev = 0;
    for (int j = 0; j < bits; j++)
        if (i & (1 << j))
            rev |= 1 << (bits - 1 - j);
    if (i < rev)
        swap(a[i], a[rev]);
}

登录后复制

}

// 快速傅里叶变换（原地迭代版） void fft(vector<Complex>& a, bool invert) { int n = a.size(); bitReverse(a);

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 (Complex& x : a)
        x /= n;
}

登录后复制

}

4. 使用示例：多项式乘法

FFT常用于高效计算两个多项式的卷积（即系数乘法）：

vector<double> multiply(const vector<double>& a, const vector<double>& b) {
    vector<Complex> fa(a.begin(), a.end()), fb(b.begin(), b.end());
    int n = 1;
    while (n < a.size() + b.size())
        n <<= 1;
<pre class='brush:php;toolbar:false;'>fa.resize(n); fb.resize(n);

fft(fa, false);
fft(fb, false);

for (int i = 0; i < n; i++)
    fa[i] *= fb[i];

fft(fa, true);

vector<double> result(n);
for (int i = 0; i < n; i++)
    result[i] = round(fa[i].real()); // 取实部并四舍五入

return result;

登录后复制

}

输入两个系数向量，输出它们的卷积结果，时间复杂度从O(n²)降至O(n log n)。

基本上就这些。注意FFT要求长度为2的幂，如果不是可补零扩展。该实现稳定且易于集成到信号处理流程中。

以上就是C++怎么实现一个快速傅里叶变换(FFT)_C++信号处理与数值计算算法的详细内容，更多请关注php中文网其它相关文章！