第四章快速傅里叶变换
第四章 快速傅里叶变换
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 / 21 n 0,1,.,N / 21 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