第五章-快速傅里叶变换(FFT)(数字信号处理)课件.ppt_163文库

2、长度为N的有限长序列x(n)的DFT为考虑x(n)为复数序列的一般情况，对某一个k值，直接按(5.2.1)式计算X(k)值需要N次复数乘法、(N-1)次复数加法。10()(),0,1,1NknNnX kx n WkN(5.2.1)第五章第五章快速傅里叶变换快速傅里叶变换(FFT)如前所述，N点DFT的复乘次数等于N2。显然，把N点DFT分解为几个较短的DFT，可使乘法次数大大减少。另外，旋转因子WmN具有明显的周期性和对称性。其周期性表现为22()jm lNjmm lNmNNNNWeeW(5.2.2)其对称性表现为2mN mN mmNNNNNmmNNWWWWWW 或者第五章第五章快速傅

3、里叶变换快速傅里叶变换(FFT)niNinNWW第五章第五章快速傅里叶变换快速傅里叶变换(FFT)5.2.2 时域抽取法基2FFT基本原理 F F T 算法基本上分为两大类：时域抽取法FFT(Decimation In Time FFT,简称DIT-FFT)和频域抽取法FFT(Decimation In Frequency FFT,简称DIFFFT)。下面先介绍DIFFFT算法。设序列x(n)的长度为N，且满足2,MNM为自然数按n的奇偶性将x(n)分解为两个N/2点的子序列12()(2),0,1,12()(21),0,1,12Nx rxrrNx rxrr第五章第

4、五章快速傅里叶变换快速傅里叶变换(FFT)则x(n)的DFT为由于所以/2 1/2 11/22/21200()()()()()NNkrkkrkNNNNrrX kx r WWx r WX kW Xk第五章第五章快速傅里叶变换快速傅里叶变换(FFT)其中X1(k)和X2(k)分别为x1(r)和x2(r)的N/2点DFT，即/2 111/210/2 122/220()()()()()()NkrNrNkrNrX kx r WDFT x rXkx r WDFT x r(5.2.5)(5.2.6)由于X1(k)和X2(k)均以N/2为周期，且，所以X(k)又可表示为2NkkNNWW 1212()()

5、()0,1,12()()()0,1,122kNkNNX kX kW XkkNNX kX kW Xkk(5.2.7)(5.2.8)第五章第五章快速傅里叶变换快速傅里叶变换(FFT)图5.2.1 蝶形运算符号 CABA BCA BC第五章第五章快速傅里叶变换快速傅里叶变换(FFT)图5.2.2 N点DFT的一次时域抽取分解图(N=8)N/2点DFTWN0N/2点DFTWN1WN2WN3x(0)X1(0)x(2)x(4)x(6)x(1)x(3)x(5)x(7)X1(1)X1(2)X1(3)X2(0)X2(1)X2(2)X2(3)X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)第五

6、章第五章快速傅里叶变换快速傅里叶变换(FFT)与第一次分解相同，将x1(r)按奇偶分解成两个N/4长的子序列x3(l)和x4(l)，即3241()(2),0,1,1()(21)4x lxlNlx lxl那么，X1(k)又可表示为/4 1/4 12(21)11/21/200/4 1/4 13/4/24/4003/24()(2)(21)()()()(),0,1,/21NNklklNNiiNNklkklNNNiikNX kxl WxlWx l WWx l Wx kWXk kN(5.2.9)第五章第五章快速傅里叶变换快速傅里叶变换(FFT)式中/4 133/430/4 144/440()()()(

7、)()()NklNiNklNix kx l WDFT x lx kx l WDFT x l 同理，由X3(k)和X4(k)的周期性和Wm N/2的对称性 Wk+N/4 N/2=-Wk N/2 最后得到：13/2413/24()()(),0,1,/41(/4)()()kNkNX kXkWXkkNX kNXkWXk(5.2.10)第五章第五章快速傅里叶变换快速傅里叶变换(FFT)用同样的方法可计算出25/2625/26()()(),0,1,/41(/4)()kNkNXkXkWXkkNXkNX kWXk(5.2.11)其中/4 155/450/4 166/4605262()()()()()()()

