3-快速傅立叶变换课件

第三章快速傅立叶变换FastFourierTransform(FFT)

1本章基本内容3.1DFT计算量分析3.2DIT-FFT:时域抽取FFT算法3.3DIF-FFT:频域抽取FFT算法3.4FFT反变换–IFFT3.5实序列FFT算法3.6使用FFT计算序列线性卷积(续)本章复习23.1DFT计算量分析计算复杂度是o(N2)假设是一个N长的复序列，计算它的DFT系数需要：次复数乘法和次复数加法。次复数乘法次复数加法。3基本步骤将长序列DFT分解为多级短序列的DFTs。利用旋转因子的性质减小计算量:WNkn_周期性和对称性。

减小DFT计算量的方法？DIT-FFT:时域抽取FFT算法DIF-FFT:频域抽取FFT算法43.2基2-时域抽取FFT算法2.基本概念

基2（radix-2）:N=2M

抽选：将长序列分解为短序列时域抽选法：按奇偶原则把输入长序列x(n)逐步分解成越来越短的序列。在频域使X(k)前后分组。

N点DFTN/2点DFTN/4点DFT2点DFT1个2个4个N/2个基本思想5假设N=2M,将x(n)按照n的奇偶分解为两个N/2长序列：3.2基2-时域抽取FFT算法63.2基2-时域抽取FFT算法7“蝶形”单元+-8DIT-FFT算法第1级分解流程图8点FFTDFTN/2DFTN/2x[n]偶数项x[n]奇数项“旋转因子”98-pointFFTDFTN/2DFTN/2x[n]偶数项x[n]奇数项继续按奇偶分组，划分为N/4点DFT10DIT-FFT算法第2级分解流程图8-pointFFTDFTN/4x1[n]偶数项DFTN/4x1[n]奇数项11-1-1-1-1-1-1-1-1-1-1-1-18-pointFFT计算的流程？DIT-FFT算法流程图12-1-1-1-1-1-1-1-1-1-1-1-18-pointFFT第1级第2级第3级流程图中，每一级有N/2个蝶形运算，因此每一级有N/2次复乘和N次复加，总共有M级（N=2M），因此：复乘次数：(Nlog2N)/2；复加次数：

Nlog2N；DIT-FFT算法流程图133.FFT计算量NN2(DFT)Nlog2N/2(FFT)DFT/FFT162563285122621442304113.82048419430411264372.4可以更直观地看出FFT算法的优越性，特别当点数N越大时，FFT的优点更为明显。

FFT和DFT复数乘法次数比较144.蝶形运算（1）蝶形运算在FFT信号流图中每一级结点都是成对出现的。每一对结点中上边的结点称为上结点，下边的结点称为下结点。计算时，总是上结点的值本身和下结点值乘以WNS相加减形成下一列的结点值。基本运算：“butterfly”element+-15（2）WNS的确定方法如:第0级：m=0S=(8/2)p=4p,p=0；第1级：m=1S=(8/22)p=2p,p=0,1；第2级：m=2S=(8/23)p=p,p=0,1,2,3；注意：在对偶结点中，只有下结点加权——WNS16-1-1-1-1-1-1-1-1-1-1-1-1DIT-FFT算法流程图8点FFT第1级第2级第3级蝶形运算旋转因子运算符号输入倒序输出正序？？？17x(n2n1n0)x(000)x(100)x(010)x(110)x(001)x(101)x(011)x(111)x(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)码位倒置树状图x(000)x(100)x(010)x(011)x(100)x(101)x(110)x(111)x(110)—x(011)x(6)—x(3)5.码位倒置

Q:

由8点FFT流图可见，输入数据序列顺序为：x(0)、x(4)、x(2)、x(6)、x(1)、x(5)、x(3)、x(7)

而给定的输入序列为：x(i),i=0,…,7

如何调整其码位倒置顺序？186.16点DIT-FFT（输入倒序，输出顺序）？19-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1DIT-FFT算法流程图207.减少运算量的其它方法（1）特殊的旋转因子不用计算（2）查表法218.FFT节省内存—同址运算In-PlaceComputation-1-1-1-1-1-1-1-1-1-1-1-1第1级第2级第3级（1）同一级中，每个蝶形的两个输入数据只对计算本蝶形运算有用。（2）每个蝶形的输入输出数据在同一水平线上，可利用同一存储单元蝶形计算的输入输出数据。

