第4章__快速傅里叶变换(FFT)-zh

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

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) 第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 如前所述，N点DFT的复乘次数等于N2。显然，把N点DFT分解为几个较短的DFT，可使乘法次数大大减少。另外，旋转因子WmN具有明

3、显的周期性和对称性。其周期性表现为22()jm lNjmm lNmNNNNWeeW(4.2.2) 其对称性表现为2mN mN mmNNNNNmmNNWWWWWW 或者 第第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的奇偶

4、把x(n)分解为两个N/2点的子序列12( )(2 ),0,1,12( )(21),0,1,12Nx rxrrNx rxrr第第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 k

5、W Xk第第4章章 快速傅里叶变换快速傅里叶变换(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(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) 第第4章章 快速傅里叶变换快速

6、傅里叶变换(FFT) 图4.2.1 蝶形运算符号 CABA BCA BC第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 图4.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)第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 与第一次分解相同，将x1(r)按奇偶分解成两个N/4长的子序列x3(l)和x4(l)，即3241( )(2

7、),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(4.2.9) 第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 式中 /4 133/430/4 144/440( )( )( )( )( )( )NklNiNklNix kx l WDFT x lx kx l WDFT x l 同理，由X3(k)和X4(k

8、)的周期性和Wm N/2的对称性 Wk+N/4 N/2=-Wk N/2 最后得到： 13/2413/24( )( )( ),0,1,/41(/4)( )( )kNkNX kXkWXkkNX kNXkWXk(4.2.10) 第第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

9、 lXkx l WDFT x lx lxllNx lxl第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 图4.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点DFTWN02WN02第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 图4.2.4 N点DI

10、TFFT运算流图(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)第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 4.2.3 DITFFT算法与直接计算DFT运算量的比较 每一级运算都需要N/2次复数乘和N次复数加(每个蝶形

11、需要两次复数加法)。所以，M级运算总共需要的复数乘次数为22(2)log22(2)logMANNCMNCN MNN复数加次数为 例如，N=210=1024时221048576204.8(/2)log5120NNN第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 图4.2.5 FFT算法与直接计算DFT所需乘法次数的比较曲线 第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 4.2.4 DITFFT的运算规律及编程思想 1.原位计算 由图4.2.4可以看出，DITFFT的运算过程很有规律。N=2M点的FFT共进行M级运算，每级由N/2个蝶形运算组成。 2.旋转因子的变化规律 如上所述，N点D

12、ITFFT运算流图中，每级都有N/2个蝶形。每个蝶形都要乘以因子WpN，称其为旋转因子，p称为旋转因子的指数。 第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 观察图4.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 MpJLNLML ML MPJJLNNNMLWW L

13、JNWWWJpJ(4.2.12) (4.2.13) 第第4章章 快速傅里叶变换快速傅里叶变换(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第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 下标L表示第L级运算，XL(J)则表示第L级运算后数组元素X(J)的值。如果要用实数运算完成上述蝶形运算，

14、可按下面的算法进行。 设 T=X L-1(J+B)WpN=TR+jTI X L-1(J)=XR(J)+jXI(J) 式中下标R表示取实部，I表示取虚部，22()cos() sin22()cos() sinRRRIIIRITXJBpXJBpNNTXJBpXJBpNN第第4章章 快速傅里叶变换快速傅里叶变换(FFT) ( )( )( )( )( )( )( )()( )()( )LRRRRIIIRRRIIIXJXJj JXJXJTXJXJTXJBXJTXJBXJT则 第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 4. 编程思想及程序框图图4.2.6 DITFFT运算和程序框图 开 始送入x(

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

16、里叶变换(FFT) 表4.2.1 顺序和倒序二进制数对照表 第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 图4.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)第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 图4.2.9 倒序程序框图 221NNLHJNLHI1 , N1I JTJAJXIAIXT)()()()(J KLHK KJJ2KKKJJNNY第第4章章

17、快速傅里叶变换快速傅里叶变换(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 nW第第4章章 快速傅里叶变换快速傅里叶变换(FFT) /

18、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)第第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 11/

19、20/2 12/20(2 )( )(21)( )NrnNnNrnNnXrx n WXrx n W (4.2.16) 第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 图4.2.10 DIFFFT蝶形运算流图符号 第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 图4.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)第第4章章 快速傅

20、里叶变换快速傅里叶变换(FFT) 图4.2.12 DIFFFT二次分解运算流图(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第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 图4.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

21、(5)x(6)x(7)第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 图4.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第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 图4.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)WN0WN2WN1WN3WN2

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

23、0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)WN2WN2N1N1N1N1N1N1N1第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 图4.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第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 如果希望直接调用FFT子程序计算IFFT，则可用

