“自研基 2 Cooley–Tukey：倒位序 + 逐級蝶形，入口
fft(int N, complex f[])”
拆成三件事
它在講什么
- “基 2 Cooley–Tukey”
指的是最常見的 FFT 算法：長度 N 必須是 2 的整數次冪，把離散傅里葉變換分解成一層一層的“2 點蝶形”運算，復雜度從 O(N2)O(N^2)O(N2) 降到 O(Nlog?2N)O(N\log_2N)O(Nlog2?N)。頭文件里也寫著“點數必須為 8, 16, 32, …”【】；接口層不滿足時會自動補零到最近的 2 的冪。
if (originDataQueue.size() < round(pow(2, 5)))
-
“倒位序”（bit-reversal permutation）
在做蝶形之前，要把輸入序列按“索引的二進制位反轉”的順序重排，這樣內層蝶形才能就地計算、順序訪問。fft()里先算 M=log?2NM=\log_2 NM=log2?N【】，然后執行倒位序重排（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，再走一層層蝶形
)