FFT节省内存的关键是采用了同址计算。22小结1.DFT运算复杂度分析；2.FFT算法的基本思想；3.时域抽取FFT算法（DIT-FFT）。233.3radix-2Decimation-In-FrequencyFFT频域抽选是按照奇偶原则把输出长序列X(k)逐步分解成越来越短的序列，由于X(k)是在频域进行抽取，故称为DIF-FFT。结论：一个域按奇偶抽选分组

另一个域内分为前后两组。241.基2DIF-FFT基本原理将x(n)分解为前后两组，它的DFT是:分解为奇数组(k=2r+1)和偶数组(k=2r)。25分为前后两个部分按照奇偶原则把输出长序列X(k)分解成两个短序列DFT26DIT-FFT基本结构两者区别？时域按奇偶抽选分组

频域内前后两组。DIT-FFT频域按奇偶抽选分组时域内前后两组。DIF-FFT被分解为两个点27DFTN/2x2(n)DFTN/2x1(n)8-pointDIF-FFTN/2点DFT可继续分解，得到完整流图28m=0m=1m=28-pointDIF-FFT292.蝶形运算基本运算：“butterfly”element-式中m为级数序号，最左边的一级为m=0；p,q为上下结点的序号。中S的确定方法：S=2mp对偶结点间距：先和后积与DIT蝶形区别303.16点DIF-FFT（输入顺序，输出倒序）？与DIT-FFT相比，DIT和DIF互为转置：方向取反，x(n)和X(k)互换31323.4FFT反变换1.FFT变换对比较FFT和IFFT的差别：（1）常数：1/N（2）W因子的符号FFTandIFFT:相同的代码?相同的程序结构?33令2.用FFT计算IFFT的方法方法1：利用旋转因子的周期性思路：将W因子变为正变换DFT的W因子（符号）计算过程（a）计算X(k)的FFT，得到g(n)

（b）计算x(n)=g(N-n)/NDFT定义34方法2：利用旋转因子的共轭特性思路：将W因子变为正变换DFT的W因子（符号）令计算过程

（a）计算X(k)取共轭得到X*(k)

（b）计算X*(k)的FFT，得到g(n)

（c）计算x(n)=g*(n)/N35Summary1.DIF-FFT算法思想；2.与DIT-FFT结构上的差异;3.如何使用FFT程序进行IFFT反变换。363.5实序列FFT的算法若将实序列x(n)视为虚部为0的复序列求解FFT时，浪费内存和时间1.一个N点FFT同时计算两个N点实序列设x1(n)和x2(n)是彼此独立的两个N点实序列，其DFT分别为：令且：由于DFT是一个线性变换：372.一个N点FFT计算2N点实序列设x(n)是2N点实序列，将x(n)划分为偶数组x1(n)和奇数组x2(n)

：

x1(n)=x(2n)，

x2(n)=x(2n+1)，n=0,1,2,….N-1由DFT的共轭对称性可得：？38类似于DIT-FFT分解算法2N点DFT前半部分：2N点DFT后半部分：393.6线性卷积的FFT算法1.意义（1）背景

滤波器h(n)，长度为N1，输入为长序列x(n)，滤波Filterh(n)x(n)y(n)（2）问题

用圆周卷积计算线性卷积时，补零太多，效率低。（3）解决方法x(n)长序列分解为短序列用FFT计算，以提高效率。

两种思路:

重叠相加法(overlap-addmethod)；重叠保存法(overlap-savemethod)

Toolargetocompute402重叠相加法Overlap-addmethod（1）Basicconcept

将长序列x(n)分解为N2的小段xi(n)，xi(n)为：可见：将序列x(n)的每一段xi(n)分别与h(n)卷积，然后再将卷积结果相加，即可得到输出序列y(n)。41由于：yi(n)长度为N，

xi(n)长度为N2，因此补零后发生重叠相邻两段yi(n)的重叠部分长度为：

N-N2=N1-1，重叠部分相加后=y(n)每段卷积用快速卷积办法计算，即xi(n)和h(n)补零，补到：N=N1+N2-1，用FFT计算：yi(n)=xi(n)h(n)2重叠相加法Overlap-addmethod42（2）Computing(A)求序列h(n)补零后的DFT系数H(k)，H(k)=FFT[h(n)](B)求序列xi(n)补零后的DFT系数Xi(k)，Xi(k)=FFT[xi(n)](C)计算Yi(k)=X