同济大学：《数字信号处理（DSP）》课程教学资源（PPT课件讲稿）第四章 快速傅里叶变换（3/9）

Q=、按频率进的蔡2F算法 1、算法原理 设序列点数N=2,L为整数。 将Ⅺk)按k的奇偶分组前,先将输入x(m)按n的 顺序分成前后两半:

三 、按频率抽选的基-2FFT算法 1、算法原理 设序列点数N=2 L ，L为整数。 将X(k)按k的奇偶分组前，先将输入x(n)按n的 顺序分成前后两半：

X(k)=∑x(n)W=∑x(m)W+∑x(mn) n=0 n=0 N/2-1 ∑x)W+∑xn+, n=0 N ∑|x(n)+xn+n|形 Nk/2 T nk WN2=-1 ∑|x(n)+(-1)xn+p减 k=0.1.N-1

1 / 2 1 1 0 0 / 2 ( ) ( ) ( ) ( ) N N N nk nk nk N N N n n n N X k x n W x n W x n W             / 2 1 / 2 1 2 0 0 ( ) 2 N N N n k nk N N n n N x n W x n W                       / 2 1 / 2 0 ( ) 2 N Nk nk N N n N x n x n W W                   / 2 1 0 ( ) ( 1) 2 N k nk N n N x n x n W                 k  0,1,...,N 1 / 2 1 N WN  

按k的奇偶将Xk)分成两部分: r=0.1.N/2-1 k=2r+1 X(2)=∑ N x(n)+xn+ N ∑|x(m)+x|n+2|W N/2 X(2r+1)=∑|x)-xn+2|2 n=0 N xI n+ 0

按k的奇偶将X(k)分成两部分： 2 2 1 k r k r       r  0,1,...,N / 2 1 / 2 1 2 0 (2 ) ( ) 2 N nr N n N X r x n x n W                / 2 1 (2 1) 0 (2 1) ( ) 2 N n r N n N X r x n x n W                  / 2 1 / 2 0 ( ) 2 N nr N n N x n x n W                / 2 1 / 2 0 ( ) 2 N n nr N N n N x n x n W W                  

N ,(n=x(n+xIn+ 0.1 x,(n x(1)-x|n+ 则X(2r)和X(2r+1)分别是x1(m)和x(n)的N/2 点DF7,记为X1(k)和2(k) ·x()+x( x(+ °x(m)-x(+,)W

令 1 2 ( ) ( ) 2 ( ) ( ) 2 n N N x n x n x n N x n x n x n W                           0,1,..., 1 2 N n   则X(2r)和X(2r+1)分别是x1(n)和x2(n)的 N / 2 点DFT，记为X1(k)和X2(k)

x(0 x1(0=X(0 x1( X1(1)=X(2) x(1) N2点 x, (2) DFT x(2) X1(2)=X(4) x1(3) (3) X1(3)=X(6) Wx(0) X2(0=X(1) W x2( x(5) X2(1)=X(3) N2点 W x2(2) DFT x(6) X2(2)X(5) X2(3)=X(7)

x1(0) x1(1) -1 x1(2) x1(3) -1 x2(0) x2(1) -1 x2(2) x2(3) -1 N/2点DFT N/2点DFT x(0) x(7) x(1) x(2) x(3) x(4) x(5) x(6) X1(0)=X(0) X2(0)=X(1) X1(1)=X(2) X1(2)=X(4) X1(3)=X(6) X2(1)=X(3) X2(2)=X(5) X2(3)=X(7) 1 WN0 WN2 WN3 WN