8、(2),0,1,/41()(21)NklNiNklNiXkx l WDFT x lXkx l WDFT x lx lxllNx lxl第五章第五章快速傅里叶变换快速傅里叶变换(FFT)图5.2.3 N点DFT的第二次时域抽取分解图(N=8)N/4点DFTWN12WN12WN0WN1WN2WN3X1(0)X1(1)X1(2)X1(3)X2(0)X2(1)X2(2)X2(3)X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)x(0)X3(0)X3(1)X4(0)X4(1)x(4)x(2)x(6)x(1)x(5)x(3)x(7)N/4点DFTN/4点DFTN/4点DFTWN02WN0

9、2第五章第五章快速傅里叶变换快速傅里叶变换(FFT)图5.2.4 N点DITFFT运算流图(N=8)WN0WN1WN2WN3WN0WN2WN0WN2WN0WN0WN0WN0 x(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)A(0)A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(0)A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(0)A(7)X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)A(0)A(1)A(2)A(3)A(4)A(5)A(6)A(7)第五章第五章快速傅里叶变换快速傅里叶变换(FFT)5.2.3 DITFFT算法与直接计

10、算DFT运算量的比较每一级运算都需要N/2次复数乘和N次复数加(每个蝶形需要两次复数加法)。所以，M级运算总共需要的复数乘次数为22(2)log22(2)logMANNCMNCN MNN复数加次数为例如，N=210=1024时221048576204.8(/2)log5120NNN第五章第五章快速傅里叶变换快速傅里叶变换(FFT)图5.2.5 FFT算法与直接计算DFT所需乘法次数的比较曲线第五章第五章快速傅里叶变换快速傅里叶变换(FFT)5.2.4 DITFFT的运算规律及编程思想 1.原位计算由图5.2.4可以看出，DITFFT的运算过程很有规律。N=2M点的FFT共进行M级运

11、算，每级由N/2个蝶形运算组成。2.旋转因子的变化规律如上所述，N点DITFFT运算流图中，每级都有N/2个蝶形。每个蝶形都要乘以因子WpN，称其为旋转因子，p称为旋转因子的指数。第五章第五章快速傅里叶变换快速傅里叶变换(FFT)观察图5.2.4不难发现，第L级共有2 L-1个不同的旋转因子。N=23=8时的各级旋转因子表示如下：L=1时，WpN=WJ N/4=WJ2L，J=0 L=2时，WpN=WJ N/2=WJ2L，J=0，1 L=3时，WpN=WJN=WJ2L，J=0，1，2，3 对N=2M的一般情况，第L级的旋转因子为12212,0,1,2,212222,0,1,2,212MLL

12、MpJLNLML ML MPJJLNNNMLWW L JNWWWJpJ(5.2.12)(5.2.13)第五章第五章快速傅里叶变换快速傅里叶变换(FFT)3.蝶形运算规律设序列x(n)经时域抽选(倒序)后，存入数组X中。如果蝶形运算的两个输入数据相距B个点，应用原位计算，则蝶形运算可表示成如下形式：X(J)XL-1(J)+X L-1(J+B)WpN XL(J+B)XL-1(J)-X L-1(J+B)WpN 式中 p=J2 M-L；J=0,1,，2 L-1-1；L=1,2,，M第五章第五章快速傅里叶变换快速傅里叶变换(FFT)下标L表示第L级运算，XL(J)则表示第L级运算后数组元素X(J)

