(3)对X(k)和X4k)进行蝶形运算,前半部为 X(0)~X(3),后半部分为X(4)X(7) 整个过程如下图所示 X1(0 x1(0)=x(0 X(0) x1(1)=(2 W幻点X1(1 X(1) x1(2)=(4 DFT X1(2 X(2) x1(3x(6 X1(3) Ⅹ(3) X2(0) x2(0x(1) Ⅹ(4) x2(1)x()-M2成 X2(1)W (2)3(5)mFrx2(2 X(5) 3)x(7) X(6) X2(3) Ⅹ(7)
x1(0)=x(0) x1(1)=x(2) N/2点 x1(2)=x(4) DFT x1(3)=x(6) x2(0)=x(1) x2(1)=x(3) N/2点 x2(2)=x(5) DFT x2(3)=x(7) 1 2 ~ ~ X1(0) X1(1) X1(2) X1(3) X2(0) X2(1) X2(2) X2(3)WN 2 WN 1 WN 0 WN 3 -1 -1 -1 -1 X(0) X(1) X(2) X(3) X(4) X(5) X(6) X(7) (3)对X (k)和X (k)进行蝶形运算,前半部为 X(0) X(3),后半部分为X(4) X(7) 整个过程如下图所示:
(二)N/4点DFT 由于N=2L,所以N/2仍为偶数,可以进 步把每个N/2点的序列再按其奇偶部分 分解为两个N/4的子序列。例如,n为偶 数时的N/2点分解为 x1(2/)=x3(,0,1 x1(2+1)=x4(),0,, 进行N/4点的DFT,得到 X(k)=∑x3(JMA4=∑x(2)M2(偶中偶) =0 =0 X(k)=∑x1(k4=x1(21+1)W21(偶中奇)
由于N=2 L ,所以 N/2仍为偶数,可以进 一步把每个N/2点的序列再按其奇偶部分 分解为两个N/4的子序列。例如，n为偶 数时的 N/2点分解为: (二) N/4点DFT (2 ) ( ), 0,1, , 1 1 3 4 = − N x l x l (2 1) ( ), 0,1, , 1 1 4 4 + = − N x l x l 进行N/4点的DFT,得到 l k N l l k N l l k N l l k N l X k x l W x l W X k x l W x l W N N N N (2 1) / 2 1 0 / 4 1 1 0 4 4 2 / 2 1 0 / 4 1 1 0 3 3 ( ) ( ) (2 1) ( ) ( ) (2 ) 4 4 4 4 + − = − = − = − = = = + = = (偶中偶) (偶中奇)
从而可得到前N4的X/ X1(k)=X3(k)+WX4(k) k=0.1.….N-1 后N4的X1(k N X1(+k)=X3(k)-WgX4(k) 4 k=0.1.…-1
( ) ( ) ( ) 1 3 4 2 X k X k W X k k = + N 0,1, , 1 4 = − N k 从而可得到前N/4的X1 (k) ) ( ) ( ) 4 ( 1 3 4 2 k X k W X k N X k + = − N 后N/4的X1 (k)为 0,1, , 1 4 = − N k
回样对n为奇数时,M2点分为两个M点 的序列进行DFT,则有: X5(k)=∑x2(21)WM4=∑x()WM4(奇中偶) x。(k)=∑x2(21+1)Wk4=2x)W4(奇中奇) 由x5(k)、X6(k进行碟形运算,得: X2(k)=X3(k)+W2X6(k);k=02….4 X2(+k)=X5(k)-WM2X6(k);k=01
(奇中偶) = + = = = − = − = − = − = 1 0 / 4 6 / 4 1 0 6 2 1 0 5 / 4 1 0 5 2 / 4 4 4 4 4 ( ) (2 1) ( ) ( ) (2 ) ( ) N N N N l l k N l k N l l l k N l l k N X k x l W x l W X k x l W x l W (奇中奇) 同样对n为奇数时，N/2点分为两个N/4点 的序列进行DFT，则有: 1 4 X (k) X (k) W X (k);k 0,1, , 6 k 2 = 5 + N/2 = − N 1 4 k) X (k) W X (k);k 0,1, , 4 N X ( 6 k 2 + = 5 − N/2 = − N 由X5 (k)、X6 (k)进行碟形运算，得：
例如,N=8时的DFT可分解为四个N/4的DF, 具体步骤如下: (1)将原序列x(n)的“偶中偶”部分: x3()=x1(r)=x(n) x3(0)=x1(0)=x(0) x3()=x1(2)=x(4) 构成N4点DFT,从而得到X3O),X3(1
例如,N=8时的DFT可分解为四个N/4的DFT, 具体步骤如下: (1) (2) (4) (0) (0) (0) ( ) ( ) ( ) 3 1 3 1 3 1 x x x x x x x l x r x n = = = = = = (1) 将原序列x(n)的“偶中偶”部分: 构成N/4点DFT，从而得到X3 (0), X3 (1)