数字信号处理第4章-快速傅里叶变换(FFT)-课件.ppt

1、第第4章章 快速傅里叶变换快速傅里叶变换(FFT)第第4章章 快速傅里叶变换快速傅里叶变换(FFT)4.1 引言引言4.2 基基2FFT算法算法4.3 进一步减少运算量的措施进一步减少运算量的措施4.4 分裂基分裂基FFT算法算法4.5 离散哈特莱变换离散哈特莱变换(DHT)1第第4章章 快速傅里叶变换快速傅里叶变换(FFT)4.1 引言引言 DFT是信号分析与处理中的一种重要变换。因直接计算DFT的计算量与变换区间长度N的平方成正比，当N较大时，计算量太大，所以在快速傅里叶变换(简称FFT)出现以前，直接用DFT算法进行谱分析和信号的实时处理是不切实际的。直到1965年发现了DFT的一种快速

2、算法以后，情况才发生了根本的变化。2第第4章章 快速傅里叶变换快速傅里叶变换(FFT)4.2 基基2FFT算法算法 4.2.1 直接计算DFT的特点及减少运算量的基本途径 长度为N的有限长序列x(n)的DFT为 考虑x(n)为复数序列的一般情况，对某一个k值，直接按(4.2.1)式计算X(k)值需要N次复数乘法、(N-1)次复数加法。10()(),0,1,1NknNnX kx n WkN(4.2.1)3第第4章章 快速傅里叶变换快速傅里叶变换(FFT)如前所述，N点DFT的复乘次数等于N2。显然，把N点DFT分解为几个较短的DFT，可使乘法次数大大减少。另外，旋转因子WmN具有明显的周期性和对

3、称性。其周期性表现为22()jm lNjmm lNmNNNNWeeW(4.2.2)其对称性表现为2mN mN mmNNNNNmmNNWWWWWW 或者 4第第4章章 快速傅里叶变换快速傅里叶变换(FFT)4.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/

4、2点的子序列12()(2),0,1,12()(21),0,1,12Nx rxrrNx rxrr5第第4章章 快速傅里叶变换快速傅里叶变换(FFT)则x(n)的DFT为/2 1/2 12(21)00/2 1/2 121200()()()(2)(21)()()knknNNnnNNkrkrNNrrNNkkrNNrrX kx n Wx n Wxr WxrWx rWx r W由于222222/2jkrNjkrkrkrNNNWeeW所以/2 1/2 11/22/21200()()()()()NNkrkkrkNNNNrrX kx r WWx r WX kW Xk6第第4章章 快速傅里叶变换快速傅里叶变换(F

5、FT)其中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(4.2.5)(4.2.6)由于X1(k)和X2(k)均以N/2为周期，且所以X(k)又可表示为前后对半分开两部分2NkkNNWW 1212()()()0,1,12()()()0,1,122kNkNNX kX kW XkkNNX kX kW Xkk(4.2.7)(4.2.8)7第第4章章 快速傅里叶变换快速傅里叶变换(FFT)图4.2.1 蝶形运算符号 CABA BCA BC

6、8第第4章章 快速傅里叶变换快速傅里叶变换(FFT)图4.2.2 N点DFT的一次时域抽取分解图(N=8)N/2点DFTN/2点DFTx(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)9第第4章章 快速傅里叶变换快速傅里叶变换(FFT)二次分解：与第一次分解相同，将x1(r)按奇偶分解成两个N/4长的子序列x3(l)和x4(l)，即3241()(2),0,1,1()(21)4x lxlNlx lxl那么，X1(k)又可表示为/4 1/4

7、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(4.2.9)10第第4章章 快速傅里叶变换快速傅里叶变换(FFT)式中/4 133/430/4 144/440()()()()()()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