13、的值。如果要用实数运算完成上述蝶形运算，可按下面的算法进行。设 T=X L-1(J+B)WpN=TR+jTI X L-1(J)=XR(J)+jXI(J)式中下标R表示取实部，I表示取虚部，22()cos()sin22()cos()sinRRRIIIRITXJBpXJBpNNTXJBpXJBpNN第五章第五章快速傅里叶变换快速傅里叶变换(FFT)()()()()()()()()()()()LRRRRIIIRRRIIIXJXJj JXJXJTXJXJTXJBXJTXJBXJT则第五章第五章快速傅里叶变换快速傅里叶变换(FFT)4.编程思想及程序框图图5.2.6 DITFFT运算和程序框图开

14、始送入x(n)，MN2 M倒序L1,M0,B 1P2 M LJk J,N1,2LpNpNWBkXkXBkXWBkXkXkX)()()()()()(输出结束B 2 L1第五章第五章快速傅里叶变换快速傅里叶变换(FFT)5.序列的倒序 DITFFT算法的输入序列的排序看起来似乎很乱，但仔细分析就会发现这种倒序是很有规律的。由于N=2M，所以顺序数可用M位二进制数(nM-1nM-2n1n0)表示。图5.2.7 形成倒序的树状图(N=23)01010101010101(n2n1n0)200004261537100010110001101011111第五章第五章快速傅里叶变换快速傅里叶变换(

15、FFT)表5.2.1 顺序和倒序二进制数对照表第五章第五章快速傅里叶变换快速傅里叶变换(FFT)图5.2.8 倒序规律 x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)A(0)A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(0)A(1)A(2)A(3)A(4)A(5)A(6)A(7)x(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)第五章第五章快速傅里叶变换快速傅里叶变换(FFT)图5.2.9 倒序程序框图 221NNLHJNLHI1,N1I JTJAJXIAIXT)()()()(J KLHK KJJ2KKKJJNNY第五章第五章快速傅里叶变换

16、快速傅里叶变换(FFT)5.2.5 频域抽取法FFT(DIFFFT)在基2快速算法中，频域抽取法FFT也是一种常用的快速算法，简称DIFFFT。设序列x(n)长度为N=2M，首先将x(n)前后对半分开，得到两个子序列，其DFT可表示为如下形式：10/2 110/2/2 1/2 1(/2)00/2 1/20()()()()()()()2()()2NkNnNNknknNNnn NNNknk n NNNnnNkNknNNnX kDFT x nx n Wx n Wx n WNx n Wx nWNx nWx nW第五章第五章快速傅里叶变换快速傅里叶变换(FFT)/21,(1)1kNkNkWk 偶数奇

17、数将X(k)分解成偶数组与奇数组，当k取偶数(k=2r,r=0,1,N/2-1)时/2 120/2 12/20(2)()()2()()2NrnNnNrnNnNXrx nx nWNx nx nW(5.2.14)第五章第五章快速傅里叶变换快速傅里叶变换(FFT)当k取奇数(k=2r+1,r=0,1,N/2-1)时/2 1(21)0/2 1/20(21)()()2()()2NnrNnNnnrNNnNXrx nx nWNx nx nWW(5.2.15)将x1(n)和x2(n)分别代入(5.2.14)和(5.2.15)式，可得/2 11/20/2 12/20(2)()(21)()NrnNnNrnNn

18、Xrx n WXrx n W(5.2.16)第五章第五章快速傅里叶变换快速傅里叶变换(FFT)图5.2.10 DIFFFT蝶形运算流图符号第五章第五章快速傅里叶变换快速傅里叶变换(FFT)图5.2.11 DIFFFT一次分解运算流图(N=8)N/2点DFTWN0N/2点DFTWN1WN2WN3X(0)x1(0)X(2)X(4)X(6)X(1)X(3)X(5)X(7)x1(1)x1(2)x1(3)x2(0)x2(1)x2(2)x2(3)x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)第五章第五章快速傅里叶变换快速傅里叶变换(FFT)图5.2.12 DIFFFT二次分解运算

