第四章快速傅里叶变换课件.ppt

1、第四章快速傅里叶变换第四章快速傅里叶变换1965年年库利库利-图基图基计算数学计算数学(Mathematic of Computation )“机器计算傅里叶级数的一种算法机器计算傅里叶级数的一种算法”揭开了揭开了FFT发展史上的第一页发展史上的第一页1967年至年至1968年间年间FFT的数字硬件制成的数字硬件制成电子数字计算机电子数字计算机FFT算法迅速发展算法迅速发展DFT走向实用走向实用一、直接计算直接计算DFT算法算法存在的问题及改进途径存在的问题及改进途径问题提出：问题提出：设有限长序列设有限长序列x(n),非零值长度为非零值长度为N,计算对计算对x(n)进行一次进行一次DFT运算

2、，共运算，共需多大的运算工作量需多大的运算工作量?(一)存在的问题存在的问题1.比较比较DFT与与IDFT之间的运算量之间的运算量10)()()(NnknNDFTWnxkXnx1, 1 , 0Nk 10)()()(NkknNIDFTWkXnxkX1, 1 , 0Nn其中x(n)为复数， 也为复数所以DFT与与IDFT二者计算量相同二者计算量相同。knNjknNeW22. DFT的复数运算量的复数运算量10)()(NnknNWnxkX计算一个计算一个X(k)(一个频率成份一个频率成份)值，运算量为值，运算量为例例 k=1 则要进行则要进行完成整个完成整个DFT运算，其计算量为：运算，其计算量为：

3、N次复数乘法次复数乘法+(N-1)次复数加法次复数加法N*N次复数相乘次复数相乘+N*(N-1)次复数加法次复数加法3.一次一次复数运算量换算成实数运算量复数运算量换算成实数运算量4次复数乘法2次实数加法复数运算要比实数运算复杂，需要的运算时间长。复数运算要比实数运算复杂，需要的运算时间长。一个复数乘法包括一个复数乘法包括4次实数次实数乘法乘法和和2次实数次实数加法加法。(a+jb)(c+jd)=(ac-bd)+j(bc+ad)一个复数加法包括一个复数加法包括2次实数次实数加法加法。(a+jb)+(c+jd)=(a+c)+j(b+d)2次实数加法4.计算计算DFT需要的实数运算量需要的实数运算

4、量由此看出：直接计算由此看出：直接计算DFT时，乘法次数与加法次数都时，乘法次数与加法次数都是和是和N2成比例的。当成比例的。当N很大时，所需工作量非常可观很大时，所需工作量非常可观。4N2次实数相乘和次实数相乘和2N(2N-1)次实数相加次实数相加.整个整个DFT实数运算量为：实数运算量为：N*N次复数乘次复数乘 + N*(N-1)次复数加次复数加整个整个DFT的复数运算量转换为实数运算量：的复数运算量转换为实数运算量：2* N*N次次实数加实数加4* N*N次次实数乘实数乘2* N*(N-1)次次实数加实数加2N(2N-1)次实数加次实数加例子例子例例1:当当N=1024点时，直接计算点时

5、，直接计算DFT需要：需要：这对实时性很强的信号处理这对实时性很强的信号处理(如雷达信号处理如雷达信号处理它对计算速度有十分苛刻的要求它对计算速度有十分苛刻的要求)来讲，迫切需要来讲，迫切需要改进改进DFT的计算方法，以减少总的运算次数。的计算方法，以减少总的运算次数。4*N2 = 4194304 次实数乘次实数乘2N(2N-1) = 4192256 次实数加次实数加(二二) 改善改善DFT运算效率的基本途径运算效率的基本途径基本思路：knNW利用利用DFT运算的系数运算的系数 的固有对称性和周期性，的固有对称性和周期性，改善改善DFT的运算效率。的运算效率。1.合并法：合并合并法：合并DFT

6、运算中的某些项。运算中的某些项。2. 分解法：将长序列分解法：将长序列DFT利用对称性和利用对称性和周期性，分解为短序列周期性，分解为短序列DFT。1. 利用利用DFT运算的系数运算的系数 的固有对称性和周的固有对称性和周期性，改善期性，改善DFT的运算效率的运算效率knNWknNW的共轭对称性：nkNknNWW*)(knNW的周期性：)()(kNnNkNnNknNWWW2、将长序列、将长序列DFT利用对称性和周期性分解利用对称性和周期性分解为短序列为短序列DFTDFT的运算量与的运算量与N2成正比成正比大点数大点数N的的DFT小点数小点数DFT的组合的组合分分解解减少运算工作量减少运算工作量

7、思路：思路：22)()()(NNNkXkXkX把把N点数据分成二半：点数据分成二半：其运算量为：其运算量为：2N再分二半：再分二半：44)()(NNkXkX44)()(NNkXkX2)2(N2)2(N+=22N2)4(N2)4(N2)4(N2)4(N+=24N这样一直分下去，剩下两点的变换。方法方法结论结论快速付里叶变换快速付里叶变换(FFT)就是在此特性基础上发展起来，就是在此特性基础上发展起来，并产生了多种并产生了多种FFT算法，其基本上可分成两大类：算法，其基本上可分成两大类：按按抽取方法抽取方法分：分： 时间抽取法时间抽取法(DIT);频率抽取法频率抽取法(DIF)按按“基数基数”分：

8、基分：基-2FFT算法；基算法；基-4FFT算算法；法； 混合基混合基FFT算法；分裂基算法；分裂基FFT算法算法其它其它方法：线性调频方法：线性调频Z变换变换(CZT法法)二、基二、基-2按时间抽取按时间抽取的的FFT算法算法(Coolkey-Tukey)（一）算法原理（一）算法原理 设设输入序列长度为输入序列长度为N=2M (M为正整数），将该为正整数），将该序列序列按时间顺序的奇偶分解按时间顺序的奇偶分解为越来越短的子序列，为越来越短的子序列，称为基称为基2按时间抽取的按时间抽取的FFT算法。也称为算法。也称为Coolkey-Tukey算法。算法。特别注意：特别注意：若不满足这个条件，可

9、以人为地加上若干零值若不满足这个条件，可以人为地加上若干零值（加零补长）使其达到（加零补长）使其达到 N=2M序列长度序列长度N必须满足必须满足 N=2M，M为整数为整数.(二二) 算法步骤算法步骤DFT变换：变换：10)()(NnknNWnxkX1,0Nk1.分组，变量置换先将先将x(n)按按n的奇偶分为两的奇偶分为两 组，作变量置换组，作变量置换:当当n=偶数时，令偶数时，令n=2r;当当n=奇数时，令奇数时，令n=2r+1;得到：得到：x(2r)=x1(r); x(2r+1)=x2(r); r=0N/2-1;1202212021120) 12(1202101010)()() 12()2(

10、)()()()(NrrkNkNNrrkNNrkrNNrrkNNnnknNNnnknNNnknNWrxWWrxWrxWrxWnxWnxWnxkX为奇数为偶数利用2/2/2222NNjNjNWeeW得2.分组序列分组序列的的DFT中中生成两个子序列12/012/02/2/2212/012/02/2/11) 12()()()2()()(NrNrrkNrkNNrNrrkNrkNWrxWrxkXWrxWrxkX其中：12/,.,2 , 1 , 0)()()()()(211202/21202/1NkkXWkXWrxWWrxkXkNNrrkNkNNrrkN12/, 2 , 1 , 0NkX1(k): 原序列

11、偶数项的原序列偶数项的DFTX2(k): 原序列奇数项的原序列奇数项的DFT3. 结论结论1)()()21kXWkXkXkN（ 再应用再应用W系数的周期性，求出用系数的周期性，求出用X1(k),X2(k)表达的表达的后半部的后半部的X(k+N/2)的值。的值。一个一个N点的点的DFT被分解为两个被分解为两个N/2点点DFT。12/1 , 0NkDFTN中的前半部分点又合成X1(k),X2(k)这两个这两个N/2点的点的DFT按照：按照：4.求出后半部的表示式求出后半部的表示式12/012/022/2)2/(2/2212/012/012/1)2/(2/11)2/(2/2/)()()()2()()