8、,/41(/4)()()kNkNX kXkWXkkNX kNXkWXk(4.2.10)11第第4章章 快速傅里叶变换快速傅里叶变换(FFT)用同样的方法可计算出25/2625/26()()(),0,1,/41(/4)()kNkNXkXkWXkkNXkNX kWXk(4.2.11)其中/4 155/450/4 166/4605262()()()()()()()(2),0,1,/41()(21)NklNiNklNiXkx l WDFT x lXkx l WDFT x lx lxllNx lxl12第第4章章 快速傅里叶变换快速傅里叶变换(FFT)图4.2.3 N点DFT的第二次时域抽取分解图(N=

9、8)N/4点DFTX1(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点DFT13第第4章章 快速傅里叶变换快速傅里叶变换(FFT)图4.2.4 N点DITFFT运算流图(N=8)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

10、)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)14第第4章章 快速傅里叶变换快速傅里叶变换(FFT)4.2.3 DITFFT算法与直接计算DFT运算量的比较 每一级运算都需要N/2次复数乘和N次复数加(每个蝶形需要两次复数加法)。所以，M级运算总共需要的复数乘次数为22(2)log22(2)logMANNCMNCN MNN复数加次数为 例如，N=210=1024时221048576204.8(/2)log5120NNN15第第4章章 快速傅里叶变换快速傅里叶变换(FFT)图4.2.5 FFT算法

11、与直接计算DFT所需乘法次数的比较曲线 16第第4章章 快速傅里叶变换快速傅里叶变换(FFT)4.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 nW17第第4章章 快速傅

12、里叶变换快速傅里叶变换(FFT)/21,(1)1kNkNkWk 偶数 奇数 X(k)分解成偶数组与奇数组，当k取偶数k=2r,r=0,1,N/2-1时/2 120/2 12/20(2)()()2()()2NrnNnNrnNnNXrx nx nWNx nx nW(4.2.14)18第第4章章 快速傅里叶变换快速傅里叶变换(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(4.2.15)将x1(n)和x2(n)分别代入(4.2.14)和(4.2.15)式，可得/2

13、11/20/2 12/20(2)()(21)()NrnNnNrnNnXrx n WXrx n W(4.2.16)19第第4章章 快速傅里叶变换快速傅里叶变换(FFT)图4.2.10 DIFFFT蝶形运算流图符号 20第第4章章 快速傅里叶变换快速傅里叶变换(FFT)图4.2.11 DIFFFT一次分解运算流图(N=8)N/2点DFTN/2点DFTX(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)21第第4章章 快速傅里叶变换快速傅里叶变换

14、(FFT)图4.2.12 DIFFFT二次分解运算流图(N=8)N/4点DFTx(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)N/4点DFTN/4点DFTN/4点DFT22第第4章章 快速傅里叶变换快速傅里叶变换(FFT)图4.2.13 DIFFFT运算流图(N=8)X(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)23第第4章章 快速傅里叶变换快速傅里叶变换(FFT)图4.2.14 DITFFT的一种变形运算流图X(0)X(4)X(2)

15、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)24第第4章章 快速傅里叶变换快速傅里叶变换(FFT)图4.2.15 DITFFT的一种变形运算流图X(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)25第第4章章 快速傅里叶变换快速傅里叶变换(FFT)4.2.6 IDFT的高效算法 上述FFT算法流图也可以用于离散傅里叶逆变换(Inverse Discrete Fourier Transform，简称IDFT)。比较DFT和IDFT的运算公式：1010()()(

16、)1()()()NkNnNknNkX kDFT x nx n Wx nIDFT x nX k WN26第第4章章 快速傅里叶变换快速傅里叶变换(FFT)如果希望直接调用FFT子程序计算IFFT，则可用下面的方法：由于 10101()()1()()NknNkNknNkx nX k WNx nXk WN对上式两边同时取共轭，得1011()()()NknNkx nXk WDFT XkNN27第第4章章 快速傅里叶变换快速傅里叶变换(FFT)4.3 进一步减少运算量的措施进一步减少运算量的措施 4.3.1 多类蝶形单元运算 由DITFFT运算流图已得出结论，N=2M点FFT共需要MN/2次复数乘法。由