19、流图(N=8)N/4点DFTWN0WN1WN2WN3x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)X(0)X(4)X(2)X(6)X(1)X(5)X(3)X(7)WN0WN2WN0WN2N/4点DFTN/4点DFTN/4点DFT第五章第五章快速傅里叶变换快速傅里叶变换(FFT)图5.2.13 DIFFFT运算流图(N=8)WN0WN1WN2WN3WN0WN2WN0WN2WN0WN0WN0WN0X(0)X(4)X(2)X(6)X(1)X(5)X(3)X(7)x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)第五章第五章快速傅里叶变换快速傅里叶变换(FFT)图5

20、.2.14 DITFFT的一种变形运算流图WN0WN0WN2WN0X(0)X(4)X(2)X(6)X(1)X(5)X(3)X(7)x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)WN0WN2WN1WN3WN2WN0WN0WN0第五章第五章快速傅里叶变换快速傅里叶变换(FFT)图5.2.15 DITFFT的一种变形运算流图WN0WN0WN2WN0X(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)WN0WN2WN1WN3WN2WN0WN0WN0第五章第五章快速傅里叶变换快速傅里叶变换(FFT)5.2.

21、6 IDFT的高效算法上述FFT算法流图也可以用于离散傅里叶逆变换(Inverse Discrete Fourier Transform，简称IDFT)。比较DFT和IDFT的运算公式：1010()()()1()()()NkNnNknNkX kDFT x nx n Wx nIDFT x nX k WN第五章第五章快速傅里叶变换快速傅里叶变换(FFT)图5.2.16 DITIFFT运算流图 WN0WN1WN2WN3WN0WN0N1x(0)x(4)x(2)x(6)x(4)x(5)x(3)x(7)X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)WN2WN2N1N1N1N1N1N1

22、N1第五章第五章快速傅里叶变换快速傅里叶变换(FFT)图5.2.17 DITIFFT运算流图(防止溢出)WN02121x(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)212121WN121WN221WN3212121WN021WN2212121WN021WN22121WN02121WN0212121WN021WN021第五章第五章快速傅里叶变换快速傅里叶变换(FFT)如果希望直接调用FFT子程序计算IFFT，则可用下面的方法：由于 10101()()1()()NknNkNknNkx nX k WNx nXk W

23、N对上式两边同时取共轭，得1011()()()NknNkx nXk WDFT XkNN第五章第五章快速傅里叶变换快速傅里叶变换(FFT)5.3 进一步减少运算量的措施进一步减少运算量的措施 5.3.1 多类蝶形单元运算由DITFFT运算流图已得出结论，N=2M点FFT共需要MN/2次复数乘法。由(5.2.12)式，当L=1时，只有一种旋转因子W0N=1，所以，第一级不需要乘法运算。第五章第五章快速傅里叶变换快速傅里叶变换(FFT)综上所述，先除去第一、二两级后，所需复数乘法次数应是从L=3至L=M共减少复数乘法次数为(2)(2)2MNCM(5.3.1)13312()2222MMLLLL

24、NNN(5.3.2)因此，DITFFT的复乘次数降至(2)(2)(2)(3)2222MNNNCMM(5.3.3)第五章第五章快速傅里叶变换快速傅里叶变换(FFT)22(1)()()222()()22()222()()22defjxjyxjyjxyxyj xyRjIRxyIxyyx 第五章第五章快速傅里叶变换快速傅里叶变换(FFT)从实数运算考虑，计算N=2M点DITFFT所需实数乘法次数为(2)4(3)2(2)2213(2)102MNNRMNM(5.3.4)第五章第五章快速傅里叶变换快速傅里叶变换(FFT)5.3.2 旋转因子的生成在FFT运算中，旋转因子WmN=cos(2m/N)-j

25、sin(2m/N)，求正弦和余弦函数值的计算量是很大的。第五章第五章快速傅里叶变换快速傅里叶变换(FFT)5.3.3 实序列的FFT算法设x(n)为N点实序列，取x(n)的偶数点和奇数点分别作为新构造序列y(n)的实部和虚部，即1212()(2),()(21),0,1,12()()(),0,1,12Nx nxn x nxnnNy nx njx n n对y(n)进行N/2点FFT，输出Y(k)，则1122()()(),0,1,1()()()2epopX kDFT x nYkNkXkDFT x njYk 根据DITFFT的思想及式(5.2.7)和(5.2.8)，可得到 12()()(),0,1

