资源描述：
《00 材料成形与控制工程导论(二)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、重点：1.基2时域FFT流图算法2.基2频域FFT流图算法难点：1.利用FFT流图计算IFFT2.利用N点复序列FFT，计算2N点实序列3.利用N点复序列FFT算法计算两个N点实序列快速Fourier变换(FFT)4点序列{2，3，3，2}DFT的计算复杂度复数加法N(N-1)复数乘法N2如何提高DFT的运算效率?问题的提出一般性DFT:直接计算的计算量：N-1复数乘法N对N个不同X[m]复数加法N(N-1)复数乘法N2对一固定的m复数加法如计算1024点DFT：复数乘法次数：N2=10242=220=1048576解决问
2、题的思路1.将长序列DFT分解为短序列的DFT2.利用旋转因子的周期性、对称性、可约性。1)周期性(periodicity)2)复共轭对称性(complexconjugate)3)当N是偶数时的性质解决问题的方法将时域序列逐次分解为一组子序列，利用旋转因子的特性，由子序列的DFT来实现整个序列的DFT。基2时间抽取(Decimationintime)FFT算法基2频率抽取(Decimationinfrequency)FFT算法3.1基2时域抽取FFT算法算法推导:N=2M时域抽取(Decimationintime)]a][
3、1kx][2lx][][21lxkxa+[][21lxkxa--1(一)算法原理基本蝶形(butterfly)算法推导:N=2M时域抽取例：]0[X]1[X-11]0[x]1[x2点FFT流图N=2基2时域FFT流图的推导N=4时域基2FFT流图的推导-1X[2]X[3]-12点DFT2点DFTx[0]x[3]x[1]x[2]X[0]X[1]2点DFT04W14Wx[0]x[3]x[1]x[2]X[3]X[1]X[2]X[0]-1-1-1-1N=8基2时域FFT流图的推导08W18W28W38W4点DFT4点DFTX[0]
4、X[3]X[1]X[2]X[4]X[5]X[6]X[7]x[0]x[6]x[2]x[4]x[1]x[3]x[5]x[7]-1-1-1-108W18W28W38WX[0]X[3]X[1]X[2]X[4]X[5]X[6]X[7]x[0]x[6]x[4]x[2]x[1]x[5]x[3]x[7]04W14W04W14W-1-1-1-1-1-1-1-1-1-1-1-18点FFT流图第三级第一级第二级(二)算法工作量a][1kx][2lx][][21lxkxa+][][21lxkxa--1一个蝶形计算量：复数乘法1，复数加法2复数乘法
5、:N，NNM2log22=复数加法：N=2M时，分解级数为M，每级蝶形数N/2计算1024点复数乘法次数：DFT：N2=10242=220=1048576；FFT：(三)流图规律1)原位运算(In-placeComputations)a][1kx][2lx][][21lxkxa+][][21lxkxa--1优点：节省存储空间(三)流图规律第二级的蝶形系数为，蝶形节点的距离为2。第一级的蝶形系数均为，蝶形节点的距离为1。第三级的蝶形系数为，蝶形节点的距离为4。第M级的蝶形系数为，蝶形节点的距离为N/2。2)FFT算法流图旋转
6、因子规律3)倒序规律k0k1k2x[k2k1k0]x[000]x[100]x[010]01011]12x[kk0]x[k2k101x[110]x[001]x[101]x[010]x[111]01010101例：试利用N=4基2时间抽取的FFT流图计算8点序列x[k]={1,-1,1,-1,2,1,1,2}的DFT。解：根据基2时间抽取FFT算法原理，8点序列的DFTX[m]可由两个4点序列的DFTX1[m]和X2[m]表达。如果按照序列x[k]序号的奇偶分解为x1[k]和x2[k]，则存在其中x1[k]={1,1,2,1}
7、，x2[k]={-1,-1,1,2}，X1[m]和X2[m]可通过4点的FFT来计算。解：X1[m]={5,-1,1,-1},X2[m]={1,-2+3j,1,-2-3j}利用上述公式，可得序列x[k]的DFTX[m]为X[m]={6,-0.293+3.535j,1+j,-1.707+3.535j,4,-1.707-3.535j,1-j,-0.293-3.535j}例：试利用N=4基2时间抽取的FFT流图计算8点序列x[k]={1,-1,1,-1,2,1,1,2}的DFT。3.2基2频域抽取FFT算法频域奇偶分组频域奇偶分
8、组当m=2r,或2r+1，得到：基2频率抽取蝶形运算的信号流图基2频率抽取蝶形运算的信号流图x[3]x[7]x[2]x[6]x[1]x[5]x[0]x[4]3NW-12NW-11NW-1-10NW4点DFT4点DFTX[0]X[6]X[2]X[4]X[1]X[3]X[5]X[7]基2频率抽取8点信号流图
