FFT通过分治法将DFT复杂度从O(N²)降至O(N log N)，核心是奇偶分解与蝴蝶操作；C++实现需用复数类、位翻转重排数据，并迭代合并子结果，正逆变换仅差符号及归一化，完整流程包括预处理、合并与还原验证。
傅里叶变换（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
- ...依此类推
通过预处理生成位反转映射表，重新排列输入数据。
3. 迭代版FFT实现代码
以下是一个简洁的C++迭代FFT实现：
#include#include #include #include using namespace std; using Complex = complex
const double PI = acos(-1); // 位反转函数 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; }
// 快速傅里叶变换（原地FFT） void fft(vector
& a, bool invert) { int n = a.size(); int logN = 0; while ((1 << logN) < n) ++logN; // 位反转重排 for (int i = 0; i zuojiankuohaophpcn n; ++i) { int ri = reverseBits(i, logN); if (i zuojiankuohaophpcn ri) swap(a[i], a[ri]); } // 迭代合并 for (int len = 2; len zuojiankuohaophpcn= n; len zuojiankuohaophpcnzuojiankuohaophpcn= 1) { double angle = 2 * PI / len * (invert ? 1 : -1); Complex wlen(cos(angle), sin(angle)); for (int i = 0; i zuojiankuohaophpcn n; i += len) { Complex w(1); for (int j = 0; j zuojiankuohaophpcn 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 zuojiankuohaophpcn n; ++i) a[i] /= n; }}
4. 使用示例与验证
测试一个简单信号的FFT：
int main() { vectorsignal = {0,1,2,3,4,5,6,7}; // 长度必须为2的幂 fft(signal, false); // 正向FFT cout zuojiankuohaophpcnzuojiankuohaophpcn "频域结果：\n"; for (int i = 0; i zuojiankuohaophpcn signal.size(); ++i) { cout zuojiankuohaophpcnzuojiankuohaophpcn "X[" zuojiankuohaophpcnzuojiankuohaophpcn i zuojiankuohaophpcnzuojiankuohaophpcn "] = " zuojiankuohaophpcnzuojiankuohaophpcn signal[i] zuojiankuohaophpcnzuojiankuohaophpcn '\n'; } fft(signal, true); // 逆FFT验证 cout zuojiankuohaophpcnzuojiankuohaophpcn "\n逆变换还原：\n"; for (auto& x : signal) cout zuojiankuohaophpcnzuojiankuohaophpcn x.real() zuojiankuohaophpcnzuojiankuohaophpcn ' '; cout zuojiankuohaophpcnzuojiankuohaophpcn '\n'; return 0;}
输出应接近原始信号，说明变换可逆。
基本上就这些。掌握FFT关键在于理解分治结构、单位根性质和蝴蝶操作。这个版本虽简单，但已具备实际用途，比如音频分析或多项式乘法。不复杂但容易忽略细节，如位反转和符号方向。
