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

分裂基 FFT 的三路分解与四组输出

正变换采用 WN=e−j2π/NW_N=e^{-j2\pi/N} 时,两条奇支路分别乘 WNkW_N^k 与 WN3kW_N^{3k};第二、第四组的差项系数分别为 −j-j、+j+j。子变换长度为 11 或 22 时直接计算。

为什么要掌握

分裂基 FFT 将 NN 点输入拆成一组 N/2N/2 点偶序列和两组 N/4N/4 点奇序列,复用旋转乘积一次生成四个频率点。标准递归长度为 N=2mN=2^m。

进入这类题的第一步

先按 2r2r、4r+14r+1、4r+34r+3 分组,再分别计算 EE、UU、VV;取 Q=N/4Q=N/4,对每个 0≤k<Q0\le k<Q 写回 kk、k+Qk+Q、k+2Qk+2Q、k+3Qk+3Q 四个输出位置。

核心公式与边界

E=DFT⁡N/2{x[2r]}E=\operatorname{DFT}_{N/2}\{x[2r]\},U=DFT⁡Q{x[4r+1]}U=\operatorname{DFT}_{Q}\{x[4r+1]\},V=DFT⁡Q{x[4r+3]}V=\operatorname{DFT}_{Q}\{x[4r+3]\},Q=N/4Q=N/4。

正变换采用 WN=e−j2π/NW_N=e^{-j2\pi/N} 时,两条奇支路分别乘 WNkW_N^k 与 WN3kW_N^{3k};第二、第四组的差项系数分别为 −j-j、+j+j。子变换长度为 11 或 22 时直接计算。

推导与检查顺序

  1. 把 DFT 求和按三类输入下标拆开,利用 WN2=WN/2W_N^2=W_{N/2}、WN4=WQW_N^4=W_Q 得到 X[k]=E[k]+WNkU[k]+WN3kV[k]X[k]=E[k]+W_N^kU[k]+W_N^{3k}V[k]。
  2. 频率下标增加 QQ 时,UU、VV 周期回到原值,旋转支路分别多乘 −j-j、jj,所以组合为 E[k+Q]−j(Ak−Bk)E[k+Q]-j(A_k-B_k);增加 2Q2Q、3Q3Q 同理得到另两组。
  3. 八点输入 [1,2,3,4,5,6,7,8][1,2,3,4,5,6,7,8] 得到 E=[16,−4+4j,−4,−4−4j]E=[16,-4+4j,-4,-4-4j]、U=[8,−4]U=[8,-4]、V=[12,−4]V=[12,-4];组合后 X[0]=36X[0]=36、X[1]=−4+4(1+2)jX[1]=-4+4(1+\sqrt2)j、X[3]=−4+4(2−1)jX[3]=-4+4(\sqrt2-1)j、X[4]=−4X[4]=-4。
  4. 直接 DFT 可独立验算:对 k=1,…,7k=1,\ldots,7,几何级数求导给出 X[k]=−8/(1−W8k)=−4+4jcot⁡(πk/8)X[k]=-8/(1-W_8^k)=-4+4j\cot(\pi k/8)。实输入还满足 X[8−k]=X∗[k]X[8-k]=X^*[k]。

相关公式

  1. E=DFT⁡N/2{x[2r]}E=\operatorname{DFT}_{N/2}\{x[2r]\},U=DFT⁡Q{x[4r+1]}U=\operatorname{DFT}_{Q}\{x[4r+1]\},V=DFT⁡Q{x[4r+3]}V=\operatorname{DFT}_{Q}\{x[4r+3]\},Q=N/4Q=N/4。
  2. Ak=WNkU[k]A_k=W_N^kU[k],Bk=WN3kV[k]B_k=W_N^{3k}V[k],Sk=Ak+BkS_k=A_k+B_k,Dk=Ak−BkD_k=A_k-B_k。
  3. X[k]=E[k]+SkX[k]=E[k]+S_k,X[k+Q]=E[k+Q]−jDkX[k+Q]=E[k+Q]-jD_k,X[k+2Q]=E[k]−SkX[k+2Q]=E[k]-S_k,X[k+3Q]=E[k+Q]+jDkX[k+3Q]=E[k+Q]+jD_k,0≤k<Q0\le k<Q。