基时域频域FFT算法

1、基时域频域FFT算法第1页，共33页，2022年，5月20日，12点22分，星期二4点序列2，3，3，2 DFT的计算复杂度复数加法N(N-1)复数乘法N 2如何提高DFT的运算效率?问题的提出第2页，共33页，2022年，5月20日，12点22分，星期二 一般性DFT:直接计算的计算量：N-1复数乘法N对N个不同Xm复数加法N(N-1)复数乘法N2对一固定的m复数加法如计算1024点DFT： 复数乘法次数： N2 =10242 = 220 = 1048576 第3页，共33页，2022年，5月20日，12点22分，星期二解决问题的思路1.将长序列DFT分解为短序列的DFT2.利用旋转因子 的

2、周期性、对称性、可约性。第4页，共33页，2022年，5月20日，12点22分，星期二1)周期性(periodicity)2)复共轭对称性(complex conjugate)3)当N是偶数时的性质第5页，共33页，2022年，5月20日，12点22分，星期二解决问题的方法 将时域序列逐次分解为一组子序列，利用旋转因子的特性，由子序列的DFT来实现整个序列的DFT。基2时间抽取(Decimation in time)FFT算法基2频率抽取(Decimation in frequency)FFT算法第6页，共33页，2022年，5月20日，12点22分，星期二3.1 基2时域抽取FFT算法算法推

3、导: N=2M时域抽取(Decimation in time)a1kx2lx21lxkxa+21lxkxa-1(一)算法原理 基本蝶形(butterfly)第7页，共33页，2022年，5月20日，12点22分，星期二算法推导: N=2M时域抽取第8页，共33页，2022年，5月20日，12点22分，星期二例：0X1X-110 x1x2点FFT流图N=2基2时域FFT流图的推导第9页，共33页，2022年，5月20日，12点22分，星期二N=4时域基2FFT流图的推导-1X2X3-12点DFT2点DFTx0 x3x1x2X0X12点DFT04W14Wx0 x3x1x2X3X1X2X0-1-1-

4、1-1第10页，共33页，2022年，5月20日，12点22分，星期二N=8基2时域FFT流图的推导08W18W28W38W4点DFT4点DFTX0X3X1X2X4X5X6X7x0 x6x2x4x1x3x5x7-1-1-1-1第11页，共33页，2022年，5月20日，12点22分，星期二08W18W28W38WX0X3X1X2X4X5X6X7x0 x6x4x2x1x5x3x704W14W04W14W-1-1-1-1-1-1-1-1-1-1-1-18点FFT流图第三级第一级第二级第12页，共33页，2022年，5月20日，12点22分，星期二(二 ) 算法工作量a1kx2lx21lxkxa+2

5、1lxkxa-1一个蝶形计算量： 复数乘法 1，复数加法 2复数乘法:N，NNM2log22=复数加法：N=2M时，分解级数为 M，每级蝶形数 N/2计算1024点复数乘法次数： DFT： N 2 =1024 2 = 220 = 1048576 ；FFT：第13页，共33页，2022年，5月20日，12点22分，星期二(三) 流图规律1) 原位运算(In-place Computations)a1kx2lx21lxkxa+21lxkxa-1优点：节省存储空间第14页，共33页，2022年，5月20日，12点22分，星期二(三) 流图规律第二级的蝶形系数为 ，蝶形节点的距离为2。第一级的蝶形系数

6、均为 ，蝶形节点的距离为1。第三级的蝶形系数为 ，蝶形节点的距离为4。第M级的蝶形系数为 ，蝶形节点的距离为N/2。2)FFT算法流图旋转因子 规律第15页，共33页，2022年，5月20日，12点22分，星期二3)倒序规律k0k1k2xk2 k1k0 x000 x100 x0100101112 xkk0 xk2 k101x110 x001x101x010 x11101010101第16页，共33页，2022年，5月20日，12点22分，星期二例：试利用N=4基2时间抽取的FFT流图计算8点序列xk=1, -1, 1, -1, 2, 1, 1, 2的DFT。解： 根据基2时间抽取FFT算法原理

7、，8点序列的DFT Xm可由两个4点序列的DFT X1m和X2m表达。如果按照序列xk序号的奇偶分解为x1k和 x2k，则存在 其中x1k=1, 1, 2, 1，x2k=-1, -1, 1, 2，X1m和X2m可通过4点的FFT来计算。第17页，共33页，2022年，5月20日，12点22分，星期二解： X1m=5, -1, 1, -1, X2m=1, -2+3j, 1, -2-3j利用上述公式，可得序列xk的DFT Xm为Xm=6, -0.293+3.535j, 1+j, -1.707 + 3.535j, 4, -1.707-3.535j, 1-j, -0.293-3.535j例：试利用N=

8、4基2时间抽取的FFT流图计算8点序列xk=1, -1, 1, -1, 2, 1, 1, 2的DFT。第18页，共33页，2022年，5月20日，12点22分，星期二3.2 基2频域抽取FFT算法频域奇偶分组第19页，共33页，2022年，5月20日，12点22分，星期二频域奇偶分组当m=2r,或2r+1，得到：第20页，共33页，2022年，5月20日，12点22分，星期二基2频率抽取蝶形运算的信号流图基2频率抽取蝶形运算的信号流图 第21页，共33页，2022年，5月20日，12点22分，星期二x3x7x2x6x1x5x0 x43NW-12NW-11NW-1-10NW4点DFT4点DFTX

9、0X6X2X4X1X3X5X7基2频率抽取8点信号流图第22页，共33页，2022年，5月20日，12点22分，星期二0NW1NW2NW3NW2 点DFT-1-1-1-1x0 x3x1x2x4x5x6x7X0X6X4X2X1X5X3X70NW2NW2NW0NW-1-1-1-12 点DFT2 点DFT2 点DFT基2频率抽取8点信号流图第23页，共33页，2022年，5月20日，12点22分，星期二基2频率抽取8点信号流图第24页，共33页，2022年，5月20日，12点22分，星期二3.3 实序列的FFT算法(二)利用N点复序列的FFT，计算2N点实序列FFT(一)利用N点复序列的FFT计算两

10、个N点实序列FFT第25页，共33页，2022年，5月20日，12点22分，星期二已知 x k, hk是实序列，构造N点复序列 yk= x k+j hk(一)利用N点复序列的FFT计算两个N点实序列FFT所以第26页，共33页，2022年，5月20日，12点22分，星期二(二)利用N点复序列的FFT，计算2N点实序列FFT已知yk是2N点实序列，希望用一个N点FFT计算其DFT 时域抽取FFT 算法：第27页，共33页，2022年，5月20日，12点22分，星期二3.4 IDFT的快速算法第28页，共33页，2022年，5月20日，12点22分，星期二IDFT的快速算法步骤步骤 (1) 将X

11、m取共轭(3)对(2)中结果取共轭并除以N第29页，共33页，2022年，5月20日，12点22分，星期二例：已知xk=1,2,3,4利用频域抽样流图， 计算12344-262j10-2-2+2j-2-2jDFTxk=10, -2+2j,-2,-2-2j利用频域基2-FFT流图计算DFT第30页，共33页，2022年，5月20日，12点22分，星期二4, 8, 12, 164, 16, 12, 8利用FFT流图计算IFFT第31页，共33页，2022年，5月20日，12点22分，星期二M=4;N=51;n=-(N-1)/2:(N-1)/2;x=ones(1,M+1),zeros(1,N-2*M-1),ones(1,M);X=fft(x,N);subplot(2,1,1);stem(n,fftshift(x);ylabel(xn);xlabel(Time n);ome