文档介绍：第4章快速傅立叶变换(FFT)
概述
时间抽取基 2 算法
频率抽取基 2 算法
减少运算量的措施
分裂基算法
线性调频 Z 变换
其它算法
概述
解决耗时的乘法问题是将数字信号处理理论用于实际的关键问题。特别是30年前,计算机的速度相当慢。因此,很多学者对解决DFT的快速计算问题产生了极大的兴趣。
Cooley J W, Tukey J W. An algorithm for the putation plex Fourier series.
Mathematics putation, 1965, pp297~301
DSP的正式开端!
FFT 的思路:
如何充分利用这些关系
?
四点 DFT
几个乘法?
时间抽取基 2 算法
FFT的核心思想是:
N点
DFT
N/2点
DFT
N/4点
DFT
2点
DFT
1个 2个 4个 N/2个
问题是如何分最有效?可以对时间变量分
(DIT),也可对频率变量分(DIF)
令:
都是 N/2 点的 DFT,它们各自又可分成 N/4 点的DFT,如此继续分下去,直至两点DFT。两点DFT不需要乘法运算:
每一级有 N/2 个如下的“蝶形”单元: