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

1、算法原理 设序列点数N=2,L为整数 若不满足,则补零 N为2的整数幂的FFT算法称基-2FFT算法。 将序列x(n)按n的奇偶分成两组: x(2r)=x1(r 0 1··· N/2-1 x(2r+1)=x2()

二 、按时间抽选的基-2FFT算法 1、算法原理 设序列点数 N = 2 L ，L 为整数。 若不满足，则补零         1 2 2 2 1 x r x r x r x r    r  0,1,...,N / 2 1 将序列x(n)按n的奇偶分成两组： N为2的整数幂的FFT算法称基-2FFT算法

则x(n)的DFT X(k)=∑x(n)W=∑x(n)W+∑x(nW n为偶数n为奇数 N/2-1 ∑x(2n)W3+∑x(2x+1)w r=0 N/2-1 N/2-1 ∑x1()V3)+H∑x2()V3) r=0 N/2-1 ∑x()WM2+W∑x()WM2 r=0 X1()+WX2()F,k=0,1,N/2-1

则x(n)的DFT:         1 1 1 0 0 0 N N N nk nk nk N N N n n n X k x n W x n W x n W            n为偶数 n为奇数       / 2 1 / 2 1 2 2 1 0 0 2 2 1 N N rk r k N N r r x r W x r W                 / 2 1 / 2 1 2 2 1 2 0 0 N N rk rk k N N N r r x r W W x r W             / 2 1 / 2 1 1 / 2 2 / 2 0 0 N N rk k rk N N N r r x r W W x r W             1 2 k X N  k W X k r,k  0,1,...N / 2 1

再利用周期性求X(k)的后半部分 x1(k),X2(k)是以N/2为周期的 X|k+y|=X() N k X2() 又WN2=WN2Wk=-Wk X(h)=X,()+WNX2(k) k=0,12,N/2-1 N X(k+=)=X1(k)-WNX2(k) X1(k) Xi()+W/ X2(k) X2(k) w Xi(k)-WN X2(k)

再利用周期性求X(k)的后半部分 1 2 1 2 ( ) ( ) ( ) ( ) ( ) ( ) 2 k N k N X k X k W X k N X k X k W X k           k  0,1,...,N / 2 1         1 2 1 1 2 2 , / 2 2 2 X k X k N N N X k X k X k X k                   是以 为周期的 2 / 2 N k N k k WN WN WN WN  又   

x1(0)=x(0) X1(0) X(0) x(1)=x(2) (1) X(1) 2 点 x1(2)=x(4) K1(2) X(2) DFT x1(3)=x(6) X1(3) X(3) x2(0)=x(1) (0) X(4) J x2(1)=x(3) Xa(1) 点 X(5) x2(2)=x(5) (2) DFT i X(6) x2(3)=x(7) X2(3) X(7) 图4-2按时间抽选,将一个N点DFT分解为两个M2点DFT

分解后的运算 复数乘法复数加法 个N/2点DFT(N/2)2 N/2(M/2-1) 两个N/2点DFTN2/2 N(N/2-1) 个蝶形 N/2个蝶形 N/2 N 总计 N2/2+N/2N(N/2-1)+N ≈N2/2 ≈N2/2 运算量减少了近一半

分解后的运算量： 复数乘法 复数加法 一个N / 2点DFT (N / 2) 2 N / 2 (N / 2 –1) 两个N / 2点DFT N 2 / 2 N (N / 2 –1) 一个蝶形 1 2 N / 2个蝶形 N / 2 N 总计 2 2 / 2 / 2 / 2 N N N     2 / 2 1 / 2 N N N N    运算量减少了近一半

N/2仍为偶数,进一步分解:N/2→N/4 x1(2)=x3( 7=0,1,…,N/4-1 x(2+1)=x(0 X1(k)=X3(k)+WN24( X(k+)=X3(k)-Wk2X)k=0 N 4 x3(0)=x1(0)=x(0) X3(0) X1(0) 点 (1)=x1(2)=x(4) DET 3(1) x4(0)=x1(1)=x(2 X4(0) N X1(2) 点 x4(1)=x1(3)=x(6 DFT X4(D) X1(3) N/2 图4-3由两个N4点DFT组合成一个N2点DFT

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

同理: X,(k)=X(k)+WNoX(k k=0 N X2(k+)=X5(k)-WM2X6(k) 4 其中: Xs(k)=DFTIx= dFtix,(2D)] l=0.1.N/4-1 x6()=DFTx()=DF7x2(2/+1) 统一系数:W2→>W

2 5 / 2 6 2 5 / 2 6 ( ) ( ) ( ) ( ) ( ) ( ) 4 k N k N X k X k W X k N X k X k W X k           0,1,..., 1 4 N k   同理： 其中： 5 5 2 X (k)  DFT[x (l)]  DFT[x (2l)] 6 6 2 X (k)  DFT[x (l)]  DFT[x (2l 1)] l  0,1,...,N / 4 1 2 / 2 k k 统一系数：WN WN

X3(0 X1(0) X(0) 点 x3(1)=x1(2)=x(4) DFT LX3(1 X1(1 1(2) (0)=x1(1)=x(2) X4(0) N 点 7x() x4(1)=x1(3)=x(6) DFT LX (D) X1(3) X(3) X2(0) x5(0)=x2(0)=x(1) Xs(0) 点 X2(1) x5(1)=x2(2)=x(5) DFT XS() X(5) x6(0)=x2(1)=x(3) X6(0 X2(2) N 点 x6(1)=x2(3)=x(7) DET X(D) X2(3) 图44按时间抽选,将一个N点DFT分解为四个N4点DFT(N=8)

这样逐级分解,直到2点DFT 当N=8时,即分解到X3(k),X4(k),X5(k), x6(k),k=0,1 X)=∑x()WM4=∑x(O)W的4k=0 x3(0)=x3(OW2+W2x3(1)=x(0)+Wx(4 x)=x(0)+形2x:()=x(0)-形3(4 N/4-1 X4(k)=∑x()WM4=∑x1()WM4k=01 =0 ∫X(O)=x1(O)H2+2x(1)=x(2)+Hx(6) x()=x:(0)2+2(1)=x2)-3(6

这样逐级分解，直到2点DFT 当N = 8时，即分解到X3(k)，X4(k)，X5(k)， X6(k)，k = 0, 1 0 0 0 3 3 2 2 3 0 1 0 3 3 2 2 3 (0) (0) (1) (0) (4) (1) (0) (1) (0) (4) N N X x W W x x W x X x W W x x W x            / 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 0 0 0 4 4 2 2 4 0 1 0 4 4 2 2 4 (0) (0) (1) (2) (6) (1) (0) (1) (2) (6) N N X x W W x x W x X x W W x x W x            / 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

x(0) 70 x(4) X(1) H x(2) X(2) x(6) X(3) X(4) wO x(5) X(5) x(3) X(6) n n x(7) X(7) 图45N=8按时间抽选法FFT运算流图