17、(4.2.12)式，当L=1时，只有一种旋转因子W0N=1，所以，第一级不需要乘法运算。28第第4章章 快速傅里叶变换快速傅里叶变换(FFT)综上所述，先除去第一、二两级后，所需复数乘法次数应是 从L=3至L=M共减少复数乘法次数为(2)(2)2MNCM(4.3.1)13312()2222MMLLLLNNN(4.3.2)因此，DITFFT的复乘次数降至(2)(2)(2)(3)2222MNNNCMM(4.3.3)29第第4章章 快速傅里叶变换快速傅里叶变换(FFT)22(1)()()222()()22()222()()22defjxjyxjyjxyxyj xyRjIRxyIxyyx 30第第4章

18、章 快速傅里叶变换快速傅里叶变换(FFT)从实数运算考虑，计算N=2M点DITFFT所需实数乘法次数为(2)4(3)2(2)2213(2)102MNNRMNM(4.3.4)31第第4章章 快速傅里叶变换快速傅里叶变换(FFT)4.3.2 旋转因子的生成 在FFT运算中，旋转因子WmN=cos(2m/N)-jsin(2m/N)，求正弦和余弦函数值的计算量是很大的。32第第4章章 快速傅里叶变换快速傅里叶变换(FFT)4.3.3 实序列的FFT算法 设x(n)为N点实序列，取x(n)的偶数点和奇数点分别作为新构造序列y(n)的实部和虚部，即1212()(2),()(21),0,1,12()()()

19、,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的思想及式(4.2.7)和(4.2.8)，可得到 12()()(),0,1,2kNNX kX kW Xk k33第第4章章 快速傅里叶变换快速傅里叶变换(FFT)由于x(n)为实序列，所以X(k)具有共轭对称性，X(k)的另外N/2点的值为()(),1,2,12NX NkXk k34第第4章章 快速傅里叶变换快速傅里叶变换(FFT)4.4 分裂基分裂基FFT算法

20、算法 4.4.1 分裂基FFT算法原理 当n=pq，且p=N/4，q=4时，n可表示为101010,03,0144NNnpnnnnnn并有 10110/4 13()41000()()()4NknNnNNknnNnnX kx n WNxnn W 35第第4章章 快速傅里叶变换快速傅里叶变换(FFT)010100/4 13104/4 1024040403304()4()()()423()4NknknNnnNkknknkkNNNWxnn WNNx n Wx nWx nWNx nW WW再将上式中的k表示为10104,01,034Nkkkkk36第第4章章 快速傅里叶变换快速傅里叶变换(FFT)可得

21、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,1,2,3,并用k表示k1，用n表示n0，可以写出37第第4章章 快速傅里叶变换快速傅里叶变换(FFT)/4 140/4 140/4 14203(4)()()()()4243(41)()()()()4243(42)()()()()424(43)()()()(42NknNnNkn

22、nNnNknnNnNNNXkx nx nx nx nWNNNXkx njx nx njx nWNNNXkx nx nx nx nWNNXkx njx nx njx n/4 14303)4014NknnNnNWNk(4.4.1)38第第4章章 快速傅里叶变换快速傅里叶变换(FFT)/2 120/4 140/4 1340(2)()(),01223(41)()()()()4240143(43)()()()()424014NknNnNnknNNnNnknNNnNNXkx nx nWkNNNXkx njx nx njx nWWNkNNNXkx njx nx njx nWWNk(4.4.2)39第第4章章

23、 快速傅里叶变换快速傅里叶变换(FFT)214234()()(),01223()()()()()4243()()()()()424014nNnNNNx nx nx nnNNNx nx njx nx njx nWNNNxnx njx nx njx nWNn(4.4.3)令 40第第4章章 快速傅里叶变换快速傅里叶变换(FFT)则(4.4.2)式可写成如下更简明的形式：/2 12220/4 1141440/4 1242440(2)()(),012(41)()(),014(43)()(),014NknNnNknNnNknNnNXkx n WDFT x nkNXkxn WDFT x nkNXkxn W

