李洁《数字信号处理》20058 2.时域抽取法基2FF基本原理 X(k)=DFx(m)=∑x(n)W如k=01…N-1 012345678910 x(r)=x(2r),r=0,2,3x1(k)=∑x)4,k=012,3 x4k)=∑x(r)H+, X(k)=∑xn)W=x0)W“+x(2)W+x(4W+x16)1+x(DW+x(3)W+x5)H1+x7W =(x(0)H“+x02)2+x(4)W“+x(6)W4)+W(x()W"+x(3)W+x5W+x7)W =(x(0)W“+x(2)W+x4)W“+x(6)W“)+“(x(D)W“+x3)W“+x(5H:+x7)W2 x(k)=x1(k)+W:(x3(k),k=0123 X(+4)=x1(k+4)+W(x2(k+4)=X1(k)-H,(x2(k),k=0123 5 影x去 蝶形 Butterfly 李洁一《数字信号处理 630 Digital Signal processing Jie Li 2005李洁《数字信号处理》2005® Digital Signal Processing__Jie Li 2005® 3 李洁 -- 《数字信号处理》 -- 第四章 快速Fourier Fourier变换 5 / 30 2. 时域抽取法基2FFT基本原理 ( ) [ ( )] ( ) 0,1, , 1 1 0 = = ∑ = − − = X k DFT x n x n W k N N n kn N L W8 0 W8 4 W8 2 W8 5 W8 6 W8 3 W8 7 W8 1 0 1 2 3 4 5 6 7 8 9 10 n 0 N x(n) 1 ( ) (2 ), 0,1,2,3 x1 r = x r r = ( ) (2 1), 0,1,2,3 x2 r = x r + r = ( ) ( ) , 0,1,2,3 3 0 1 1 4 = ∑ = = X k x r k n kn W ( ) ( ) , 0,1,2,3 3 0 2 2 4 = ∑ = = X k x r k n kn W W W W W W W W W W k k k k k k k k n kn X k x n x x x x x x x x 7 8 5 8 3 8 1 8 6 8 4 8 2 8 0 8 7 0 8 ( ) = ∑ ( ) = (0) + (2) + (4) + (6) + (1) + (3) + (5) + (7) = W W kn j kn j kn kn e e 2 8 2 8 2 4 2 4 = = = − − π π ( ) ( ( )) ( (0) (2) (4) (6) ) ( (1) (3) (5) (7) ) ( (0) (2) (4) (6) ) ( (1) (3) (5) (7) ) 1 8 2 3 4 2 4 1 4 0 4 1 8 3 4 2 4 1 4 0 4 6 8 4 8 2 8 0 8 1 8 6 8 4 8 2 8 0 8 X k X k x x x x x x x x x x x x x x x x W W W W W W W W W W W W W W W W W W W k k k k k k k k k k k k k k k k k k k = + = + + + + + + + = + + + + + + + ( 4) ( 4) ( ( 4)) ( ) ( ( )), 0,1,2,3 ( ) ( ) ( ( )), 0,1,2,3 2 1 8 2 4 1 8 1 8 2 + = + + + = − = = + = + X k X k X k X k X k k X k X k X k k W W W k k k 李洁 -- 《数字信号处理》 -- 第四章 快速Fourier Fourier变换 6 / 30 „ 蝶形 WN k X1(k) X1(k)+WN k X2(k) X1(k)-WN k X2(k) X2(k) Butterfly