为什么要掌握
混合基 FFT 按 N 的因子拆分小 DFT,通过旋转因子和输出重排组合回同一 N 点频谱。它可直接处理六点等非 2 的幂长度,不需要改成补零后的另一种长度。
进入这类题的第一步
先写 N=ab、输入下标 n=ar+s 与输出下标 k=q+bp,再把复指数拆成小变换与旋转因子。
推导与检查顺序
- 代入 n=ar+s、k=q+bp 后,指数中 Npr 对应的旋转因子 WNNpr=1,剩余项分别形成 b 点 DFT、WNsq 连接因子和 a 点 DFT。
- 六点输入 [1,2,3,4,5,6] 拆为 [1,3,5] 与 [2,4,6],各做三点 DFT,再做三组二点组合,得到 X[0]=21 和 X[3]=−3。
- 完整结果还需满足实输入的 X[5]=X∗[1]、X[4]=X∗[2];这是旋转因子符号与输出排序的交叉检查。
相关公式
- Gs[q]=∑r=0b−1x[ar+s]Wbrq,X[q+bp]=∑s=0a−1Gs[q]WNsqWasp,N=ab。
- N=6 取 a=2,b=3:X[q]=G0[q]+W6qG1[q],X[q+3]=G0[q]−W6qG1[q]。