FFT在功率谱密度计算中的应用.doc

《FFT在功率谱密度计算中的应用.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、FFT在功率谱密度计算中的应用一、FFT算法理论依据和编程思想FFT算法的基本思想：   考察DFT与IDFT的运算发现，利用以下两个特性可减少运算量：Ⅰ)系数是一个周期函数，它的周期性和对称性可利用来改进运算，提高计算效率。如:   因此   利用这些周期性和对称性，DFT运算中有些项可合并；   Ⅱ）利用WNnk的周期性和对称性，把长度为N点的大点数的DFT运算分解为若干个小点数的DFT。因为DFT的计算量正比于N2，N小计算量也就小。FFT算法正是基于这样的基本思想发展起来的。它有多种形式，下面是按时间抽取的FFT（N点DFT运算的分解）  

2、 先从一个特殊情况开始，假定N是2的整数次方，N=2M，M：正整数 1.将N点的DFT分解为两个N/2点的DFT：首先将序列x（n）分解为两组，一组为偶数项，一组为奇数项r=0,1，…，N/2-1将DFT运算也相应分为两组：                                          其中X1（k）和X2（k）分别是x1（r）和x2（r）的N/2点DFT。   可见，一个N点的DFT可以分解为两个N/2点的DFT，这两个N/2点的DFT再按照上面（1）式合成为一个N点DFT，注意到，X1（k），X2（k）有N/2个点，即k=0

3、，1，…，N/2-1，由（1）式得到X（k）只有N/2点，而实际上X（k）有N个点，即k=0，1，…，N-1，要用X1（k），X2（k）表示全部X（K）值，还必须应用系数w的周期性和对称性。2.X(k)的(N/2)～N-1点表示：   由X(k)=X1（k）+wkNX2（k）,k=0,1,2,…,N/2-1得：，（2a）因为,   且   同样。   考虑到WNk对称性：。   故（2b）（2a）式表示了X（k）前半部分k=0～N/2-1时的组成方式，（2b）式则表示了后半部分k=N/2～N-1时的组成方式。这两式所表示的运算过程可用一个称作蝶形的

4、信号流图来表示。3.蝶形信号流图：   如图1（a）所示，图中左面两支为输入，中间以一个小圆圈表示加、减运算，右上支为相加输出，右下支为相减输出，如果在某一支路上信号需要进行乘法运算，则在该支路上标以箭头，并将相乘的系数标在简头边，这样（2a），（2b）所表示的运算，可用图1（b）所表示的“蝶形结”来表示。采用这种表示法，可将以上以讨论的分解过程用计算流图来表示。图2.6所示为N=23=8的例子。通过这样分解以后，每一个N/2点DFT只需要图2.6N点DFT分解为2个N/2点DFT（N=8）(N/2)2=N2/4次复数乘法运算，两个N/2点的DFT

5、需要2(N/2)2=N2/2次复乘，再加上将两个N/2点DFT合成为N点DFT时，在蝶形结前的N/2次复乘，共需要(N/2)2+N/2≈N2/2次复乘，由此可见，经过这样的分解处理，运算量差不多节省了一倍。4.将N/2点的DFT分解为两个N/4点的DFT：   既然这样分解是有效的，由于N=2M，N/2仍然是偶数，因此可对两个N/2点的DFT再分别作进一步分解，例如对x1（r）和x2（r）可以再按其偶数部分及奇数部分分解为两个N/4点的DFT，既然这样分解是有效的，由于N=2M，N/2仍然是偶数，因此可对两个N/2点的DFT再分别作进一步分解，例如

6、对x1（r）和x2（r）可以再按其偶数部分及奇数部分分解为两个N/4点的DFT，     l=0,1,…，N/4-1而同样X2(k)也可这样分解，并且将系数统一为，这样一个8点DFT就可分解为四个2点的DFT，如图2.7所示。图2.7N点DFT分解为4个N/4点的DFT(N=8)5.2个点DFT的表示：最后剩下的是2点DFT，它可以用一个蝶形结表示，例如，x（0），x（4）所组成的2点DFT就可表示式：这样，一个8点的完整的按时间抽取运算的流图如图2.8所示。由于这样的方法每一步分解都是按输入时间序列是属于偶数还是奇数来抽取的，所以称为“按时间抽取

7、法”或“时间抽取法”。6.时间抽取法FFT运算特点：（1）蝶形运算   对任何一2的整数幂N=2M，总是可以通过M次分解最后完全成为2点的DFT运算。这样的M次分解，就构成从x(n)到X(k)的M级运算过程。从上面的流图可看到，每一级运算都由N/2个蝶形运算构成。因此每一级运算都需要(N/2次复乘和N次复加(每个结作加、减各一次)，这样，经过时间抽取后M级运算总共需要的运算：复乘 复加N·M=Nlog2N实际运算量与这个数字稍有出入，因为W这几个系数实际上都不用乘法运算，因此在上面N=8的例子中，实际上只有两个系数WN1及WN3是需要乘法运算的。 

8、  用时间抽取法所需的计算量，不论是复乘还是复加都与Nlog2N成正比，而直接运算时则与N2成正比。例N=2048，N2=