为什么要掌握
分裂基 FFT 将 N 点输入拆成一组 N/2 点偶序列和两组 N/4 点奇序列,复用旋转乘积一次生成四个频率点。标准递归长度为 N=2m。
进入这类题的第一步
先按 2r、4r+1、4r+3 分组,再分别计算 E、U、V;取 Q=N/4,对每个 0≤k<Q 写回 k、k+Q、k+2Q、k+3Q 四个输出位置。
推导与检查顺序
- 把 DFT 求和按三类输入下标拆开,利用 WN2=WN/2、WN4=WQ 得到 X[k]=E[k]+WNkU[k]+WN3kV[k]。
- 频率下标增加 Q 时,U、V 周期回到原值,旋转支路分别多乘 −j、j,所以组合为 E[k+Q]−j(Ak−Bk);增加 2Q、3Q 同理得到另两组。
- 八点输入 [1,2,3,4,5,6,7,8] 得到 E=[16,−4+4j,−4,−4−4j]、U=[8,−4]、V=[12,−4];组合后 X[0]=36、X[1]=−4+4(1+2)j、X[3]=−4+4(2−1)j、X[4]=−4。
- 直接 DFT 可独立验算:对 k=1,…,7,几何级数求导给出 X[k]=−8/(1−W8k)=−4+4jcot(πk/8)。实输入还满足 X[8−k]=X∗[k]。
相关公式
- E=DFTN/2{x[2r]},U=DFTQ{x[4r+1]},V=DFTQ{x[4r+3]},Q=N/4。
- Ak=WNkU[k],Bk=WN3kV[k],Sk=Ak+Bk,Dk=Ak−Bk。
- X[k]=E[k]+Sk,X[k+Q]=E[k+Q]−jDk,X[k+2Q]=E[k]−Sk,X[k+3Q]=E[k+Q]+jDk,0≤k<Q。