B 类考点专题9-10月
基 2 FFT 的蝶形与运算量
蝶形下支路要减去同一个旋转因子乘积。补零可凑成基 2 长度,但不增加原记录的真实频率分辨能力。
为什么要掌握
FFT 利用复指数的周期性和对称性,重复使用小规模 DFT 的结果。它得到的频谱与 DFT 定义完全相同;基 2 算法要求数据长度是 2 的整数次幂。
进入这类题的第一步
问时间抽取 FFT 时,把输入按偶数下标和奇数下标分组;问蝶形、级数或运算量时先写 。
核心公式与边界
,,其中 。
蝶形下支路要减去同一个旋转因子乘积。补零可凑成基 2 长度,但不增加原记录的真实频率分辨能力。
推导与检查顺序
- 将 DFT 求和中的偶数下标 和奇数下标 分开。两组求和都是 点 DFT,奇数组额外乘 。
- 由于 ,同一对 、 可一次算出相隔 的两个输出,这对加减运算称为蝶形。
- 例如 8 点基 2 FFT 有 3 级、每级 4 个蝶形,通常计 12 次复乘;因子为 、 的乘法还能简化,所以实际乘法条数取决于题目计数约定。
相关公式
- ,,其中 。
- 基 2 FFT 有 级,每级 个蝶形;通常按 次复乘和 次复加计数。