,可实现原位计算,具有良好的模块性,因此更容易实现。总的来说,快速傅里叶变换(Fast Fourier Transform,FFT)并不是与离散傅里叶变换不同的另一种变换,而是为了减少DFT计算次数的一种快速有效的算法。Р2.1.2 FFT原理Р快速傅氏变换(FFT),是离散傅氏变换的快速算法,它是根据离散傅氏变换的奇、偶、虚、实等特性,对离散傅里叶变换的算法进行改进获得的[2]。它对傅氏变换的理论并没有新的发现,但是对于在计算机系统或者说数字系统中应用离散傅里叶变换,可以说是进了一大步。设为N项的复数序列,由DFT变换,任一X(M)的计算都需要N次复数乘法和N-1次复数加法,而一次复数乘法等于四次实数乘法和两次实数加法,一次复数加法等于两次实数加法,即使把一次复数乘法和一次复数加法定义成一次“运算”(四次实数乘法和四次实数加法),那么求出N项复数序列的X(M),即N点DFT变换大约就需要次运算。当N=1024点甚至更多的时候,需要次运算,在FFT中,利用的周期性和对称性,把一个N项序列(设N=2k,k为正整数),分为两个项的子序列,每个点DFT变换需要次运算,再N次运算把两个点的DFT变换组合成一个N点的DFT变换。这样变换以后,总的运算次数就变成。继续上面的例子,N=1024时,总的运算次数就变成了525312次,节省了大约50%的运算量。而如果我们将这种“一分为二”的思想不断进行下去,直到分成两两一组的DFT运算单元,那么N点的DFT变换就只需要次的运算,N在1024点时,运算量仅有10240次,是先前的直接算法的1%,点数越多,运算量的节约就越大,这就是FFT的优越性。Р2.2 快速傅里叶变换算法РFFT的基本思想:将大点数的DFT分解为若干个小点数DFT的组合,从而减少运算量。Р根据对序列分解与选取方法的不同而产生了FFT的多种算法[3]。算法分类如图2-1所示:
全文预览