26、,2kNNX kX kW Xk k第五章第五章快速傅里叶变换快速傅里叶变换(FFT)由于x(n)为实序列，所以X(k)具有共轭对称性，X(k)的另外N/2点的值为()(),1,2,12NX NkXk k第五章第五章快速傅里叶变换快速傅里叶变换(FFT)5.4 分裂基分裂基FFT算法算法 5.5.1 分裂基FFT算法原理当n=pq，且p=N/4，q=4时，n可表示为101010,03,0144NNnpnnnnnn并有 10110/4 13()41000()()()4NknNnNNknnNnnX kx n WNxnn W 第五章第五章快速傅里叶变换快速傅里叶变换(FFT)010100/4

27、13104/4 1024040403304()4()()()423()4NknknNnnNkknknkkNNNWxnn WNNx n Wx nWx nWNx nW WW再将上式中的k表示为10104,01,034Nkkkkk第五章第五章快速傅里叶变换快速傅里叶变换(FFT)可得 1001010100000010010/4 1(4)0040823(4)(4)0404/4 120040403(4)04()(4)()()43()()24()()()423()4NkknkkkkknNNkknkkknNX kXkkNx nx nWNNx nWx nWWNNx nx nWx nWNx nWW 对k0=0

28、，1,2,3,并用k表示k1，用n表示n0，可以写出第五章第五章快速傅里叶变换快速傅里叶变换(FFT)/4 140/4 140/4 14203(4)()()()()4243(41)()()()()4243(42)()()()()424(43)()()()(42NknNnNkn nNnNknnNnNNNXkx nx nx nx nWNNNXkx njx nx njx nWNNNXkx nx nx nx nWNNXkx njx nx njx n/4 14303)4014NknnNnNWNk(5.5.1)第五章第五章快速傅里叶变换快速傅里叶变换(FFT)/2 120/4 140/4 1340(2

29、)()(),01223(41)()()()()4240143(43)()()()()424014NknNnNnknNNnNnknNNnNNXkx nx nWkNNNXkx njx nx njx nWWNkNNNXkx njx nx njx nWWNk(5.5.2)第五章第五章快速傅里叶变换快速傅里叶变换(FFT)214234()()(),01223()()()()()4243()()()()()424014nNnNNNx nx nx nnNNNx nx njx nx njx nWNNNxnx njx nx njx nWNn(5.5.3)令第五章第五章快速傅里叶变换快速傅里叶变换(FFT)

