-第3快速疼里叶变换一 x1(0) x1(1) x1(1)=x(2) 点 2-|Xx1(2) x(2)=x(4) DFT X(2) x1(3) X(3) X,(O) Wo x2(O)=x(1) X(4 x2(1) X(5) 点 2|x,(2)W2 x2(2)=x(5) DET (6 X, 3)WA x2(3)=x(7) X(7) 图3-2按时间抽取将一个N点DFT分解 为两个M2点DFT(N=8)
第3章 快速傅里叶变换 图 3-2 按时间抽取将一个N点DFT分解 为两个N/2点DFT（N=8） X1 (0) X1 (1) x 1 (0)＝x(0) X(0) X(1) X1 (2) X1 (3) － 1 － 1 0 WN DFT 2 点 x1 (1)＝x(2) N x1 (2)＝x(4) x1 (3)＝x(6) X(2) X(3) X2 (0) X2 (1) x 2 (0)＝x(1) X(4) X(5) X2 (2) X2 (3) DFT 2 点 x2 (1)＝x(3) N x2 (2)＝x(5) x2 (3)＝x(7) X(6) X(7) 1 WN 2 WN 3 WN － 1 － 1
-第3快速疼里叶变换一 个N点DFT分解为两个M2点DFT,每一个M2点DFT只需 (N2)2=N24次复数乘法,M2(M21)次复数加法。两个N2点DFT 共需2×(M2)2=N2/2次复数乘法和N(N2-1)次复数加法。此外,把 两个M2点DFT合成为N点DFT时,有M2个蝶形运算,还需要M2 次复数乘法及2×M2=N次复数加法。因而通过第一步分解后, 总共需要(N2)+(M2)=NN+1)2≈N2/2次复数乘法和NM2 )+N=M次复数加法。由此可见,通过这样分解后运算工作量 差不多节省了一半。 既然这样分解是有效的,由于N=2M,因而N2仍是偶数,可 以进一步把每个M2点子序列再按其奇偶部分分解为两个M4点的 子序列
第3章 快速傅里叶变换 一个N点DFT分解为两个N/2点DFT，每一个N/2点DFT只需 (N/2) 2=N2 /4次复数乘法，N/2(N/2-1)次复数加法。两个N/2点DFT 共需2×(N/2) 2=N2 /2次复数乘法和N(N/2-1)次复数加法。此外，把 两个N/2点DFT合成为N点DFT时，有N/2个蝶形运算，还需要N/2 次复数乘法及2×N/2=N次复数加法。因而通过第一步分解后， 总共需要 (N2 /2)+(N/2)=N(N+1)/2≈N2 /2 次复数乘法和 N(N/2- 1)+N=N2 /2次复数加法。由此可见，通过这样分解后运算工作量 差不多节省了一半。 既然这样分解是有效的，由于N=2 M ，因而N/2仍是偶数，可 以进一步把每个N/2点子序列再按其奇偶部分分解为两个N/4点的 子序列
-第5快速傅里叶度换 (2)=x3() (3-13) x1(2+1)=x() X(k)=∑x1(2)22+∑x(21+1形2 =∑x(WMk4+A2∑x1()W =X3(k)+WM2X4(k)k=0 4
第 3 章 快速傅里叶变换 1 4 0,1, , (2 1) ( ) (2 ) ( ) 1 4 1 3 = − + = = N l x l x l x l x l （ 3 -13 ） 1 4 ( ) ( ) 0,1, , ( ) ( ) ( ) (2 ) (2 1) 3 / 2 4 1 4 0 / 2 4 / 4 1 4 0 3 / 4 1 4 0 (2 1) 1 / 2 1 4 0 2 1 1 / 2 = + = − = + = + + −= −= −= + −= N X k W X k k x l W W x l W X k x l W x l W kN Nl l kN kN Nl l k N Nl l k N Nl l k N
-第3快速疼里叶变换一 且 X+k=X2(k)-W2x4(k)k=01;’4 4 式中 N X(k)=∑x()W4 X()=∑x1(J4 (3-15) 图3-3给出N=8时,将一个M2点DFT分解成两个M4点DFT, 由这两个M4点DFT组合成一个M2点DFT的流图
第3章 快速傅里叶变换 且 ( ) ( ) 4 1 3 / 2 4 k X k W X k N X k = − N + 1 4 = 0,1, , − N k 式中： − = − = = = 1 4 0 4 4 / 4 1 4 0 3 3 / 4 ( ) ( ) ( ) ( ) N l l k N N l l k N X k x l W X k x l W （3-14） （3-15） 图3-3给出N=8时，将一个N/2点DFT分解成两个N/4点DFT， 由这两个N/4点DFT组合成一个N/2点DFT的流图
-第3快速疼里叶变换一 x2(0) x20)=x10)=x(0) x1(0) 点 x3(1) x3(1)=x1(2)=x(4) DFT x1(1) x4(0)W0 x4(0)=x1(1)=x(2) N/2 x1(2) 点 A( WN/ x4(1)=x1(3)=x(6 DFT x1(3) 图3-3N2点DFT分解为两个N4点DFT
第3章 快速傅里叶变换 图 3-3 N/2点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 1 WN / 2