24、下面的方法： 由于 10101( )( )1( )( )NknNkNknNkx nX k WNx nXk WN对上式两边同时取共轭，得1011( )( )( )NknNkx nXk WDFT XkNN第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 4.3 进一步减少运算量的措施进一步减少运算量的措施 4.3.1 多类蝶形单元运算 由DITFFT运算流图已得出结论，N=2M点FFT共需要MN/2次复数乘法。 由(4.2.12)式，当L=1时，只有一种旋转因子W0N=1，所以，第一级不需要乘法运算。 第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 综上所述，先除去第一、二两级后，所需复数乘

25、法次数应是 从L=3至L=M共减少复数乘法次数为(2)(2)2MNCM(4.3.1) 13312( )2222MMLLLLNNN(4.3.2) 因此，DITFFT的复乘次数降至 (2)(2)(2)(3)2222MNNNCMM(4.3.3) 第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 22(1)()()222()()22()222()()22defjxjyxjyjxyxyj xyRjIRxyIxyyx 第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 从实数运算考虑，计算N=2M点DITFFT所需实数乘法次数为(2)4(3)2(2)2213(2)102MNNRMNM(4.3.4)第第4

26、章章 快速傅里叶变换快速傅里叶变换(FFT) 4.3.2 旋转因子的生成 在FFT运算中，旋转因子WmN=cos(2m/N)-jsin(2m/N)，求正弦和余弦函数值的计算量是很大的。 第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 4.3.3 实序列的FFT算法 设x(n)为N点实序列，取x(n)的偶数点和奇数点分别作为新构造序列y(n)的实部和虚部，即1212( )(2 ),( )(21),0,1,12( )( )( ),0,1,12Nx nxnx nxnnNy nx njx n n对y(n)进行N/2点FFT，输出Y(k)，则1122( )( )( ),0,1,1( )( )( )2

27、epopX kDFT x nYkNkXkDFT x njYk 根据DITFFT的思想及式(4.2.7)和(4.2.8)，可得到 12( )( )( ),0,1,2kNNX kX kW Xk k第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 由于x(n)为实序列，所以X(k)具有共轭对称性，X(k)的另外N/2点的值为 ()( ),1,2,12NX NkXk k第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 4.4 分裂基分裂基FFT算法算法 4.4.1 分裂基FFT算法原理 当n=pq，且p=N/4，q=4时，n可表示为101010,03,0144NNnpnnnnnn并有 10110/

28、4 13()41000( )( )()4NknNnNNknnNnnX kx n WNxnn W 第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 010100/4 13104/4 1024040403304()4 ( )()()423()4NknknNnnNkknknkkNNNWxnn WNNx n Wx nWx nWNx nW WW再将上式中的k表示为10104,01,034Nkkkkk第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 可得 1001010100000010010/4 1(4)0040823(4)(4)0404/4 120040403(4)04( )(4) ()()43(

29、)()24 ()()()423()4NkknkkkkknNNkknkkknNX kXkkNx nx nWNNx nWx nWWNNx nx nWx nWNx nWW 对k0=0，1,2,3,并用k表示k1，用n表示n0，可以写出第第4章章 快速傅里叶变换快速傅里叶变换(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

30、nWNNXkx njx nx njx n/4 14303)4014NknnNnNWNk (4.4.1) 第第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) 第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 214234( )( )(),01223( ) ( )()()()42

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

32、 图4.4.1 分裂基第一次分解L形流图 点DFT 点DFT 点DFTx2(1)x2(1 N/4)2N4N4N) 1 (14x) 1 (24x1NW3NWx(1)41Nx21Nx431Nx 1 1 1 j第第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), 0

33、k7 X(4k+1)=DFTx14(n), 0k3 X(4k+3)=DFTx24(n), 0k3 第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 图4.4.2 分裂基FFT算法L形排列示意图与结构示意图(a)分裂基FFT算法L形排列示意图；(b)分裂基FFT算法运算流图结构示意图 ( a )( b )第第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点DFT)0(14x) 1 (14x)2(14x)3(14x)0(24x) 1

