按时间抽取的基一2FFT算法 (二)N4点DFT 由于N=2L,所以N/2仍为偶数,可以进一步把每个N/2 点的序列再按其奇偶部分分解为两个N/4的子序列。 E(k)=A(k)+WN B(k) F(k)=C(k)+WN,D(k) E(k+)=4(k)-B(k)F(k+4)=C(k)-WD(k) 其中: (k=01…,4-1) Ak)=∑x(41)W4B(k)=∑x(1+24 C)=∑x(41+)4D(k)=∑x(4+3)W4 =0 蝶形图同上类似。 4
按时间抽取的基－2 FFT算法 (二) N/4点DFT 由于N=2 L ,所以 N/2仍为偶数,可以进一步把每个N/2 点的序列再按其奇偶部分分解为两个N/4的子序列。 ) ( ) ( ) 4 ( ( ) ( ) ( ) 2 2 A k W B k N E k E k A k W B k k N k N + = − = + ( 0,1, , 1) 4 = − N k ) ( ) ( ) 4 ( ( ) ( ) ( ) 2 2 C k W D k N F k F k C k W D k k N k N + = − = + 其中： kl l N N A k x l W 4 4 1 0 ( ) (4 ) − = = kl l N N B k x l W 4 4 1 0 ( ) (4 2) − = = + kl l N N C k x l W 4 4 1 0 ( ) (4 1) − = = + kl l N N D k x l W 4 4 1 0 ( ) (4 3) − = = + 蝶形图同上类似
按时间抽取的基—2FFT算法 (三)2点DFT 按上述办法不断划分下去,直到最后剩下2点DFT,2 点DFT实际上只有加减运算。 这种FFT算法,是在时间上对输入序列的次序是属于 偶数还是属于奇数来进行分解的,所以称作按时间抽 取的算法。 了例:作N=8时FFT的运算流图 由上推证:B(k)=∑x(2)WF(k)=∑x(2r+1)W A(k)=∑x(4W2B(k)=∑x4+2)2 =0 C(k)=∑x(41+1WD(k)=∑x44+3W2
按时间抽取的基－2 FFT算法 按上述办法不断划分下去，直到最后剩下2点DFT，2 点DFT实际上只有加减运算。 这种FFT算法，是在时间上对输入序列的次序是属于 偶数还是属于奇数来进行分解的，所以称作按时间抽 取的算法。 例：作N＝8时FFT的运算流图 由上推证： = = 3 0 4 ( ) (2 ) r r k E k x r W = = + 3 0 4 ( ) (2 1) r r k F k x r W kl l A k x l W2 1 0 ( ) (4 ) = = kl l B k x l W2 1 0 ( ) (4 2) = = + kl l C k x l W2 1 0 ( ) (4 1) = = + kl l D k x l W2 1 0 ( ) (4 3) = = + (三) 2点DFT
按时间抽取的基一2FFT算法 例续:N=8时FFT的运算 展开得 A(0)=x(0)+W2x(4)=x(0)+x(4) A(1)=x(0)+W2x(4)=x(0)-x(4) B(0)=x(2)+x(6) B(1)=x(2)-x(6) C(0)=x(1)+x(5) C(1)=x(1)-x(5) D(0)=x(3)+x(7) D(1)=x(3)-x(7)
按时间抽取的基－2 FFT算法 例续：N＝8时FFT的运算 (1) (0) (4) (0) (4) (0) (0) (4) (0) (4) 1 2 0 2 A x W x x x A x W x x x = + = − = + = + 展开得： (1) (3) (7) (0) (3) (7) (1) (1) (5) (0) (1) (5) (1) (2) (6) (0) (2) (6) D x x D x x C x x C x x B x x B x x = − = + = − = + = − = +
按时间抽取的基一2FFT算法 例续:N=8点FFT的运算流图: x(0) A(0) E(0) Ⅹ (4)W0 A(1) E(1) B(OW E(2) x(6) B(1)W E(3) X(3) 0 x(1) C(0) F(OW 0 x(5) C(1) F(1)W X(5) D()w0 F(2WN D(1)W x(7)① S F(3)WN X(7)
例续：N=8点FFT的运算流图： x(0) x(4) x(2) x(6) x(1) x(5) x(3) x(7) WN 0 A(0) -1 A(1) WN 0 WN 0 W 0 N -1 -1 -1 B(0) B(1) D(0) C(0) C(1) D(1) WN 0 E(0) E(2) -1 WN 2 WN 0 WN 2 E(1) E(3) F(0) F(1) F(2) F(3) X(0) N X(4) 0 -1 W -1 -1 -1 -1 -1 -1 X(1) X(2) X(3) X(5) X(6) X(7) N 1 N 2 N 3 W W W 按时间抽取的基－2 FFT算法
按时间抽取的基-2FFT算法 二运算量分析 由上例分析可知,N=8=3需三级蝶形运算由此可知 N=24共需L级蝶形运算,L=log2N 每级都由N/2个蝶形运算组成 每个蝶形运算有一次复乘,两次复加。 因此,N点的FFT的运算量为 复乘mF=(N2)=(N/2)Nog2N 复加:aF=2*(N2)L=N“og2N 即计算量远比DFT的计算量小 N越大,FFT的优点越明显
按时间抽取的基－2 FFT算法 由上例分析可知，N=8= 2 3 需三级蝶形运算,由此可知： • N=2 L 共需L级蝶形运算， L＝log2 N ； • 每级都由N/2个蝶形运算组成； • 每个蝶形运算有一次复乘，两次复加。 因此，N点的FFT的运算量为： 复乘: mF =（N/2）*L=（N/2）*log2 N 复加: aF =2*（N/2）*L=N*log2 N 即计算量远比DFT的计算量小。 N越大，FFT的优点越明显。 二 运算量分析