12、()()2(NrNrrkNkNrNNrNrrkNkNrNNkrNrkNkXWrxWrxkNXkXWrxWrxkNXWW看出：后半部的看出：后半部的k值所对应的值所对应的X1(k),X2(k)则完全重则完全重复了前半部分的复了前半部分的k值所对应的值所对应的X1(k),X2(k)的值。的值。)()()(212/)2/kXWkXkXWWWWkNkNkNNNkNN后半部分：又（5.结论结论2频域中的频域中的N个点频率成分为：个点频率成分为：)()()2/()()()(2121kXWkXNkXkXWkXkXkNkN后半部分：前半部分：只要求出（只要求出（0N/2-1）区间内的各个整数）区间内的各个整数

13、k值所值所对应的对应的X1(k),X2(k)值，即可以求出值，即可以求出(0N-1)整整个区间内全部个区间内全部X(k)值，这就是值，这就是FFT能大量节省能大量节省计算计算的关键。的关键。结论：结论：6.结论结论3由于N=2M，因此N/2仍为偶数，可以依照上面方法进一步把每个N/2点子序列，再按输入n的奇偶分解为两个N/4点的子序列，按这种方法不断划分下去，直到最后剩下的是2点DFT，两点DFT实际上只是加减运算加减运算。（三）蝶形结（三）蝶形结即蝶式计算结构即蝶式计算结构,或蝶式信号流图。或蝶式信号流图。X1(k)X2(k)kNW)()(21kXWkXkN)()(21kXWkXkN作图要素

14、：作图要素：(1)左入右出左入右出(2) 上加下减上加下减(3)系数标箭头系数标箭头 上面上面频域频域中前中前/后半部分表示式可以用蝶形后半部分表示式可以用蝶形信号流图表示如下。信号流图表示如下。例子例子)()() 2/()()()(2121kXWkXNkXkXWkXkXkNkN12/, 0Nk先将N=8DFT分解成2个4点DFT：可知：时域上时域上：x(0),x(2),x(4),x(6)为偶子序列 x(1),x(3),x(5),x(7)为奇子序列 频域上频域上：X(0)X(3)，由X(k)给出 X(4)X(7),由X(k+N/2)给出求求 N=23=8点点FFT变换变换解：（1）先按N=8-

15、N/2=4，做4点的DFT：将将N=8点分解成点分解成2个个4点的点的DFT的信号流图的信号流图 4点DFTx(0)x(2)x(4)x(6)4点DFTx(1)x(3)x(5)x(7)08W18W28W38WX(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)X1(0)X1(1)X1(2)X1(3)X2(0)X2(1)X2(2)X2(3)偶数序列奇数序列3821282118210821) 3 () 3 (3) 2() 2(2) 1 () 1 (1) 0() 0(0WXXXWXXXWXXXWXXX）（）（）（）（如：X(4)X(7)同学们自已写x1(r)x2(r)(2)N/2(4点点)

16、-N/4(2点点)FFT奇序列、偶序列、) 6() 2() 4() 0(: )(1xxxxrx奇序列、偶序列、同理：)7() 3 () 5 () 1 (: )(2xxxxrx 因为因为4点点DFT还是比较麻烦，所以再继续分解。还是比较麻烦，所以再继续分解。若将若将N/2(4点点)子序列按奇子序列按奇/偶分解成两个偶分解成两个N/4点（点（2点）点）子序列。即将子序列。即将x1(r)和和x2(r)分解成奇、偶两个分解成奇、偶两个N/4点点（2点）点的子序列。点）点的子序列。一个一个2点点的的DFT蝶形流图蝶形流图2点DFT2点DFTx(0)x(4)x(2)x(6)X3(0)X3(1)X4(0)X

17、4(1)X1(0)X1(1)X1(2)X1(3)04W14W) 1 () 1 () 1 () 0() 0() 2() 1 () 1 () 1 () 0() 0() 0(41431404314143140431XWXXXWXXXWXXXWXX其中另一个另一个2点的点的DFT蝶形流图蝶形流图2点DFT2点DFTx(1)x(5)x(3)x(7)X5(0)X5(1)X6(0)X6(1)X2(0)X2(1)X2(2)X2(3)04W14W) 1 () 1 () 1 () 0() 0() 2() 1 () 1 () 1 () 0() 0() 0(61452604526145260452XWXXXWXXXW

18、XXXWXX其中(3)将将N/4（2点）点）DFT再分解成再分解成2个个1点的点的DFT 最后剩下两点DFT,它可分解成两个一点DFT，但一点DFT就等于输入信号本身，所以两点DFT可用一个蝶形结表示。取x(0)、x(4)为例。2个个1点点的的DFT蝶形流图蝶形流图 1点DFTx(0)1点DFTx(4)X3(0)X3(1)02W进一步简化为蝶形流图：02WX3(0)X3(1)x(0)x(4)4()0()4()0() 1 ()4()0()4()0()0(023023xxxWxXxxxWxX其中：(4)一个完整一个完整N=8的按时间抽取的按时间抽取FFT的运算流图的运算流图 x(0)x(4)x(2

19、)x(6)x(1)x(5)x(3)x(7)38W28W18W08W08W08W08W08W08W08W28W28WX(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)12/0NNNWW其中旋转因子，共有m=0m=1m=2三、基三、基-2按频率抽取的按频率抽取的FFT算法算法 (DIF) (Sander-Tukey)(一一) 算法原理算法原理 设输入序列长度为设输入序列长度为N=2M(M为正整数，将该序列为正整数，将该序列的的频域的输出序列频域的输出序列X(k)(也是也是M点序列点序列)，按其，按其频域顺频域顺序的奇偶分解序的奇偶分解为越来越短的子序列，称为基为越来越短的子序列，称为

20、基2按频率按频率抽取的抽取的FFT算法。也称为算法。也称为Sander-Tukey算法。算法。基基-2按时间抽取的按时间抽取的FFT时域时域：按：按奇偶奇偶划分划分 频域频域：按：按前后前后划分划分基基-2按频率抽取的按频率抽取的FFT时域时域：按：按前后前后划分划分 频域频域：按：按奇偶奇偶划分划分例子例子nNWNnxnxnxNnxnxnx)2()()()2()()(21频域上：X(0),X(2),X(4),X(6)由x1(n)给出 X(1),X(3),X(5),X(7),由x2(n)给出求求 N=23=8点点DIF（1）先按N=8-N/2=4，做4点的DIF：将将N=8点分解成点分解成2个

21、个4点的点的DIF的信号流图的信号流图 4点DFTx(0)x(1)x(2)x(3)4点DFTx(4)x(5)x(6)x(7)X(0)X(2)X(4)X(6)X(1)X(3)X(5)X(7)X1(k)前半部分序列后半部分序列nNnNnNnNWxxxWxxxWxxxWxxxxxxxxxxxxxxx)7()3(3,)6()2(2,)5() 1 (1,)4()0(0)7()3(3),6()2(2),5() 1 (1),4()0(022221111）（）（）（）（）（）（）（）（如：08W18W28W38Wx1(n)x2(n)X2(k)(4)一个完整一个完整N=8的按频率抽取的按频率抽取FFT的运算流图

22、的运算流图 x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)38W28W18W08W08W08W08W08W08W08W28W28WX(0)X(4)X(2)X(6)X(1)X(5)X(3)X(7)12/0NNNWW其中旋转因子，共有m=0m=1m=2DIF与与DIT比较比较算法是两种等价的与次复加次复乘FFTDITDIFNaNmNFNF22lglg2相同之处：相同之处：（1）DIF与与DIT两种算法均为原位运算。两种算法均为原位运算。（2）DIF与与DIT运算量相同。运算量相同。它们都需要它们都需要不同之处：不同之处：（1）DIF与与DIT两种算法结构倒过来。两种算法结构倒过来。DIF为输入顺序，输出乱序。运算完毕再运行为输入顺序，输出乱序。运算完毕再运行“二进制倒读二进制倒读”程序。程序。DIT为输入乱序，输出顺序。先运行为输入乱序，输出顺序。先运行“二进制二进制倒读倒读”程序，再进行求程序，再进行求DFT。（2）DIF与与DIT根本区别：在于蝶形结不同。根本区别：在于蝶形结不同。DIT的复数相乘出现在减法之前。的复数相乘出现在减法之前。DIF的复数相乘出现在减法之后。的复数相乘出现在减法之后。