直接计算DFT的计算量与变换区间长度N的平方成正比,当N
较大时,计算量太大,直接用DFT算法进行谱分析和信号的
实时处理是不切实际的。
1965年库利、图基发现了DFT的一种快速算法,使DFT的运
算效率提高1-2个数量级,为数字信号处理技术应用于各种
信号的实时处理创造了条件,推动了数字处理技术的发展。
1984年,提出了分裂基快速算法,使运算效率进一步提高;
与DFT、FFT相关的论文有2400余篇
近期,随着计算机运算单元、存储器等性能的提升,FFT算法
有一些改变。
4.1 引言