“自研基 2 Cooley–Tukey：倒位序 + 逐级蝶形，入口 fft(int N, complex f[])”

拆成三件事

---

它在讲什么

1. “基 2 Cooley–Tukey”
   指的是最常见的 FFT 算法：长度 N 必须是 2 的整数次幂，把离散傅里叶变换分解成一层一层的“2 点蝶形”运算，复杂度从 $O(N^2)$ 降到 $O(N{\log }_{2}N)$。头文件里也写着“点数必须为 8, 16, 32, …”【】；接口层不满足时会自动补零到最近的 2 的幂。

if (originDataQueue.size() < round(pow(2, 5)))

2. “倒位序”（bit-reversal permutation）
   在做蝶形之前，要把输入序列按“索引的二进制位反转”的顺序重排，这样内层蝶形才能就地计算、顺序访问。 fft() 里先算 $M={\log }_{2}N$【】，然后执行倒位序重排（i,j,k 这段就是） 。

3. “逐级蝶形”（stage-by-stage butterflies）
   一共 M 层。第 m 层把数据分成长度 $2^m$ 的小组，每组做一堆 2 点蝶形；每个蝶形都要乘一个“旋转因子” $W_N^r=e^{-j2\pi 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\pi r/N}$ 或 $e^{+j2\pi 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，再走一层层蝶形