DSP-5-2014(新).

第五章快速傅里叶变换(FFT)数字信号处理DigitalSignalProcessing中国民航大学航空自动化学院nx(n)第5章快速傅里叶变换(FFT)FFT：引言直接计算DFT的问题及改进的途径按时间抽取的基2-FFT算法(掌握)按频率抽取的基2-FFT算法(掌握)本章主要内容进一步减少运算量的措施(理解)第5章快速傅里叶变换(FFT)FFT:FastFourierTransform1965年，JamesW.Cooley和JohnW.Tukey在《计算数学》（《MathematicsofComputation》）上发表了“一种用机器计算复序列傅立叶级数的算法（AnalgorithmforthemachinecalculationofcomplexFourierseries）”论文。自此之后，新的算法不断涌现。一种是对N等于2的整数次幂的算法，如基2算法，基4算法。另一种是N不等于2的整数次幂的算法，例如Winagrad算法，素因子算法。Dr.JamesW.CooleyWorkedatIBMWatsonResearchCenterinYorktownHeights,N.Y..AfterhisretirementfromIBMin1991,hejoinedtheElectricalEngineeringDepartmentattheUniversityofRhodeIsland.2020/1/113FFT：直接计算DFT的运算量分析第5章快速傅里叶变换(FFT)N点有限长序列x(n)的DFT变换对的定义为：10()()NnkNnXkxnW0,,1kN2jNNWe101()()NnkNkxnXkWN0,,1nN其中假设x(n)是复序列，同时X(k)一般也是复数。FFT：直接计算DFT的运算量分析第5章快速傅里叶变换(FFT)FFT：直接计算DFT的运算量分析第5章快速傅里叶变换(FFT)10102X(k)=()()NnNnkNnjnkNxnneWxFFT：直接计算DFT的运算量分析计算量分析N次复数相乘N-1次复数相加N2次复数相乘N（N-1）次复数相加第5章快速傅里叶变换(FFT)如N=512、1024和8192时，DFT的乘法运算N2=5122=218=262144（26万次）N2=10242=220=1048576（105万次）N2=81922=226=67108864（6千7百万次）N2次复数相乘N（N-1）次复数相加一次复数乘法需四次实数乘法和二次实数加法一次复数加法需两次实数加法1010ImRe)(Im)(Re)()(NnnkNnkNnkNNnWjWnxjnxWnxkXFFT：直接计算DFT的运算量分析采用通用计算机，速度为平均每次复乘为5μs，每次复加为1μs，所用时间:T=5*10-6*10242+10-6*1024*1023=6.290s第5章快速傅里叶变换(FFT)1.如果一台通用计算机的速度为平均每次复乘，每次复加，用它来计算512点的，问直接计算需要多少时间，用运算需要多少时间。5s0.5sDFTxnFFT解：(1)直接利用计算：复乘次数为，复加次数为。DFT2N1NN复乘所需时间626215105105121.31072TNs复加所需时间6260.51010.51051251210.130816TNNs所以直接利用DFT计算所需时间：121.441536TTTsFFT：直接计算DFT的运算量分析第5章快速傅里叶变换(FFT)对于大N，在实际中是不能接受的，无法“实时”应用DFT。•一般地，在计算机中，一次加法比一次乘法所需时间要短;•在DSP中，由于乘法用特殊的硬件电路专门完成，因此乘法和加法所需机器周期相同。Cooley与Turkey提出的FFT算法，大大减少了计算次数。如N=512时，FFT的乘法次数约为2000次，提高了约128倍，而且简化随N的增加而巨增，因而，用数值方法计算频谱得到实际应用。FFT：直接计算DFT的运算量分析第5章快速傅里叶变换(FFT)FFT：旋转因子的特点把长序列分解成短序列计算，然后再组合出结果。nkNW主要原理是利用系数的以下特性对DFT进行分解：nkNW（1）对称性()nkNW()kNnNW（2）周期性()()nNknkNnkNNN（3）可约性mnknkmNNWW//nknkmNNmWW另外，12/NNWkNNkNWW)2/(第5章快速傅里叶变换(FFT)DFT高效运算的可能性分析：假定x(n)为4点长的信号，对其做4点DFT：04040404)3()2()1()0()0(WxWxWxWxX34241404)3()2()1()0()1(WxWxWxWxX64442404)3()2()1()0()2(WxWxWxWxX94643404)3()2()1()0()3(WxWxWxWxX利用旋转因子的4个特点：)]3()1([)]2()0([)0(xxxxX14)]3()1([)]2()0([)1(WxxxxX--14)]3()1([)]2()0([)3(WxxxxX---)]3()1([)]2()0([)2(xxxxX计算量？计算量？FFT：旋转因子的特点显然N值越小越有利！第5章快速傅里叶变换(FFT)FFT算法分类:时间抽选法DIT:Decimation-In-Time频率抽选法DIF:Decimation-In-Frequency基本思路：虽然存在不同的FFT方法，但其核心思想大致相同，即通过迭代，反复利用低点数的DFT完成高点数的DFT计算，以此达到降低运算量的目的。迭代：利用WNkn的周期性、特殊点和对称性，合并DFT计算中很多重复的计算，达到降低运算量的目的。低点数：将傅氏变换DFT分解成相继小的DFT计算，即N变小，而计算量与N2成正比。FFT：基本思想第5章快速傅里叶变换(FFT)FFT：基2时间抽选法-算法原理算法原理设序列点数N=2M，M为整数。若不满足，则补零。将序列x(n)按n的奇偶分成两组：N为2的整数幂的FFT算法称基-2FFT算法。即一组由偶数序号组成，另一组由奇数序号组成。12()(2)0,1,,12()(21)xrxrNrxrxr偶序列奇序列注意其长度为N/2第5章快速傅里叶变换(FFT)111000NNNnknknkNNNnnnXkxnWxnWxnWn为偶数n为奇数212121200221//NNrkrkNNrrxrWxrW2121221200//NNrkrkkNNNrrxrWWxrW2121120202////NNNrkkrkrNNrxrWWxrW12kNXkWXk0112,,...k=0,1,...N-1Nr注意：这里的k的取值范围为0，1，…，N-1FFT：基2时间抽选法-算法原理第5章快速傅里叶变换(FFT)偶数取样点DFT为：NN-1-122krkr1N21N2r=0r=0X(k)=x(2r)W=x(r)W112222002122X()()(r)NNkrkrNNrrkxrWxW0121,,.../k=0,1,...N-1rN奇数取样点DFT为：①k的整个范围为0～(N-1)，而X1(k)、X2(k)是由N/2个样点形成的DFT，x(2r)和x(2r＋1）的长度为N/2；②由这两个偶数和奇数N/2个时域样值可以计算出前N/2个DFT系数，也可以计算出后N/2个DFT系数。③问题：这前后N/2个DFT有无关系？k在N/2～(N-1)时，X1(k)、X2(k)、WN情况如何？FFT：基2时间抽选法-算法原理第5章快速傅里叶变换(FFT)1122,,,NNkN当时0122,,,NNkll令观察21()())(kNXkXWXkk分为三部分第一第三第二则2221122()22110012102()()(2)(2)2(2)()NNNNNNNrlrrlrrNrlNrNXkXlxrWxrWWxrWXl2222221NjrNNrjrNWeeN-12kr1N2r=0X(k)=x(2r)WFFT：基2时间抽选法-算法原理第5章快速傅里叶变换(FFT)因此：整个X(k)的计算，可以分解为前、后半部分的运算。而只要求出前一半，就可以由上式求出整个序列。同理2222()()()NXkXlXl而2()222(1)NNNljkljNNNNN因此1122()()()()()()2kNkNNXkXkWXXkkXkWXk0,1,,12NkFFT：基2时间抽选法-算法原理第5章快速傅里叶变换(FFT)上式表示为信号流程图：此信号流程图也称为蝶形流程图1122()()()()()()2kNkNNXkXkWXXkkXkWXk0,1,,12Nk)(1kX)(2kX)()(21kXWkXkNkNW)()(21kXWkXkN1偶数点的DFT奇数点的DFT()Xk()2NXkMorphoButterfly大闪蝶(南美洲)FFT：基2时间抽选法-算法原理第5章快速傅里叶变换(FFT)122()()()kNNXkXkWXkFFT：基2时间抽选法-算法原理偶数序列奇数序列12()()()kNXkXkWXk以N=8为例，分解为2个4点的DFT，然后做8/2=4次蝶形运算即可求出所有8点X(k)的值。第5章快速傅里叶变换(FFT)复数乘法次数：N2复数加法次数：N(N－1)复数乘法次数：2*(N/2)2+N/2=N2/2+N/2复数加法次数：2*(N/2)(N/2－1)+2*N/2=N2/2N点DFT的运算量分解一次后所需的运算量＝2个N/2的DFT＋N/2蝶形：因此通过一次分解后，运算工作量减少了差不多一半。FFT：基2时间抽选法-算法原理第5章快速傅里叶变换(FFT)二次分解：将x1(r)按r取奇、偶可分解成2个长度为N/4的子序列x3(l)=x1(2h)、x4(l)=x1(2h+1)，根据上面推导可得：X1(k)=X3(k)+WN/2kX4(k)，k=0,1,…,N/2-1将x2(r)按r取奇、偶可分解成2个长N/4的子序列x5(l)=x2(2h)，h=0,1,…，N/4x6(l)=x2(2h+1)；同理得h=0,1,…，N/4-1；X1(k+N/2)=X3(k)WN/2kX4(k)，k=0,1,…,N/4-1；X1(k)=X3(k)+WN/2kX4(k)，k=0,1,…,N/4-1；X2(k)=X5(k)+WN/2kX6(k)，k=0,1,…,N/4-1；X2(k+N/2)=X5(k)WN/2kX6(k),k=0,1,…,N/4-1；FFT：基2时间抽选法-算法原理第5章快速傅里叶变换(FFT)FFT：基2时间抽选法-算法原理第5章快速傅里叶变换(FFT)由于N=2M，这样逐级分解，直到2点DFT当N=8时，可分解三次00033223010332230010410104()()()()()()()()()()NNXxWWxxWxXxWWxxWx/41133/43/400()()()NlklkNNllXkxlWxlW0,1k0004422401044224(0)(0)(1)(2)(6)(1)(0)(1)(2)(6)NNXxWWxxWxXxWWxxWx4114444400///()()()NlklkNNllXkxlWxlW