数字信号处理程佩青第三版课件_第四章_快速傅里叶变换(FFT)

第四章快速傅里叶变换（FFT）主要内容DIT-FFT算法DIF-FFT算法IFFT算法Chirp-FFT算法线性卷积的FFT算法§4.1引言FFT:FastFourierTransform1965年，Cooley-Turky发表文章《机器计算傅里叶级数的一种算法》，提出FFT算法，解决DFT运算量太大，在实际使用中受限制的问题。FFT的应用。频谱分析、滤波器实现、实时信号处理等。DSP芯片实现。TI公司的TMS320c30，10MHz时钟，基2-FFT1024点FFT时间15ms。典型应用：信号频谱计算、系统分析等)()(kXnxDFT)()()(nynhnxFFTnhnyIFFTFFTnx)()()(系统分析频谱分析与功率谱计算§4.2直接计算DFT的问题及改进途径10)()(NnknNWnxkX10)(1)(NkknNWkXNnx1、DFT与IDFT()Nxn点有限长序列2、DFT与IDFT运算特点复数乘法复数加法一个X(k)NN–1N个X(k)(N点DFT)N2N(N–1)10()NnkNnxnWajbcjdacbdjadcb同理：IDFT运算量与DFT相同。实数乘法实数加法一次复乘42一次复加2一个X(k)4N2N+2(N–1)=2(2N–1)N个X(k)(N点DFT)4N22N(2N–1)3、降低DFT运算量的考虑nkNW的特性*()()()nknkNnknNkNNNN对称性()()nkNnknNkNNN周期性nkmnkNmNWW可约性//nknkmNNmWW0/2(/2)11NkNkNNNN特殊点：2jnknkNNWeNknkNNWWnNnkNNWW2jmnkmNe221NjjNeeFFT算法分类:时间抽选法DIT:Decimation-In-Time频率抽选法DIF:Decimation-In-FrequencyFFTDFTDFTDFTDFT算法的基本思想：利用系数的特性，合并运算中的某些项，把长序列短序列，从而减少其运算量。§4.3按时间抽取（DIT）的FFT算法12/...210)12()()2()(21Nrrxrxrxrx，，，，（DecimationInTime）1、算法原理设序列点数N=2L，L为整数。若不满足，则补零将序列x(n)按n的奇偶分成两组：N为2的整数幂的FFT算法称基-2FFT算法。将N点DFT定义式分解为两个长度为N/2的DFT10)()()(NnknNWnxnxDFTkXkrNnNrrkNnNrWrxWrx)12(12/0212/0)12()2(为奇为偶)(12/02/2)(2/12/0121)()(kXNrrkNkNkXrkNNrWrxWWrx)()()(21kXWkXkXkN记：………（1）rkNrkNWW2/2（这一步利用：）,0,1,.../21rkN再利用周期性求X(k)的后半部分/22NkNkkNNNN又)(2)()()(222112/02/112/0)2/(2/11kXkNXkXWrxWrxkNXNrrkNNrkNrNrkNkNrNWW2/)2/(2/)2()2()2()2(12/,...2,1,0)()()(2)2/(121kNXWkNXkNXNkkXWkXkXkNNkN，12/,...2,1,0)()(21NkkXWkXkN，将上式表达的运算用一个专用“蝶形”信流图表示。)(1kX)(2kX)()(21kXWkXkN)()(21kXWkXkNkNW1212()()()()()()2kNkNXkXkWXkNXkXkWXk0,1,...,/21kN注：a.上支路为加法，下支路为减法；b.乘法运算的支路标箭头和系数。用“蝶形结”表示上面运算的分解：328N)0(x)1(x)2(x)3(x)4(x)5(x)6(x)7(x)0(X)1(X)2(X)3(X)4(X)5(X)6(X)7(X1NW0NW2NW3NW)0(1X)1(1X)2(1X)3(1X)0(2X)1(2X(3)2X)2(2XDFTN点2DFTN点2分解后的运算量：复数乘法复数加法一个N/2点DFT(N/2)2N/2(N/2–1)两个N/2点DFTN2/2N(N/2–1)一个蝶形12N/2个蝶形N/2N总计22/2/2/2NNN2/21/2NNNN运算量减少了近一半进一步分解MN2122MN2N4N由于，仍为偶数，因此，两个点DFT又可同样进一步分解为4个点的DFT。1314(2)()(21)()xlxlxlxl0,1,...,/41lN13/2413/24()()()()()()4kNkNXkXkWXkNXkXkWXk0,1,...,14Nk02/NW12/NW)(3lx)(4lx)2(x)4(x)6(x)0(x)0(1X)1(1X)2(1X)3(1X)0(3X)1(3X)0(4X)1(4XDFTN点4DFTN点4“蝶形”信流图表示N点DFT分解为四个N/4点的DFTDFTN点4DFTN点4DFTN点4DFTN点4)2(x)4(x)6(x)0(x)1(x)3(x)5(x)7(x0NW2NW0NW2NW1NW0NW2NW3NW)0(X)1(X)2(X)3(X)4(X)5(X)6(X)7(X)(....kX)(.....nx类似的分解一直继续下去，直到分解为最后的两类蝶形运算为止(2点DFT).如上述N=8=23，N/4=2点中：类似进一步分解1点DFTx(0)1点DFTx(4)X3(0)X3(1)02W进一步简化为蝶形流图：0NWX3(0)X3(1)x(0)x(4))4()0()4()0()0(004/3xWxxWxXNN)4()0()4()0()1(014/3xWxxWxXNN因此8点FFT时间抽取方法的信流图如下——)2(x)4(x)6(x)0(x)1(x)3(x)5(x)7(x0NW0NW0NW0NW第一级......0NW2NW0NW2NW第二级..............)(0kX1m)(1kX)(2kX)(3kX2m3m1NW0NW2NW3NW)0(X)1(X)2(X)3(X)4(X)5(X)6(X)7(X第三级......................FFT运算量与运算特点1．N=2L时，共有L=log2N级运算；每一级有N/2个蝶形结。2．每一级有N个数据中间数据），且每级只用到本级的转入中间数据，适合于迭代运算。3．计算量：每级N/2次复乘法，N次复加。（每蝶形只乘一次，加减各一次）。共有L*N/2=N/2log2N次复乘法；复加法L*N=Nlog2N次。与直接DFT定义式运算量相比(倍数)N2/(Nlog2N)。当N大时，此倍数很大。222()2()loglog2FFmDFTNNNmFFTNN比较DFT参考P150表4-1图4-6可以直观看出，当点数N越大时，FFT的优点更突出。按时间抽取FFT蝶形运算特点1、关于FFT运算的混序与顺序处理（位倒序处理）由于输入序列按时间序位的奇偶抽取，故输入序列是混序的，为此需要先进行混序处理。混序规律：x(n)按n位置进行码位（二进制）倒置规律输入，而非自然排序，即得到混序排列。所以称为位倒序处理。位倒序实现：（1）DSP实现采用位倒序寻址（2）通用计算机实现可以有两个方法：一是严格按照位倒序含义进行；二是倒进位的加N/2。倒位序自然序00000000100410010102201011063011001141001015510101136110111771112102()()xnnnnn倒位序例计算，。计算点FFT。用时间抽取输入倒序算法，问倒序前寄存器的数和倒序后的数据值？2)(nnx31....2,1,0n32N)13(x)13(x16913)13(2x5232N210)01101()13(102)22()10110(48422)13(2x解：倒序前倒序倒序为倒序后DITFFT中最主要的蝶形运算实现（1）参与蝶形运算的两类结点（信号）间“距离”（码地址）与其所处的第几级蝶形有关；第m级的“结距离”为(即原位计算迭代）（2）每级迭形结构为，12m)2(,...2,1LNLmrNmmmmmrNmmmmWkXkXkXWkXkXkX)2()()2()2()()(1111111蝶形运算两节点的第一个节点为k值，表示成L位二进制数，左移L–m位，把右边空出的位置补零，结果为r的二进制数。2()2Lmrk（3）的确定：第m级的r取值：rNWkNW四、FFT算法中一些概念（1）“级”概念将N点DFT先分成两个N/2点DFT，再是四个N/4点DFT…直至N/2个两点DFT.每分一次称为“一”级运算。因为N=2M所以N点DFT可分成M级如上图所示依次m=0,m=1….M-1共M级（2）“组”概念每一级都有N/2个蝶形单元，例如：N=8,则每级都有4个蝶形单元。每一级的N/2个蝶形单元可以分成若干组，每一组具有相同的结构，相同的因子分布，第m级的组数为：rNW12mN例：N=8=23，分3级。m=0级,分成四组,每组系数为m=1级,分成二组,每组系数为m=2级,分成一组,每组系数为080204/28082012/02/,,,382818083210,,,,,,(3)因子的分布rNW121,0,,3,2,102101001238281808828081404408022mkkkkkWm级的系数为看出：第，，，级，，，，级，级，由上可知：结论：每由后向前（m由M-1--0级）推进一级，则此系数为后级系数中偶数序号的那一半。DIT算法的其他形式流图输入倒位序输出自然序输入自然序输出倒位序输入输出均自然序相同几何形状输入倒位序输出自然序输入自然序输出倒位序参考P154-155时间抽取、输入自然顺序、输出倒位序的FFT流图0NW0NW0NW2NW－1－1－10NW－10NW2NW－1－1－1－1X(0)x(0)X(4)x(1)X(2)x(2)X(6)x(3)X(1)x(4)X(5)x(5)X(3)x(6)X(7)x(7)－1－10NW0NW2NW1NW3NW－1－1例用FFT算法处理一幅N×N点的二维图像，如用每秒可做10万次复数乘法的计算机，当N=1024时，问需要多少时间（不考虑加法运算时间）？解当N=1024点时，FFT算法处理一幅二维图像所需复数乘法约为次，仅为直接计算DFT所需时间的10万分之一。即原需要3000小时，现在只需要2分钟。722210log2NN§4.4按频率抽取（DIF）的FFT算法与DIT-FFT算法类似分解，但是抽取的是X(k)。即分解X(k)成奇数与偶数序号的两个序列。设：N=2L，L为整数。将X(k)按k的奇偶分组前，先将输入x(n)按n的顺序分成前后两半：（DecimationInFrequency)一、算法原理12/12/0)()()(NNnnkNNnnkNWnxWnxkX12/0)(212/02)()(NnknNNNnnkNNWnxWnx12/022/)()(NnnkNNkNNWnxWnxkNkNW)1(2//210()(1)2NknkNnNx