按时间抽取的基一2FFT算法 以N=4为例 X()=x0)+x(1)+x2)+x(3)=x(0)A(2)+[x()Bx(3 X)0x0)+x(wy-x(2)-2x3w=x0)c(2)+Wx()x(3 N2)=x00)+2301 X(3)=3(0)-=x()1-x2)+x(3)4=x(0)c(2)-W{()Dx(3) 运算流图x(O X(0 x(2) ACB X(1 X(2) D w x(3) X(3) 1 王
按时间抽取的基－2 FFT算法 以 N＝4为例 (3) (0) (1) (2) (3) (0) (2) (1) (3) (2) (0) (1) (2) (3) (0) (2) (1) (3) (1) (0) (1) (2) (3) (0) (2) (1) (3) (0) (0) (1) (2) (3) (0) (2) (1) (3) 1 4 1 4 1 4 1 4 1 4 1 4 X x x W x x W x x W x x X x x x x x x x x X x x W x x W x x W x x X x x x x x x x x = − − + = − − − = − + − = + − + = + − − = − + − = + + + = + A + + B A B C D C D 运算流图 x(0) x(2) x(1) x(3) A -1 C -1 B D 1 W4 X (0) X (2) -1 X (1) X (3) -1
按时间抽取的基=2FFT算法 算法原理 (一)N2点DFT 1.先将ⅹ(η)按n的奇偶分为两组作DFT设N=24(L大于 等于2),不足时,可补些零,这样一个N点的DFT分 解为两个N/2点的DFT。 X(k)=∑x(m)W=∑x(mW+∑x(n)W n为偶数 n为奇数 ∑x(2r)+∑x(2r+1)W +1)k O ∑x(21)形+形∑x(2r+ = E(+wFc
按时间抽取的基－2 FFT算法 一、算法原理 1. 先将x(n)按n的奇偶分为两组作DFT,设N=2 L （L大于 等于2），不足时，可补些零，这样一个N点的DFT分 解为两个N/2点的DFT。 ( ) ( ) (2 ) (2 1) (2 ) (2 1) 1 0 2 1 0 2 1 0 (2 1) 1 0 2 2 2 2 2 E k W F k x r W W x r W x r W x r W k N r r k N k N r r k N r r k N r r k N N N N N = + = + + = + + − = − = − = + − = − = − = − = = = + 1 0 1 0 1 0 ( ) ( ) ( ) ( ) N n n N n n kn N kn N N n kn X k x n WN x n W x n W 为偶数 为奇数 (一)N/2点DFT
按时间抽取的基一2FFT算法 2.分解说明 E(k)=∑x(2)W0≤k≤ N F()=∑x(2n+1)W0≤k≤ E(k)和F(k)均为N2点的DFT,均以M2为周期; 因W是以N为周期,故X(k)是以N为周期 X(k)=E(k)+WF(k)只能确定出X(k)的k￡,…,个1 值,即前一半的结果
2. 分解说明： 1 2 ( ) (2 ) 0 1 0 2 2 = − − = N E k x r W k N r r k N 1 2 ( ) (2 1) 0 1 0 2 2 = + − − = N F k x r W k N r r k N • E(k)和F(k)均为N/2点的DFT，均以N/2为周期； • 因W 是以N为周期，故X(k)是以N为周期； • X(k)=E(k)+W F(k)只能确定出X(k)的k= 个 值，即前一半的结果。 0,1, , 1 2 − k N N k N 按时间抽取的基－2 FFT算法
按时间抽取的基-2FFT算法 3.Xk)后一丰的确定 由旋转因子的周期性(k+y)mmk E(2+k)=x(2)”=∑x(2)Wy=E(k) 同理:F( n+k)=F(k) 2 这就是说,E(k)和F(k)的后一半分别等于其前一半的值。 W(+k)=WWk=一Wk X(k+)=Ek+)+WF(k+)=E(k)-WF(k)0≤k≤-1 可见X(k)的后一半,也完全由E(k和F(k)的前一半确定。 即N点的DFT可由两个N/2点的DFT来计算
按时间抽取的基－2 FFT算法 3. X(k)后一半的确定 由旋转因子的周期性： r k rk N N WN W 2 2 2 ( ) = + ) (2 ) (2 ) ( ) 2 ( 1 0 ( ) 1 0 2 2 2 2 2 k x r W x r W E k N E N N N N N r r k r k r + = = = − = + − = 这就是说，E(k)和F(k)的后一半分别等于其前一半的值。 同理： ) ( ) 2 ( k F k N F + = k N k N N k WN W W W N N = = − +2 2 ( ) 1 2 ) ( ) ( ) 0 2 ) ( 2 ) ( 2 ( 2 + = + + + = − − + N E k W F k k N W F k N E k N X k k N k N N 可见,X(k)的后一半，也完全由E(k)和F(k)的前一半确定。 即N点的DFT可由两个N/2点的DFT来计算
。按时间抽取的基一2FFT算法 4.蝶形运算一一流图表示 由E(K)、F扆示)的运算是一种特殊的运算-碟形运算 X(K=E(k)+WNF(k) X(k+)=E(k)-WF(k)(k=01…,-1 2 蝶形运算流图(N2个蝶形) E(k) X(k FlK)wk X￥(-+k
4. 蝶形运算－－流图表示 蝶形运算流图（N/2个蝶形): -1 X (k) ) 2 ( k N X + E(k) F(k) k WN ) ( ) ( ) 2 ( ( ) ( ) ( ) E k W F k N X k X k E k W F k k N k N + = − = + ( 0,1, , 1) ( 0,1, , 1) 2 2 = − = − N N k k 由E(k)、F(k)表示X(k)的运算是一种特殊的运算-碟形运算 按时间抽取的基－2 FFT算法