第4章快速傅立叶变换(FFT) 4.2.2时域抽取法基2FFT基本原理 染算法原理 (一)N/2点DFT 1.先将x(n)按n的奇偶分为两组作DFT,设N=2M,这样 有： x2r)=x6r=01,}-1 n为偶数时： x2r+10=x2r,r=0,1,-1 n为奇数时： X)=DFT=2ww时 n-0
4.2.2 时域抽取法基2FFT基本原理 − − = = 1 0 ( ) [ ( )] ( ) N n nk n WN X k DFT x n x 算法原理 (一)N/2点DFT (2 1) ( ), 0,1, , 1 (2 ) ( ), 0,1, , 1 2 2 1 2 + = = − = = − N N x r x r r x r x r r 1.先将x(n) 按n的奇偶分为两组作DFT,设N=2M , 这样 有: n为偶数时: n为奇数时: 第4章 快速傅立叶变换（FFT）
第4章快速傅立叶变换(FFT) X=空w±∑xaw N-1 N-1 n=0(n为偶数) n=0(n为奇数) 2rwg+2ar+Dwg叫 =0 -克+r空口my 因为：w=e疼”=e2》=W X(k)=∑xr)W+WΣx,(r)W=X(k)+WX(k)
− = + − = = + + 1 0 (2 1) 1 0 2 2 2 (2 ) (2 1) N N r r k N r r k x r WN x r W − = − = = + 1 0 1 0 ( ) ( ) ( ) N n N n nk N nk X k x n WN x n W (n为偶数) (n为奇数) 2 2 2 2 2 2 / ( ) N N W e N e W j j N = = = − − 因为： X(k) x (r)W W x (r)W X (k) W X (k) k N r k r k N r r k N N N N 1 2 1 0 2 1 0 1 2 2 2 2 = + = + − = − = − = − = = + 1 0 2 2 1 0 2 1 2 2 ( )( ) ( )( ) N N r r k N k N r r k x r WN W x r W 第4章 快速傅立叶变换（FFT）
第4章快速傅立叶变换(FFT) -1 -1 X,(k)=Σx(r)W=Σx(2r)W X(k)= 艺x)wg-三(2r+Dw 2.两点结论 (1)X1(k),X2(k)均为N/2点的DFT。 (2)X(k)=X1(k)+WNX2(k)只能确定出X(k)的 k=0.1.N/2-1个，即前一半的结果
(1) X1 (k),X2 (k)均为N/2点的DFT。 (2) X(k)=X1 (k)+WN k X2 (k)只能确定出X(k)的 k= 0.1.N/2-1 个，即前一半的结果。 − = − = − = − = = = + = = 1 0 1 0 2 2 1 0 1 0 1 1 2 2 2 2 2 2 2 2 2 1 2 N N N N N N N N r r k r r k r r k r r k X k x r W x r W X k x r W x r W ( ) ( ) ( ) ( ) ( ) ( ) 2.两点结论 第4章 快速傅立叶变换（FFT）
第4章快速傅立叶变换 (FFT) 3.Xk)的后一半的确定 -WWN=-WW X+义=XW+义+ (k+ X(k+ 由于X1和X2)均以NW2为周期，得 x空=X因x今+=x,) Xk+》=x-X,因 k=0,1,岁-1 可见X(k)的后一半，也完全由X(k),X2(k)的前一 半所确定。 *N点的DFT可由两个N/2点的DFT来计算
3.X(k)的后一半的确定 ) ( ) 2 ( 1 1 k X k N X + = ) ( ) 2 ( 2 k X2 k N X + = 由于X1 (k)和X2 (k)均以N/2为周期，得 ) 2 ) ( 2 ) ( 2 ( 2 ) 2 ( 1 N W X k N X k N X k N k = + + N + + ＋ k N k WN WN W N = = − 2 ) ( ) ( ) 0,1, , 1 2 (k 1 2 2 = − = − k N N X k W X k k N X ＋ 可见,X(k)的后一半，也完全由X1 (k), X2 (k)的前一 半所确定。 *N点的DFT可由两个N/2点的DFT来计算。 第4章 快速傅立叶变换（FFT）
第4章快速傅立叶变换 (FFT) 4.蝶形运算 1次复乘2次复加 X(k)=X1(k)+W2(k) 前一半k=0,1,2. X(k)=X1(k)-WX2(k)后一半k=0,1,2. 实现上式运算的流图称作堞形运算 (N/2个蝶形) X (k) X()=X(k)+WX2(k)(前一半) X2(k) W X(6+k)=X()-WX,(k)(后一半）
实现上式运算的流图称作蝶形运算（N/2个蝶形) 4.蝶形运算 1 2 ( ) ( ) ( ) k 0,1,2 1 2 ( ) ( ) ( k 0,1,2 1 2 1 2 = − = − = + = − N X k X k W X k N X k X k W X k k N k N 后一半 ）前一半 X(k) X (k) W X (k) (前一半) k 1 N 2 = + ) ( ) ( )(后一半) 2 ( 1 2 k X k W X k N X k + = − N 1 1 1 1 -1 ( ) 1 X k ( ) 2 X k k WN 1次 复乘2次复加 第4章 快速傅立叶变换（FFT）