24、DFT xnk(4.4.4)41第第4章章 快速傅里叶变换快速傅里叶变换(FFT)图4.4.1 分裂基第一次分解L形流图 点DFT 点DFT 点DFTx2(1)x2(1 N/4)x(1)1 1 1 j42第第4章章 快速傅里叶变换快速傅里叶变换(FFT)例如，N=16，第一次抽选分解时，由式(4.4.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 把上式代入式(4.4.4)，可得 X(2k)=DFTx2(n),0k7 X(

25、4k+1)=DFTx14(n),0k3 X(4k+3)=DFTx24(n),0k3 43第第4章章 快速傅里叶变换快速傅里叶变换(FFT)图4.4.2 分裂基FFT算法L形排列示意图与结构示意图(a)分裂基FFT算法L形排列示意图；(b)分裂基FFT算法运算流图结构示意图(a)(b)44第第4章章 快速傅里叶变换快速傅里叶变换(FFT)图4.4.3 16点分裂基第一次分解L形流图(图中省去箭头)(8)点DFTx2(0)x2(1)x2(2)x2(3)x2(4)x2(5)x2(6)x2(7)点DFT点DFTx(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)x(8)x(9)x(10)x

26、(11)x(12)x(13)x(14)x(15)j j jX(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(2k)X(4k1)X(4k3)111111111145第第4章章 快速傅里叶变换快速傅里叶变换(FFT)第二次分解：先对图4.4.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 46第第4章章 快速傅里叶变换快速傅里叶变换(FFT)其中y2(n)=x2(

27、n)+x2(n+4),0n3y14(n)=x2(n)-x2(n+4)-x2(n+2)x(n+6)Wn8,n=0,1y24(n)=x2(n)-x2(n+4)+jx2(n+2)x2(n+6)W3n8,n=0,147第第4章章 快速傅里叶变换快速傅里叶变换(FFT)图4.4.4 图4.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)

28、X1(2l)X1(4l1)X1(4l3)j j1111111148第第4章章 快速傅里叶变换快速傅里叶变换(FFT)图4.4.5 4点分裂基L形运算流图 v(0)v(1)v(2)v(3)V(0)V(2)V(1)V(3)j111149第第4章章 快速傅里叶变换快速傅里叶变换(FFT)图4.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(1

29、5)j1111 j j1111 j j111111111111 j j j jW 1W 2W 3W 3W 6W 9W 2W 6111111111111NNNNNNNN50第第4章章 快速傅里叶变换快速傅里叶变换(FFT)4.4.2 分裂基FFT算法的运算量 设第j级有lj个L形，j=1,2,M-1,M=log2N，则有l1=N/4。由图4.4.2(b)可见，第j-1列中的L形包含了第j列中的一部分结点的计算，即空白部分，所占结点数刚好等于第j-1列中所有L形对应结点的一半，所以第j列L形个数就减少l j-1/2个，即 51第第4章章 快速傅里叶变换快速傅里叶变换(FFT)11122310424

30、1(1)424211(1)42424111()(1)42424jjjijjilNlNlNlNlNlNlNNl52第第4章章 快速傅里叶变换快速傅里叶变换(FFT)由于每个L形有两次复(数)乘运算，所以全部复乘次数为1122212()3332122log(1)399MMMjjMNClMNNN(4.4.5)53第第4章章 快速傅里叶变换快速傅里叶变换(FFT)4.5 离散哈特莱变换离散哈特莱变换(DHT)4.5.1 离散哈特莱变换定义 设x(n),n=0,1,N-1，为一实序列，其DHT定义为102()()()cos(),0,1,1NHnXkDHT x nx nkn kNN式中，cas()=cos

31、+sin。其逆变换(IDHT)为1012()()()cos(),0,1,1NHHkx nIDHT XkXkkn nNNN (4.5.3)54第第4章章 快速傅里叶变换快速傅里叶变换(FFT)4.5.2 DHT与DFT之间的关系 为了便于比较，重写DFT如下：211002110022()()()()cos()sin()1122()()()cos()sin()NNjknNnnNNjknNkkX kDFT x nx n ex nknjknNNx nX k eX kknjknNNNN(4.5.5)(4.5.6)容易看出，DHT的核函数 DFT的核函数 的实部与虚部之和。222cos()cos()sin

32、()knknknNNN222cos()()jknNeknjknNN55第第4章章 快速傅里叶变换快速傅里叶变换(FFT)将XH(k)分解为奇对称分量XHo(k)与偶对称分量XHe(k)之和()()()1()()()21()()()2HHeHoHeHHHoHHXkXkXkXkXkXNkXkXkXNk(4.5.7)(4.5.8)(4.5.9)由DHT定义有10102()()cos()2()()sin()NHenNHonXkx nknNXkx nknN(4.5.10a)(4.5.10b)56第第4章章 快速傅里叶变换快速傅里叶变换(FFT)所以，x(n)的DFT可表示为同理，x(n)的DHT可表示为

33、因此，已知x(n)的DHT，则DFT可用下式求得：()()()HeHoX kXkjXk(4.5.11)()()Im()HeXkH kX k(4.5.12)11()()()()()22HHHHX kXkXNkj XkXNk(4.5.13)57第第4章章 快速傅里叶变换快速傅里叶变换(FFT)4.5.3 DHT的主要优点 (1)DHT是实值变换，在对实信号或实数据进行谱分析时避免了复数运算，从而提高了运算效率，相应的硬件也更简单、更经济；(2)DHT的正、反变换(除因子1/N外)具有相同的形式，因而，实现DHT的硬件或软件既能进行DHT，也能进行IDHT；(3)DHT与DFT间的关系简单，容易实现

34、两种谱之间的相互转换。58第第4章章 快速傅里叶变换快速傅里叶变换(FFT)4.5.4 DHT的性质 1.线性性质11221212(),()()()()()()HHHHxXkx nXkax nbx naXkbXk(4.5.14)2.x(N-n)的DHT()(),()()HHx nXkx NnXNn1022()()cos()sin(),0,1,1NHnXNkx nknknkNNN(4.5.15)其中，当k=0时，XH(N-k)=XH(N)=XH(0)。59第第4章章 快速傅里叶变换快速傅里叶变换(FFT)3.循环移位性质00000022()()()cos()()sin()22()()()cos(

35、)()sin()NNHNNHx nnRnXkknH NkknNNx nnRnXkknH NkknNN(4.5.16)(4.5.17)60第第4章章 快速傅里叶变换快速傅里叶变换(FFT)4.奇偶性 奇对称序列和偶对称序列的DHT仍然是奇对称序列或偶对称序列，即DHT不改变序列的奇偶性。5.循环卷积定理1122122121121212()(),()()()()()()()()()()()()()()HHHHeHHoHHeHHox nXkx nXkx nx nXk XkXNk Xkx nx nXk XkXNk Xk(4.5.18)(4.5.19)61第第4章章 快速傅里叶变换快速傅里叶变换(FFT

36、)。当x1(n)或x2(n)是偶对称序列时，则由DHT的奇偶性有1212()()()()()HHHx nx nXkXk Xk(4.5.21)62第第4章章 快速傅里叶变换快速傅里叶变换(FFT)4.5.5 DHT的快速算法(FHT)1.基2DITFHT算法及运算流图 仿照快速DFT的分解方法，可通过时域抽取或频域抽取的方式实现快速DHT。x(n)的N=2M点DHT如下式：10011122002()()cos(),01()(2),01()(21)222()(2)cos(2)(21)cos(21)NHnNNHrrXkx nknkNNx rxrNrx rxrXkxrrkxrrkNN对x(n)进行奇偶

37、抽取(4.5.22)(4.5.23)63第第4章章 快速傅里叶变换快速傅里叶变换(FFT)与DFT的时域抽取分解比较，不是 一个指数函数，所以处理要比W(2r+1)kN麻烦一些。根据三角公式有2cos(21)krN112201001210cos()coscoscos()sin222()()cos()cos()()cos()/2/222sin()()cos()/2HrrrXkx rrkkx rrkNNNkx rrkNN(4.5.24)(4.5.25)64第第4章章 快速傅里叶变换快速傅里叶变换(FFT)令X0H(k)=DHTx0(n),X1H(k)=DHTx1(n)，并考虑DHT的周期性，(4.

38、5.25)式可写成01122()()cos()()sin()()2HHHHNXkXkk Xkk XkNN 为了使以下推导中公式简明，记 C(k)=cos(2/N)k，S(k)=sin(2/N)/k。将式(4.5.26)中的k分别取k，N/2+k,N/2-k和N-k四个值，并考虑X0H(k)和X1H(k)以N/2为周期，得到 65第第4章章 快速傅里叶变换快速傅里叶变换(FFT)011011011011()()()()()()2()()()()()()22()()()()()()222()()()()()()22HHHHHHHHHHHHHHHNXkXkC k XkS k XkNNXkXkC k

39、XkS k XkNNNXkXkS k XkC k XkNNXNkXkS k XkC k Xk048NkN(4.5.27)66第第4章章 快速傅里叶变换快速傅里叶变换(FFT)当k=0时，式(4.5.27)中有重复，可单独写成0101(0)(0)(0)()(0)(0)2HHHHHHXXXNXXX(4.5.28)同理，在k=N/4时有0101()()()4443()()()444HHHHHHNNNXXXNNNXXX(4.5.29)67第第4章章 快速傅里叶变换快速傅里叶变换(FFT)图4.5.1 基2DIT-FHT原理和哈特莱碟形点DFTx(0)x(2)x(N2)点DFTx(1)x(3)x(N1)

40、X0H(k)X1H(k)X0H(N/2 k)X1H(N/2 k)XH(k)XH(N/2 k)XH(N/2 k)XH(N k)c(k)s(k)s(k)c(k)11s(k)68第第4章章 快速傅里叶变换快速傅里叶变换(FFT)图4.5.2 4点DFHT蝶形图 1111x0(0)x(0)x0(2)x(2)x1(0)x(1)x1(1)x(3)XH(0)XH(1)XH(2)XH(3)69第第4章章 快速傅里叶变换快速傅里叶变换(FFT)图4.5.3 16点基2DITFHT流图 x(0)x(8)x(4)x(12)x(2)x(10)x(6)x(14)x(1)x(9)x(5)x(13)x(3)x(11)x(7

41、)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)111111111111111111111111111111 c2 c1 c3c3c2c1c2 c2s2s2s2s1s3s3s2c2 c2s2s21170第第4章章 快速傅里叶变换快速傅里叶变换(FFT)2.基2DITFHT的运算量 观察图4.5.3可知，运算流图中都是实数运算。N=2M点FHT流图共分为M级。用L表示流图自右向左的蝶形级数。第L级乘法次数为2L(N/2L-2)，但最后二级无乘法运算，所以，总的乘法次数MH为2112(2)34233222MLHLLHMNMNANMN(4.5.30)(4.5.31)同理可求得总的加法次数AH为71第第4章章 快速傅里叶变换快速傅里叶变换(FFT)4.5.6 实信号的快速循环卷积 用DITFFT计算两个实信号x1(n)和x2(n)的循环卷积时，最直接的方法是将信号的虚部都置为零，再按复序列用FFT计算。显然这样做是很浪费的。现在我们可用基2DITFHT直接进行实正交变换来处理实信号的循环卷积问题。1122()()()()FHTHFHTHx nXkx nXk12()()()()IFHTHYky nx nx n计算式(4.5.18)72