同济大学：《数字信号处理（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

N/2仍为偶数,进一步分解:N/2→)N/4 x(n)=x1(m)+x(n+N/4) x4(m)=[x1(n)-x(n+N/4)x2 0.1. 4 A X3(k)=X,(2k)=DFT[x, (n) k=0.1 X4(k)=X1(2k+1)=DF[x4(m) N4

N /2仍为偶数，进一步分解：N /2  N /4 3 1 1 4 1 1 / 2 ( ) ( ) ( / 4) ( ) [ ( ) ( / 4)] n N x n x n x n N x n x n x n N W          0,1,..., 1 4 N n   3 1 3 4 1 4 ( ) (2 ) [ ( )] ( ) (2 1) [ ( )] X k X k DFT x n X k X k DFT x n         0,1,..., 1 4 N k  

x3(0 x3(O)=X1(0)=X(0) N4点 DET 1(1) X3(1)=X1(2)=X(4) 0 1(2) M2x4(0 x4(0=X1(1)=X(2) N4点 DET x1(3) WM2x4(1) X4(1)=X1(3)X(6)

x3(0) x3(1) -1-1 x4(0) x4(1) N/4点DFT N/4点 DFT x1(0) x1(1) x1(2) x1(3) X3(0)=X1(0)=X(0) X4(0)=X1(1)=X(2) X3(1)=X1(2)=X(4) X4(1)=X1(3)=X(6) 0 WN / 2 1 WN / 2

同理: Xs(k)=X,(2k)= DFTL.(n) k=0.1 X6(k)=X2(2k+1)=DFT[x6(m) 4 其中 x6(mn)=[x2(m)-x2(n+N/4)W+=0,1.4 x5(n)=x2(m)+x2(n+N/4) 4

0,1,..., 1 4 N k   5 2 5 6 2 6 ( ) (2 ) [ ( )] ( ) (2 1) [ ( )] X k X k DFT x n X k X k DFT x n         同理： 其中： 5 2 2 6 2 2 / 2 ( ) ( ) ( / 4) ( ) [ ( ) ( / 4)] n N x n x n x n N x n x n x n N W          0,1,..., 1 4 N n  

x(0) x(0) 点 DFT oX(4) x(2)q X(2) 4点 x(3) WI DFT oX(6) x(4)d X(1) 点 y 4 x(5) DFT oX(5) (6 X(3) 点 x(7) DFT X(7 图4-16按频率抽选将一个N点DFT分解为4个N4点DFT(N=8)

逐级分解,直到2点DFT 当N=8时,即分解到x3(n),x4(m),x(m), xln), n= X)=∑x()WM4=∑x()W的4k=0,1 X(0)=Xx(0)=x(O)m2+2x(①)=x0)+x() 1x(4)=x:()=x(0)W2+72x()=x0)-x(W N/4-1 X4(k)=∑x(1)W4=∑x()WM4k=01 =0 )=X4(0)=x(O)W2+W2x4(1)=x4(0)+x4(1) 1x(6)=x()=x、O形2+形2x()=[x:(0)-x:()JF

逐级分解，直到2点DFT 0 0 3 3 2 2 3 3 3 0 1 0 3 3 2 2 3 3 3 (0) (0) (0) (1) (0) (1) (4) (1) (0) (1) [ (0) (1)] N X X x W W x x x X X x W W x x x W              / 4 1 1 3 3 / 4 3 / 4 0 0 ( ) ( ) ( ) N lk lk N N l l X k x l W x l W        k  0,1 当N=8时，即分解到x3(n)，x4(n)，x5(n)， x6(n)，n=0,1 0 0 4 4 2 2 4 4 4 0 1 0 4 4 2 2 4 4 4 (2) (0) (0) (1) (0) (1) (6) (1) (0) (1) [ (0) (1)] N X X x W W x x x X X x W W x x x W              / 4 1 1 4 4 / 4 4 / 4 0 0 ( ) ( ) ( ) N lk lk N N l l X k x l W x l W        k  0,1