《数字信号处理》课程教学课件（2020讲稿）第四章 快速傅里叶变换 §4-4 按频率抽取（DIF）的FFT算法（Sande-Tukey算法）

第四章快速傅里叶变换

第四章 快速傅里叶变换

s 4-4按频率抽取(DIF)的FFT算法(Sande-Tukey算法)一、算法原理Vx(n),N=2'0≤n≤N-1↑X(k)= DFT[x(n)]N-1=Zx(n)Wm,0≤k≤N-1n=0将x(n)，0≤n≤N-1 按顺序分为前后两半NNNk(n+X(k)=Zx(n)WknA2+n)W+(4-23)2n=0n=0k=0,1,...,N-12元N注意：+WWn=eN.两个>和式并不是N/2-DFT

3 / 30 §4-4 按频率抽取(DIF)的FFT算法 (Sande-Tukey算法) 一、算法原理  x(n), 0  n  N 1, N  2 ( ) [ ( )] X k  DFT x n         1 0 ( ) , 0 1 N n kn x n WN k N 将x(n)，0 ≤ n ≤N-1 按顺序分为前后两半           1 2 0 1 2 0 ) 2 ( ) 2 ( ) ( ) ( N n N n N k n N kn N n W N X k x n W x k=0,1,.,N-1 (4-23) 注意： ∴两个∑和式并不是 N/2-DFT 2 2 j N W e W N N    

NN2= e-jnk = (-1)kW"2?N不过，由于eN所以，式(4-23)可改写为NNN+nX(k)=Zx(n)Whmtn7(4-23)2n=0n=0NN(4-24)Rk =0,1....N-1Z[x(n)+(-1)+n)2n=0k为偶数k为奇数:.可按k的奇偶取值将X(k)分为两部分：

4 / 30 ( ) N N k j k N j k k W e e N 2 2 2 不过，由于 1 所以，式(4-23)可改写为 1 2 0 [ ( ) ( 1) ( )] , 0,1,., 1 2 N k kn N n N x n x n W k N          (4-24)      为奇数 为偶数 k k k 1 1 ( 1) ∴可按k的奇偶取值将X(k)分为两部分： 1 1 2 2 ( ) 2 0 0 ( ) ( ) ( ) 2 N N N k n kn N N n n N X k x n W x n W           (4-23)

N2N2rnX(2r)=Z[x(n)+ x(+n)N2n=0NNNrnZ[x(n)+(4-25)n)专22n=0N-NW(2r+1)nX(2r +1)= Z[x(n)-x(=+n)lN2n=0NNW2rnZ[x(n)-+n2n=0NNNrZ[x(n)-(4-26)2N/222n=0

5 / 30       1 2 0 2 )] 2 (2 ) [ ( ) ( N n r n n WN N X r x n x 1 2 )] 0,1,., 2 [ ( ) ( 1 2 0 2         N n W r N x n x N n r n N         1 2 0 (2 1) )] 2 (2 1) [ ( ) ( N n r n n WN N X r x n x        1 2 0 2 )] 2 [ ( ) ( N n r n N n n WN W N x n x 1 2 )] 0,1,., 2 [ ( ) ( 1 2 0 2          N n W W r N x n x N n r n N n N (4-25) (4-26)

显然，若令NNNxi(n)=[x(n)+ x(n+1n=22N1k = 0,1X,(k)= X(2k),2NNWn= 0.1x2(n)=[x(n)-x(n+22N△k = 0.11X,(k)= X(2k +1),2则有（式(4-25)(4-26)分别变为)NNX(k) = X(2k) = DFT[x;(n)= Zx;(n)Wz:k=N'2n=0N-NX,(k)= X(2k +1)= DFT[x (n)]= x(n)Wk = 0.2n=0

6 / 30 显然，若令 1 2 )], 0,1,., 2 ( ) [ ( ) ( 1       N n N x n x n x n 1 2 ( ) (2 ), 0,1,., 1     N X k X k k 1 2 )] , 0,1,., 2 ( ) [ ( ) ( 2       N W n N x n x n x n n N 1 2 ( ) (2 1), 0,1,., 2      N X k X k k 则有（式(4-25)(4-26)分别变为） 1 2 ( ) (2 1) [ ( )] ( ) , 0,1,., 1 2 ( ) (2 ) [ ( )] ( ) , 0,1,., 1 2 0 2 2 2 2 1 2 0 2 1 1 1                  N X k X k DFT x n x n W k N X k X k DFT x n x n W k N n kn N N n kn N

可见，NDFT2按k为奇偶分解N-DFT按频率抽取NDFT2N1(n)=x(n)+x(n+(n2N1n=2N4NWNx(n+x2(n)=[x(n)-x(n+IW222

7 / 30 可见， N  DFT 按k为奇偶分解 按频率抽取 DFT N  2 DFT N  2 ) 2 ( ( ) N x n x n  n WN N x n x n x n N x n x n x n )] 2 ( ) [ ( ) ( ) 2 ( ) ( ) ( 2 1         1 2  0,1,.,  N n n WN

例：N=8，DIF的分解过程（见图4-16）[P.137]N=2v-1仍为偶数(v≥3):N=2V2(0)x(0)X(0)：上述分解过程可继续下去，(1)N/2点x(1)X(2)直至分解v次/步后变成求X(2)N/2 个 2-DFT 为止。DFTX(4)x(2)x(3)X(6)x(3)DIF-FFT算法(0)X()x(4)(1)X(3)x(5)N/2点（显然与DIT-FFT算法的分解类似）WNS5(2)x(6)DFTX(5)WN(3)(7)X()

8 / 30 例：N=8，DIF的分解过程（见图4-16）[P.137] 2 ( 3) 2 2 1       ，  仍为偶数 N N （显然与DIT-FFT算法的分解类似） N/2点 DFT N/2点 DFT DIF-FFT算法 ∴上述分解过程可继续下去， 直至分解ν次/步后变成求 N/2 个 2-DFT 为止

例：N=8，DIF-FFT算法流图[图4-18，P.138]Win注意：n=01.....N/2-1n=0,1....N/2-1N:WF→ Wn, n=0,l..,N/2-2n=01.....N/4-1-N/Wn=0,1.....N/8-1n=0.1....,N/2-4Vx(0)X(0)x(1)X(4)woX(2)②W(=1)，依然保留x(2)WoX(6)（为了算法结构上的统一）x(3)WWX()x(4)WlX(5)x(5)W!WNX(3)x(6)wi3WNW3x(7)X(7)Wo

9 / 30 例：N=8，DIF-FFT算法流图 [图4-18，P.138] 注意: ① , 0,1,., / 4 1 , 0,1,., / 2 2 2 W n  N   W n  N  n N n N , 0,1,., /8 1 0,1,., / 2 4 4 W n  N  n  N  n N W , n  0,1,.,N / 21 n  0,1,.,N / 21 n N ( 1), 0 ② WN  依然保留 （为了算法结构上的统一）

DIF-FFT与DIT-FFT的比较x(0)X(0)x(1)X(4)w!X(2)x(2)xi(n)Wx(n)X(6)x(3)NWWWNx(n+Wx,(n)2X(1)x(4)O4NW!xi(n)=x(n)+ x(n+2x(5)X(5)wWNANVJW"x2(n)=[x(n)-x(n+X(3)x(6)wi2WNW3x()X()W!图4-183N=8DIF-FFT算法流图

10 / 30 二、DIF-FFT与DIT-FFT的比较 图4-18 N=8,DIF-FFT算法流图 x(n) ( ) x1 n n WN ( ) ) x2 n 2 ( N x n  n WN N x n x n x n N x n x n x n )] 2 ( ) [ ( ) ( ) 2 ( ) ( ) ( 2 1        

X(0)x(0)WX(1)x(4)W,x(2)X(2)X,(k)X(k)WWX(3)x(6)NWX(k +X2(k)W!2X(4)x(1)W!WoX(k) = X,(k)+WnX,(k)X(5)x(5)WaONX(k+) = X,(k)-W"X,(kwo222Wx(3)X(6)WWix(7)X()图4-5N=8,DIT-FFT算法流图

11 / 30 图4-5 N=8,DIT-FFT算法流图 ( ) 1 X k X(k) k WN ( ) 2 X k ) 2 ( N X k  ) ( ) ( ) 2 ( ( ) ( ) ( ) 1 2 1 2 X k W X k N X k X k X k W X k n N n N     