DFT和FFT算法比较.doc

DFT和FFT算法的比较摘要：快速傅里叶变(FastFourierTranformation，FFT)是将一个大点数N的DFT分解为若干小点的DFT的组合。将用运算工作量明显降低，从而大大提高离散傅里叶变换(DFT)的计算速度。因各个科学技术领域广泛的使用了FFT技术它大大推动了信号处理技术的进步，现已成为数字信号处理强有力的工具。关键词：离散傅立叶变换；快速傅立叶变换Abstract：Fast Fourier (Fast Fourier Tranformation) is to a large number N of DFT is decomposed into several smaller D F T combination. Will use computing workload is decreased obviously, thus greatly improve the discrete Fourier transform (DFT) computing speed. Due to the various areas of science and technology widely USES the FFT technology, it greatly promotes the progress of the signal processing technology, has become a powerful digital signal processing tools.Keyword：discrete Fourier transform；Fast Fourier TranformationDFT算法：FFT是一种DFT的高效算法，称为快速傅立叶变换（fast Fourier transform）。FFT算法可分为按时间抽取算法和按频率抽取算法，先简要介绍FFT的基本原理。从DFT运算开始，说明FFT的基本原理。DFT的运算为：式中由这种方法计算DFT对于X（K）的每个K值，需要进行4N次实数相乘和（4N-2）次相加，对于N个k值，共需N*N乘和N（4N-2）次实数相加。改进DFT算法，减小它的运算量，利用DFT中的周期性和对称性，使整个DFT的计算变成一系列迭代运算，可大幅度提高运算过程和运算量，这就是FFT的基本思想。FFT基本上可分为两类，时间抽取法和频率抽取法，而一般的时间抽取法和频率抽取法只能处理长度N=2M的情况，另外还有组合数基四FFT来处理一般长度的FFT。FFT算法：快速傅氏变换（FFT）是离散傅氏变换的快速算法，它是根据离散傅氏变换的奇、偶、虚、实等特性，对离散傅立叶变换的算法进行改进获得的。它对傅氏变换的理论并没有新的发现，但是对于在计算机系统或者说数字系统中应用离散傅立叶变换，可以说是进了一大步。设x(n)为N项的复数序列，由DFT变换，任一X（m）的计算都需要N次复数乘法和N-1次复数加法，而一次复数乘法等于四次实数乘法和两次实数加法，一次复数加法等于两次实数加法，即使把一次复数乘法和一次复数加法定义成一次“运算”（四次实数乘法和四次实数加法），那么求出N项复数序列的X（m）,即N点DFT变换大约就需要N2次运算。当N=1024点甚至更多的时候，需要N2=1048576次运算，在FFT中，利用WN的周期性和对称性，把一个N项序列（设N=2k,k为正整数），分为两个N/2项的子序列，每个N/2点DFT变换需要（N/2）2次运算，再用N次运算把两个N/2点的DFT变换组合成一个N点的DFT变换。这样变换以后，总的运算次数就变成N+2（N/2）2=N+N2/2。继续上面的例子，N=1024时，总的运算次数就变成了525312次，节省了大约50%的运算量。而如果我们将这种“一分为二”的思想不断进行下去，直到分成两两一组的DFT运算单元，那么N点的DFT变换就只需要Nlog2N次的运算，N在1024点时，运算量仅有10240次，是先前的直接算法的1%，点数越多，运算量的节约就越大，这就是FFT的优越性。其原理是将长序列DFT根据其内在的对称性和周期性分解为短序列的DFT之和.N点的DFT先分解为2个N/2点的DFT,每个N/2点的DFT又分解为N/4点的DFT.最小变换的点数即所谓FFT的“基数”.因此,基数为2的FFT最小变换是2点DFT(或称蝶形运算).在基数为2的N点FFT中,设N=2M,则总共可分成M级运算,每级中有N/2个蝶算,则N点FFT总共有(N/2)log2N个蝶算,而1个蝶算只需一个复数乘法,2个复数加法,因此对N点FFT需计算(N/2)log2N个复数乘法、Nlog2N个复数加法.DFT与FFT的比较：(1)运算量一般来说,FFT比DFT运算量小得多,N点的FFT需要做(N/2)log2N次乘法运算,而N点DFT需要做N2次乘法运算,由此看来N点DFT运算量大约是FFT的2N/log2N倍,例如对1024点的变换,DFT大约是FFT的200倍.然而实际应用时存在下列情况:实际应用时DFT中的乘法可以是实数和复数相乘,原因是输入信号可以是实数,而FFT只能是复数和复数的乘法,原因是FFT是分级运算的,中间运算过程都是复数运算,由此来看DFT的运算量大约是FFT的Nlog2N倍,而不是2N/log2N倍.实际应用时往往只关心整个频谱中的某一部分,甚至是只关心某些个别频点的谱线.DFT的特点是可按式(1)单独计算某一部分的谱线,而直接进行FFT的算法必须计算整个频谱后才能得到需要的那一部分频谱,实际上已造成了浪费.如果N点的变换中只关心其中的M个频点或称M条谱线,那么实际DFT的运算量大约是FFT的M/NN/log2N倍,即Mlog2N倍.例如对1024点的变换,只需关心10条谱线,那么直接用DFT和用FFT的运算量是相同的.因此,实际应用时DFT与FFT相比可能并没有那么慢,甚至有可能比FFT快.(2)点数或采样率的可选性对DFT来讲,其变换点数可任意选定,如实际应用时采样率已确定为1000Hz,如选变换点数为1000点,那么每条谱线正好可落在整数频点上.FFT的变换点数必须是有规律的,如基数为2算法的FFT其点数必须是2M,如1024点、4096点等.在实际应用时为分析方便,采样率往往要定为变换点数的倍数,如2048Hz、8192Hz,以避免变换后的频谱落在复杂的带小数点的频点上.因此实际应用时FFT在变换点数选择或采样率选择上可能会带来局限性.(3)实时性DFT运算可以用采一点后立即进行相乘、累加运算的方法,即可以采一点算一点,从采样结束到DFT变换结束只需要一个点的运算时间.而FFT运算必须在全部点采集结束后才能开始进行计算,因此从某种角度讲DFT的实时性优于FFT.(4) 数据内存开销对N点DFT来讲,如只需其中的M个频点,那么在计算时至少需2M个单元的数据内存,对N点FFT来讲则至少需2N个单元的数据内存,另外现有的FFT程序一般需要将系数放在数据内存区,因此需另选N个单元的数据内存,故DFT有可能比FFT更节省数据内存.(5)程序的复杂性DFT计算程序非常简单而且可以非常方便地在非DFT专用芯片上实现,而FFT程序较为复杂.(6) 动态范围或抗溢出性在定点运算的场合,DFT较FFT更容易实现多精度的运算,例如在TI公司的16位定点DSP处理器中,采用的数据和系数为16位,而相乘并累加的结果可设为双字节即32位,一般来讲设计合理的话不会产生计算溢出的现象,免去了复杂的溢出控制,同时输入输出信号可保持较好的动态范围.FFT在程序中有防溢出的措施,然而在定点运算的场合点数越多输入信号的动态范围越小.结论：在某些具体的应用场合,DFT与它的快速算法FFT相比可能更有优势,而FFT却存在某些局限性.在只需要求出部分频点的频率谱线时DFT的运算时间大为减少,所需的数据内存量也大为减小.DFT与FFT相比还具有变换点数或采样率选择更灵活、实时性更好、更容易控制溢出和动态范围、运算编程简单、可方便地在非DSP芯片中编程实现等优点.因此在实际应用中可以从具体条件出发来比较、选择DFT或FFT,而不应片面地由于FFT是所谓的DFT的快速算法而只选用FFT.参考文献：1YUANLi-guo,FUXin-ch