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

基 2 FFT 的蝶形与运算量

蝶形下支路要减去同一个旋转因子乘积。补零可凑成基 2 长度,但不增加原记录的真实频率分辨能力。

为什么要掌握

FFT 利用复指数的周期性和对称性,重复使用小规模 DFT 的结果。它得到的频谱与 DFT 定义完全相同;基 2 算法要求数据长度是 2 的整数次幂。

进入这类题的第一步

问时间抽取 FFT 时,把输入按偶数下标和奇数下标分组;问蝶形、级数或运算量时先写 N=2mN=2^m。

核心公式与边界

X[k]=E[k]+WNkO[k]X[k]=E[k]+W_N^kO[k],X[k+N/2]=E[k]−WNkO[k]X[k+N/2]=E[k]-W_N^kO[k],其中 WN=e−j2π/NW_N=e^{-j2\pi/N}。

蝶形下支路要减去同一个旋转因子乘积。补零可凑成基 2 长度,但不增加原记录的真实频率分辨能力。

推导与检查顺序

  1. 将 DFT 求和中的偶数下标 n=2rn=2r 和奇数下标 n=2r+1n=2r+1 分开。两组求和都是 N/2N/2 点 DFT,奇数组额外乘 WNkW_N^k。
  2. 由于 WNk+N/2=−WNkW_N^{k+N/2}=-W_N^k,同一对 EE、OO 可一次算出相隔 N/2N/2 的两个输出,这对加减运算称为蝶形。
  3. 例如 8 点基 2 FFT 有 3 级、每级 4 个蝶形,通常计 12 次复乘;因子为 ±1\pm1、±j\pm j 的乘法还能简化,所以实际乘法条数取决于题目计数约定。

相关公式

  1. X[k]=E[k]+WNkO[k]X[k]=E[k]+W_N^kO[k],X[k+N/2]=E[k]−WNkO[k]X[k+N/2]=E[k]-W_N^kO[k],其中 WN=e−j2π/NW_N=e^{-j2\pi/N}。
  2. 基 2 FFT 有 log⁡2N\log_2N 级,每级 N/2N/2 个蝶形;通常按 (N/2)log⁡2N(N/2)\log_2N 次复乘和 Nlog⁡2NN\log_2N 次复加计数。