34、 (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(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第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 第二次分解： 先对图4.4.3中N/2点DFT进行分解。 令X1(l)=X(2l)，则有 X1(2l)=DFT

35、y2(n), 0l3 X1(4l+1)=DFTy14(n), 0l1 X1(4l+3)=DFTy24(n), 0l1 第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 其中y2(n)=x2(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,1第第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(

36、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 j j11111111第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 图4.4.5 4点分裂基L形运算流图 v(0)v(1)v(2)v(3)V(0)V(2)V(1)V(3) j1111第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 图4.4.6 16点分裂基F

37、FT运算流图 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 j111111111111 j j j jW 1W 2W 3W 3W 6W 9W 2W 6111111111111NNNNNNNN第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 4.4.2 分裂基FFT算法的运算量 设第j级有lj个L形，j=1,2,M-1,M=log

38、2N，则有l1=N/4。由图4.4.2(b)可见，第j-1列中的L形包含了第j列中的一部分结点的计算，即空白部分，所占结点数刚好等于第j-1列中所有L形对应结点的一半，所以第j列L形个数就减少l j-1/2个，即 第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 111223104241(1)424211(1)42424111()(1) 42424jjjijjilNlNlNlNlNlNlNNl第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 由于每个L形有两次复(数)乘运算，所以全部复乘次数为1122212() 3332122log( 1)399MMMjjMNClMNNN (4.4.5)

39、第第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+sin。其逆变换(IDHT)为1012( )( )( )cos(),0,1,1NHHkx nIDHT XkXkkn nNNN (4.5.3) 第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 逆变换证明如下：1010101022cos()cos()2222cos()sin()cos()sin

40、()2222cos()cos()sin()sin()2222cos()sin()sin()cos()22cos()sinNkNkNkNkknkNNknknkkNNNNknkknkNNNNknkknkNNNNk nN(),0,k nNNnn(4.5.4) 第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 将式(4.5.2)代入式(4.5.3)得1100110010122( )cos()cos()122( )cos()cos(),01( )0,0NNkNNkNkxkknNNNxknkNNNNxN 第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 4.5.2 DHT与DFT之间的关系 为了便于比

41、较，重写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()knknknNNN222cos()()jknNeknjknNN第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 将XH(k)分解为奇对称分量XHo(k)与偶对称分量XHe(k)之和 ( )( )( )1( )(

42、 )()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) 第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 所以，x(n)的DFT可表示为同理，x(n)的DHT可表示为因此，已知x(n)的DHT，则DFT可用下式求得： ( )( )( )HeHoX kXkjXk(4.5.11)( )( )Im( )HeXkHkX k(4.5.12)11( )( )()( )

43、()22HHHHX kXkXNkj XkXNk(4.5.13) 第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 4.5.3 DHT的主要优点 (1)DHT是实值变换，在对实信号或实数据进行谱分析时避免了复数运算，从而提高了运算效率，相应的硬件也更简单、更经济； (2)DHT的正、反变换(除因子1/N外)具有相同的形式，因而，实现DHT的硬件或软件既能进行DHT，也能进行IDHT； (3)DHT与DFT间的关系简单，容易实现两种谱之间的相互转换。 第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 4.5.4 DHT的性质 1. 线性性质11221212( ),( )( )( )( )( )

44、( )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)。第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 证明 由DHT定义 1010102 ()()cos()2( )cos()22( )cos()sin()NnNnNnDFT x Nnx NnknNx nk NnNx nknknNN而 10102()( )cos() )22( )cos(

45、)sin() ()NHnNnXNkx nNk nNx nknknDFT x NnNN第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 3. 循环移位性质00000022()( )( )cos()()sin()22()( )( )cos()()sin()NNHNNHx nnRnXkknH NkknNNx nnRnXkknH NkknNN(4.5.16) (4.5.17) 证明 由DHT定义有 101010 ()( )2() cos()2( )cos()2222( )cos()cos()sin()sin()2222sin()cos()cos()sin()oNNNoNnNonNoonooDHT x

46、 nnRnx nnknNx nk nnNx nknknknknNNNNknknknknNNNN第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 1010222( )cos()sin()cos()222( )cos()sin()sin()22( )cos()()sin()NonNonHoHox nknknknNNNx nknknknNNNXkknXNkknNN第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 4. 奇偶性 奇对称序列和偶对称序列的DHT仍然是奇对称序列或偶对称序列，即DHT不改变序列的奇偶性。 5.循环卷积定理1122122121121212( )( ),( )( )( )(

47、 )( )( )()( )( )( )( )( )()( )HHHHeHHoHHeHHox nXkx nXkx nx nXk XkXNk Xkx nx nXk XkXNk Xk(4.5.18) (4.5.19) 第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 证明 下面利用DFT的循环卷积定理和DHT与DFT之间的关系来证明 其中，X1(k)=DFTx1(n),X2(k)=DFTx2(n),根据DHT与DFT之间的关系，则有1212( )( )( )( )DFT x nx nX kXk111222222( )( )( )( )( )( )11( )()()22HeHoHeHoHHHX kX

48、kjXkXkXkjXkXkXNkj XNk第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 将上面两式代入式(4.5.20)并整理后，得21111211111221211( )( )( )( )( )( )21()( )( )( )( )2( )( )( )Re( )Im( )( )( )()( )HHeHoHeHoHHeHoHeHoHHHeHHoX kXkXkXkjXkjXkXNkXkXkjXkjXkXkDFT x nx nX kX kXk XkXNk Xk所以式(4.5.18)成立。同理可证明式(4.5.19)亦成立。 当x1(n)或x2(n)是偶对称序列时，则由DHT的奇偶性有1212

49、( )( )( )( )( )HHHx nx nXkXk Xk(4.5.21)第第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)进行奇偶抽取(4.5.22) (4.5.23)第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 与DFT的时域抽取分解比较， 不是 一个指数函数，所以处理要比W(2r+1)kN麻烦一些。 根据三角公式有2cos(21)krN112201001210cos()coscoscos()sin222( )( )cos()cos()( )cos()/2/2