快速傅立叶变换(FFT)课件.ppt

《快速傅立叶变换(FFT)课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、快速傅立叶变换（FFT)理论及算法实现直接计算DFT的问题及改进途径设x(n)为N点有限长序列，其DFT为一般来说，x(n)和都是复数，X(k)也是复数，因此每计算一个X(k)值，需要N次复数乘法以及（N-1)次复数加法。而X(k)一共有N个点，所以完成整个DFT运算总共需要次复数乘法及N(N-1)次复数加法。直接计算DFT的问题及改进途径由于一次复数乘法需用四次实数加法；一次复数加法则需二次实数加法。因此每运算一个X(k)需要4N次实数乘法及2N+2(N-1)=2(2N-1)次实数加法。所以整个DFT运算总共需要次实数乘法和次加法。例如：N=

2、1024时，DFT需要复乘1,048,576次。所以，直接计算DFT对实时性很强的信号处理来说，对计算速度要求是太高了。直接计算DFT的问题及改进途径仔细观察DFT的运算就可以看出，利用系数的以下固有特性，就可以减小DFT的运算量：1、的对称性2、的周期性由此可得出直接计算DFT的问题及改进途径这样，(1)利用这些特性，使DFT运算中有些项可以合并；(2)利用的对称性和周期性，可以将长序列的DFT分解为短序列的DFT。前面已经说过，DFT的运算量与成正比，所以N越小越有利。快速傅立叶变换就是在这种思路下发展起来的。下面将详细介绍。按时间抽取的F

3、FT算法先设序列长度为,L为整数。将的序列x(n)(n=0,1,..,N-1),先按n的奇偶分成两组r=0,1,…,-1则将DFT化为按时间抽取的FFT算法可以得到由于则上式可表示成式中及分别是及的点DFT由上式可以看出，一个N点DFT已分解为两个点DFT，它们又可以组合成一个N点DFT。按时间抽取的FFT算法按时间抽取的FFT算法但是，以及都是点的序列即r,k满足r,k=0,…,-1。而却有N点，而用上面的式子计算得到的只是的前一半项数的结果，要用来表达全部的值，还必须应用系数的周期性，即这样可得到按时间抽取的FFT算法同理可得：上两式说明了

4、后半部分k值()所对应的分别等于前半部分k值()所对应的。再考虑到的对称性这样，就可以得到分为前后两部分得表达：前半部分按时间抽取的FFT算法后半部分这样，只要求出0到()区间得所有值，即可求出0到（N－1）区间内的所有值，这就大大节省了运算。按时间抽取的FFT算法上面的式子可以用下面的蝶形图符号表示：可以看出，每个蝶性运算，需要一次复数乘法及两次复数加(减)法。据此，一个N点DFT分解为两个点DFT只需要次复数乘法，次复数加法，两个点DFT共需次复按时间抽取的FFT算法数乘法和次复数加法。此外把两个点DFT合成N点DFT时，有个蝶性运算，还需

5、要次复数乘法及次复数加法。因而通过这一步分解后，总共需要次复数乘法和次复数加法，可见通过这样的分解后运算工作量差不多减少到一半。FFT的软件实现1.指数因子的确定每一蝶算得输出都含有指数因子，因而如何根据不同蝶算确定具体的k值是编程过程需要考虑的重要问题。一般规律是随着极数及节点数而变化，当DIT输入反序，则每级有个。第一级均为第二级为、共=组第三级为、、、共=组……FFT的软件实现2.整序由于基2的FFT，若正序输入则反序输出，因此需要经过整序才便于读取和应用处理后的数据。参见下图。FFT的软件实现m01234567FFT的软件实现3.2个实

6、序列的DFT的计算从FFT的流图可见，由第一级输出开始，算法的所有变量都是复数，即此后蝶算的输入和输出均为复数。因而在考虑FFT算法时将输入序列x(n)设置为复数，更具有普遍意义。且将两个实数当作一个复数来计算，可以减少运算量。下面来说明如何由计算一个复数序列的FFT来等效得到两个实数序列的FFT。FFT的软件实现设有两个待处理的实数序列,令复数序列，则按DFT线性性质有由于又可以表示为根据DFT线性与复共轭性质，故得