-第3快速疼里叶变换一 31引言 快速傅里叶变换(FFT)并不是一种新的变换,而是离散傅里叶变换 (DFT)的一种快速算法。 由于有限长序列在其频域也可离散化为有限长序列(DFT),因此离散 傅里叶变换(DFT)在数字信号处理中是非常有用的。例如,在信号的频谱 分析、系统的分析、设计和实现中都会用到DFT的计算。但是,在相当长 的时间里,由于DFT的计算量太大,即使采用计算机也很难对问题进行实时 处理,所以并没有得到真正的运用。直到1965年首次发现了DFT运算的一种 快速算法以后,情况才发生了根本的变化。人们开始认识到DFT运算的一些 内在规律,从而很快地发展和完善了一套高速有效的运算方法,这就是现在 人们普遍称之为快速傅里叶变换(FFT)的算法。FFT出现后使DFT的运算 大大简化,运算时间一般可缩短一二个数量级之多,从而使DFT的运算在实 际中真正得到了广泛的应用第3章 快速傅里叶变换 3.1 引 言 快速傅里叶变换（FFT）并不是一种新的变换， 而是离散傅里叶变换 （DFT）的一种快速算法。 由于有限长序列在其频域也可离散化为有限长序列（DFT），因此离散 傅里叶变换（DFT）在数字信号处理中是非常有用的。例如，在信号的频谱 分析、 系统的分析、 设计和实现中都会用到DFT的计算。 但是，在相当长 的时间里， 由于DFT的计算量太大，即使采用计算机也很难对问题进行实时 处理，所以并没有得到真正的运用。 直到1965年首次发现了DFT运算的一种 快速算法以后，情况才发生了根本的变化。人们开始认识到DFT运算的一些 内在规律，从而很快地发展和完善了一套高速有效的运算方法， 这就是现在 人们普遍称之为快速傅里叶变换（FFT）的算法。 FFT出现后使DFT的运算 大大简化，运算时间一般可缩短一二个数量级之多，从而使DFT的运算在实 际中真正得到了广泛的应用