No.2014211218 Cla.2014211304 史文翰
基 2 的 DIT-FFT 算法实验报告
一、 算法原理
本实验实现基 2 的 DIT-FFT 算法,基于分治法的思想,将时域上的快速傅里叶变换
用 C++语言实现。
对于 DFT 变换,表达式为
计算一个 X(K)需要 N 次复数乘法和 N-1 次复数加法。算出全部的 N 点 X(k)
共需要 N^2 次复数乘法和 N(N-1)次复数加法。即计算量是 O(N^2)。如果可以将
DFT 分解成若干组合,利用蝶型运算,可以达到分而治之的目的。我们利用旋转因子 W
的若干性质:
可以化简运算。
对于时间抽取的 FFT 即 DIT-FFT 将输入序列 x(n)按奇偶分为两组。
那么 DFT 也可以相应地表示为: