文档介绍：CH9 FFT:快速傅里叶变换
主讲教师王崇骏
主要内容
[1] 引言
[2] 高效计算目标
[3] 划分和组合方法
[4] 按时间抽取的基-2FFT算法
[5] 按频率抽取
引言
DFT及IDFT公式给定如下:
缺点:计算量太大,阻碍它在实际长信号的应用。
, 0kN-1
, 0nN-1
高效计算目标
其中,WN如下:
周期性:
对称性:
充分利用周期性和对称性以减少计算量,包括下面两个具体的算法:
1)按时间抽取:
2)按频率抽取:
思路
利用对称性和周期性计算下面的4点DFT
举例:
整体思路:基于较小的DFT计算一个较大DFT
步骤:将序列化分为M个长度为L的较小序列,作M个较小的L点DFT,然后利用M个较小的L点DFT组合成一个较大的DFT。
划分和组合方法: