-第5快速傅里叶度换 X2(k)也可进行同样的分解: x2(k)=X5(k)+WN26(k) k=0 N X2+k =X(k)-WN12-X6(k) N 式中: X()=∑x()WK lk k N/4 ∑x(21)W N/4 X()=∑x(M4=Ex1(21+1形M4
第3章 快速傅里叶变换 X2 (k)也可进行同样的分解： = − + = + ( ) ( ) 4 ( ) ( ) ( ) 2 5 / 2 6 2 5 / 2 6 k X k W X k N X X k X k W X k k N k N 1 4 = 0,1, , − N k 式中： − = − = − = − = = = + = = 1 4 0 2 / 4 1 4 0 6 6 / 4 1 4 0 2 / 4 1 4 0 5 5 / 4 ( ) ( ) (2 1) ( ) ( ) (2 ) N l l k N N l l k N N l l k N N l l k N X k x l W x l W X k x l W x l W
-第3快速疼里叶变换一 x1(0) x3(0)=x1(0)=x(0) 点 Y(0 X1(1) x3(1)=x1(2)=x(4) DFT X4(0)WM x1(2) x40)=x1(1)=x(2) 点 X(2) 4|x4(1)W X1(3) x4(1)=x1(3)=x6) DFT X(3) Y(OWN x5(0)=x2()=x(1) x0) 点 X,(1)W x5(1)=x2(2)=x(5) DFT X(5) (0)W x,(2)W 点 X(6 X(1)W X2(3)W x6(1)=x2(3)=x(7) DFT X(7) 图3-4个N=8点DFT分解为四个N4点DF
第3章 快速傅里叶变换 图 3-4 一个N=8点DFT分解为四个N/4点DFT DFT 4 点 N X3 (0) X3 (1) x 3 (0)＝x 1 (0)＝x(0) x3 (1)＝x1 (2)＝x(4) X1 (0) X1 (1) DFT 4 点 N X4 (0) X4 (1) x4 (0)＝x1 (1)＝x(2) x 4 (1)＝x 1 (3)＝x(6) X1 (2) X1 (3) － 1 － 1 0 WN 2 WN X(0) X(1) X(2) X(3) DFT 4 点 N X5 (0) X5 (1) x 5 (0)＝x 2 (0)＝x(1) x5 (1)＝x2 (2)＝x(5) X2 (0) X2 (1) DFT 4 点 N X6 (0) X6 (1) x6 (0)＝x2 (1)＝x(3) x 6 (1)＝x 2 (3)＝x(7) X2 (2) X2 (3) － 1 － 1 X(4) X(5) X(6) X(7) 0 WN 1 WN 2 WN 3 WN － 1 － 1 － 1 － 1 0 WN 2 WN
-第3快疼里叶变换 根据上面同样的分析知道,利用四个M4点的DFT及两级蝶 形组合运算来计算N点DFT,比只用一次分解蝶形组合方式的计 算量又减少了大约一半 最后,剩下的是2点DFT,对于此例N8,就是四个M4=2 点DFT,其输出为X3(k),X(k),X(k),X6k),k=0,1,这由式 (3-14)~式(3-17)四个式子可以计算出来。例如,由式(3 14)可得: X3(O)=x3(O)+W2x(1)=x(0)+W2x(4)=x(0)+Wx(4) (3-16 X3(1)=x3(0)+W2x3(1)=x(0)+M2x(4)=x(0)-W0x(4) (3-17 式中,W=e2=e=-1=-形,故上式不需要乘法。类 似地,可求出X),4(4,6
第3章 快速傅里叶变换 根据上面同样的分析知道，利用四个N/4点的DFT及两级蝶 形组合运算来计算N点DFT，比只用一次分解蝶形组合方式的计 算量又减少了大约一半。 最后，剩下的是2点DFT，对于此例N=8，就是四个N/4=2 点DFT，其输出为X3 (k)，X4 (k)，X5 (k)，X6 (k)，k=0, 1，这由式 （3-14）～式（3-17）四个式子可以计算出来。例如，由式（3- 14）可得： (1) (0) (1) (0) (4) (0) (4) (0) (0) (1) (0) (4) (0) (4) 1 0 3 2 1 3 3 2 0 0 3 2 0 3 3 2 X x W x x W x x W x X x W x x W x x W x N N = + = + = − = + = + = + 式中， , 故上式不需要乘法。 类 似地, 可求出X4 (k)，X5 (k)，X6 (k)。 0 1 2 2 1 2 1 N j j W = e = e = − = −W − − （3-16） （3-17）
-第3快速疼里叶变换一 这种方法的每一步分解,都是按输入序列在时间上的次序 是属于偶数还是属于奇数来分解为两个更短的子序列,所以称 为“按时间抽取法”。 x(0) X(0) x(4) x(2) X(2) W x(( X(3) X(4) x65)· X(5) x(3) X(6 W W x(7) X(7) 图3-5N=8按时间抽取的FFT运算流图
第3章 快速傅里叶变换 这种方法的每一步分解，都是按输入序列在时间上的次序 是属于偶数还是属于奇数来分解为两个更短的子序列，所以称 为“按时间抽取法” 。 图 3-5 N=8 按时间抽取的FFT运算流图 x(0) X(0) x(4) X(1) － 1 0 WN x(2) X(2) x(6) X(3) － 1 0 WN 0 WN 2 WN － 1 － 1 x(1) X(4) x(5) X(5) － 1 0 WN x(3) X(6) x(7) X(7) － 1 0 WN 0 WN 2 WN － 1 － 1 0 WN 1 WN 2 WN 3 WN － 1 － 1 － 1 － 1
-第5快速傅里叶度换 3.32按时间抽取的FFT算法与直接计算DFT运算量的比较 由按时间抽取法FFT的流图可见,当N=2M时,共有M级蝶形, 每级都由M2个蝶形运算组成,每个蝶形需要一次复乘、二次复 加,因而每级运算都需M2次复乘和N次复加,这样M级运算总共 需要 N N 复乘数 m=-M=-1bN 复加数 a= NM=Ibn 式中,数学符号b-og2
第3章 快速傅里叶变换 3.3.2 按时间抽取的FFT算法与直接计算DFT运算量的比较 由按时间抽取法FFT的流图可见，当N=2M时，共有M级蝶形， 每级都由N/2个蝶形运算组成，每个蝶形需要一次复乘、 二次复 加，因而每级运算都需N/2次复乘和N次复加，这样M级运算总共 需要 复乘数 a NM N bN bN N M N m F F 1 1 2 2 = = = = 复加数 式中，数学符号lb=log2