30、则(5.5.2)式可写成如下更简明的形式：/2 12220/4 1141440/4 1242440(2)()(),012(41)()(),014(43)()(),014NknNnNknNnNknNnNXkx n WDFT x nkNXkxn WDFT x nkNXkxn WDFT xnk(5.4.4)第五章第五章快速傅里叶变换快速傅里叶变换(FFT)图5.5.1 分裂基第一次分解L形流图点DFT 点DFT 点DFTx2(1)x2(1 N/4)2N4N4N)1(14x)1(24x1NW3NWx(1)41Nx21Nx431Nx 1 1 1 j第五章第五章快速傅里叶变换快速傅里叶变换(FFT)

31、例如，N=16，第一次抽选分解时，由式(5.5.3)得 x2(n)=x(n)+x(n+8),0n7x14(n)=x(n)-x(n+8)-jx(n+4)-x(n+12)Wn16,0n3x24(n)=x(n)-x(n+8)+jx(n+4)-x(n+12)W3n16,0n3 把上式代入式(5.4.4)，可得 X(2k)=DFTx2(n),0k7 X(4k+1)=DFTx14(n),0k3 X(4k+3)=DFTx24(n),0k3 第五章第五章快速傅里叶变换快速傅里叶变换(FFT)图5.5.2 分裂基FFT算法L形排列示意图与结构示意图(a)分裂基FFT算法L形排列示意图；(b)分裂基FFT算法运

32、算流图结构示意图(a)(b)第五章第五章快速傅里叶变换快速傅里叶变换(FFT)图5.5.3 16点分裂基第一次分解L形流图(图中省去箭头)(8)点DFTx2(0)x2(1)x2(2)x2(3)x2(4)x2(5)x2(6)x2(7)点DFT点DFT)0(14x)1(14x)2(14x)3(14x)0(24x)1(24x)2(24x)3(24x44N44N2Nx(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)x(8)x(9)x(10)x(11)x(12)x(13)x(14)x(15)0NW1NW3NW2NW0NW3NW6NW j j jX(0)X(1)X(2)X(3)X(4)X(

33、5)X(6)X(7)X(8)X(9)X(10)X(11)X(12)X(13)X(14)X(15)X(2k)X(4k1)X(4k3)1111111111第五章第五章快速傅里叶变换快速傅里叶变换(FFT)第二次分解：先对图5.5.3中N/2点DFT进行分解。令X1(l)=X(2l)，则有 X1(2l)=DFTy2(n),0l3 X1(4l+1)=DFTy14(n),0l1 X1(4l+3)=DFTy24(n),0l1 第五章第五章快速傅里叶变换快速傅里叶变换(FFT)其中y2(n)=x2(n)+x2(n+4),0n3y14(n)=x2(n)-x2(n+4)-x2(n+2)x(n+6)Wn8,n

34、=0,1y24(n)=x2(n)-x2(n+4)+jx2(n+2)x2(n+6)W3n8,n=0,1第五章第五章快速傅里叶变换快速傅里叶变换(FFT)图5.4.4 图5.4.4中N/2点DFT的分解L形流图(4)点DFTx2(0)x2(1)x2(2)x2(3)x2(4)x2(5)x2(6)x2(7)y2(0)y2(1)y2(2)y2(3)X1(0)X(0)X1(2)X(4)X1(4)X(8)X1(6)X(12)X1(1)X(2)X1(5)X(10)X1(3)X(6)X1(7)X(14)X1(2l)X1(4l1)X1(4l3)4N)0(14y)1(14y)1(24y)0(24y12NW32NW

35、 j j11111111第五章第五章快速傅里叶变换快速傅里叶变换(FFT)图5.5.5 4点分裂基L形运算流图 v(0)v(1)v(2)v(3)V(0)V(2)V(1)V(3)j1111第五章第五章快速傅里叶变换快速傅里叶变换(FFT)图5.4.6 16点分裂基FFT运算流图 x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)x(8)x(9)x(10)x(11)x(12)x(13)x(14)x(15)X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)X(8)X(9)X(10)X(11)X(12)X(13)X(14)X(15)j1111 j j1111 j j11

36、1111111111 j j j jW 1W 2W 3W 3W 6W 9W 2W 6111111111111NNNNNNNN第五章第五章快速傅里叶变换快速傅里叶变换(FFT)5.5.2 分裂基FFT算法的运算量设第j级有lj个L形，j=1,2,M-1,M=log2N，则有l1=N/4。由图5.5.2(b)可见，第j-1列中的L形包含了第j列中的一部分结点的计算，即空白部分，所占结点数刚好等于第j-1列中所有L形对应结点的一半，所以第j列L形个数就减少l j-1/2个，即第五章第五章快速傅里叶变换快速傅里叶变换(FFT)111223104241(1)424211(1)42424111()(1)42424jjjijjilNlNlNlNlNlNlNNl第五章第五章快速傅里叶变换快速傅里叶变换(FFT)由于每个L形有两次复(数)乘运算，所以全部复乘次数为1122212()3332122log(1)399MMMjjMNClMNNN(5.5.5)

展开阅读全文