“自研基 2 Cooley–Tukey：倒位序 + 逐级蝶形，入口
fft(int N, complex f[])”
拆成三件事
它在讲什么
- “基 2 Cooley–Tukey”
指的是最常见的 FFT 算法：长度 N 必须是 2 的整数次幂，把离散傅里叶变换分解成一层一层的“2 点蝶形”运算，复杂度从 O(N2)O(N^2)O(N2) 降到 O(Nlog2N)O(N\log_2N)O(Nlog2N)。头文件里也写着“点数必须为 8, 16, 32, …”【】；接口层不满足时会自动补零到最近的 2 的幂。
if (originDataQueue.size() < round(pow(2, 5)))
-
“倒位序”（bit-reversal permutation）
在做蝶形之前，要把输入序列按“索引的二进制位反转”的顺序重排，这样内层蝶形才能就地计算、顺序访问。fft()里先算 M=log2NM=\log_2 NM=log2N【】，然后执行倒位序重排（i,j,k这段就是） 。 -
“逐级蝶形”（stage-by-stage butterflies）
一共 M 层。第 m 层把数据分成长度 2m2^m2m 的小组，每组做一堆 2 点蝶形；每个蝶形都要乘一个“旋转因子” WNr=e−j2πr/NW_N^r=e^{-j2\pi r/N}WNr=e−j2πr/N。代码里：-
分层与分组：
la = 2^m、lb = la/2【】； -
计算旋转因子：
Wn_i(N, r, &wn, 1)（flag=1 表示正变换取-sin） ； -
2 点蝶形核心：
t = f[lc] * wn f[lc] = f[n] - t f[n] = f[n] + t这三行就在循环里 。整段“逐级蝶形”的外层/内层循环见 。
-
“入口函数 fft(int N, complex f[])”
- 函数签名：
fft(int N, complex f[])；传入长度N和一段复数数组f。 - 就地运算：输入和输出都在同一个数组
f（in-place），不另外开输出缓冲；这一点在头文件注释里写了。 - 正/逆变换：正变换用
fft(...)；逆变换ifft(...)的实现方式是“共轭→fft→再共轭→每点除以 N” 。
这段代码的变量怎么对应
M = log2(N)：总共层数- 倒位序重排：
i,j,k三个指针完成置换 - 每层参数：
la=2^m（这一层每组长度）、lb=la/2（每组蝶形的“半距离”） - 旋转因子：
Wn_i(N,r,...)生成 e−j2πr/Ne^{-j2\pi r/N}e−j2πr/N 或 e+j2πr/Ne^{+j2\pi r/N}e+j2πr/N（逆变换） - 蝶形对下标：
n是上节点，lc = n + lb是下节点
和整条链路的关系
- C# 侧把时域数据打包成 JSON 串，调用
calcOfflineFFT_testing送到 C++； - C++ 侧先去直流、补零到 2 的幂，再调
fft(N, fftData)； - FFT 结果出来后你在接口层做了单边谱归一化（直流和奈奎斯特不乘 2，其余乘
2/N）并构建频轴df = Fs/N。
需要注意的两点
fft()本身不做幅值归一化；如果要得到幅值（如 Vrms/Arms 或幅度谱），现在是在外层完成的，这是对的。N必须是 2 的幂；已经在接口层做了检查并自动补零，避免算法报错或性能退化。
扩展举例
可以把这段算法画成一张小示意图或用 N=8 的例子演示“倒位序”如何从索引 0..7 变成 0,4,2,6,1,5,3,7，再走一层层蝶形
)
