第四章快速傅里叶变换
第四章 快速傅里叶变换
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