返回考点地图
B 类考点专题9-10月

混合基 FFT 的分解与输出排序

旋转因子与输出下标重排都不可省略;基 2 的运算量公式不能直接套到任意混合基流程。补零到八点得到的不是六点 DFT。

为什么要掌握

混合基 FFT 按 NN 的因子拆分小 DFT,通过旋转因子和输出重排组合回同一 NN 点频谱。它可直接处理六点等非 2 的幂长度,不需要改成补零后的另一种长度。

进入这类题的第一步

先写 N=abN=ab、输入下标 n=ar+sn=ar+s 与输出下标 k=q+bpk=q+bp,再把复指数拆成小变换与旋转因子。

核心公式与边界

Gs[q]=∑r=0b−1x[ar+s]WbrqG_s[q]=\sum_{r=0}^{b-1}x[ar+s]W_b^{rq},X[q+bp]=∑s=0a−1Gs[q]WNsqWaspX[q+bp]=\sum_{s=0}^{a-1}G_s[q]W_N^{sq}W_a^{sp},N=abN=ab。

旋转因子与输出下标重排都不可省略;基 2 的运算量公式不能直接套到任意混合基流程。补零到八点得到的不是六点 DFT。

推导与检查顺序

  1. 代入 n=ar+sn=ar+s、k=q+bpk=q+bp 后,指数中 NprNpr 对应的旋转因子 WNNpr=1W_N^{Npr}=1,剩余项分别形成 bb 点 DFT、WNsqW_N^{sq} 连接因子和 aa 点 DFT。
  2. 六点输入 [1,2,3,4,5,6][1,2,3,4,5,6] 拆为 [1,3,5][1,3,5] 与 [2,4,6][2,4,6],各做三点 DFT,再做三组二点组合,得到 X[0]=21X[0]=21 和 X[3]=−3X[3]=-3。
  3. 完整结果还需满足实输入的 X[5]=X∗[1]X[5]=X^*[1]、X[4]=X∗[2]X[4]=X^*[2];这是旋转因子符号与输出排序的交叉检查。

相关公式

  1. Gs[q]=∑r=0b−1x[ar+s]WbrqG_s[q]=\sum_{r=0}^{b-1}x[ar+s]W_b^{rq},X[q+bp]=∑s=0a−1Gs[q]WNsqWaspX[q+bp]=\sum_{s=0}^{a-1}G_s[q]W_N^{sq}W_a^{sp},N=abN=ab。
  2. N=6N=6 取 a=2,b=3a=2,b=3:X[q]=G0[q]+W6qG1[q]X[q]=G_0[q]+W_6^qG_1[q],X[q+3]=G0[q]−W6qG1[q]X[q+3]=G_0[q]-W_6^qG_1[q]。